Thread: Other function, Node at the end of a List

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    33

    Other function, Node at the end of a List

    Hi everybody,

    I have another doubt about another function.
    Sorry if this will be boring or silly d for anyone, but I began to study C language only two months ago.

    The function is thought to insert a new node at the end of a list.
    The function is named "suf_insert".

    Code:
    struct list{
        float value;
        struct list *next_ptr;
        }
    
    
    
    void suf_insert(struct list ** doublepointer, float value)
    /*INPUT of the function:
    -a pointer which points to a pointer which points to a record;
    -a float.*/
    
    
    
          while (*doublepointer != NULL) { /*while the pointer pointed by the doublepointer of the input si different from NULL*/
    
    
                doublepointer = &((*doublepointer)->next_ptr); 
    /*I can't understand this line.
    How can I make my double pointer "slide" from one record to another? What is happening here?*/
    
    
          } pre_insert(ptrptr, value); /*here I use a known function which insert the node when I reach the end of the list*/
        }

    My double pointer at the beginning points to a pointer which point to the first node of my linked list.
    I can't understand how it can slide from a node to another.

    Moreover, I can't understand how it can point "automatically" to the part of the node which contain next_ptr.
    I tried to study the theory, but I think I'm not understanding something about the pointer and the record (node).

    Thanks to anyone who will be able to clear up my doubts!!
    Last edited by Salem; 06-24-2019 at 10:05 PM. Reason: Yet more font size abuse!!! QUIT DOING IT

  2. #2
    Registered User
    Join Date
    May 2019
    Posts
    213
    First, to be safe one should not dereference a pointer without checking it first. doublepointer is a pointer, it just happens to point to a pointer. It could be null, which is to say you may need to protect against a crash with

    Code:
    if ( doublepointer == NULL ) return;
    This is in the "novice" form. We may well say "if ( !doublepointer )", but at least the "novice" form is clear.

    It checks to see that doublepointer is valid before we dereference it in the next line

    Code:
    while (*doublepointer != NULL)
    When I read further I see "ptrptr" used, but not declared, so I'm not sure what that should say, so I expect a crash (or that it is probably doublepointer), but that ignores the fact that this is not a valid "while" loop. When, exactly, should pre_insert be called? Is it to be called when the "while" finishes, or is it to be called at each loop? It can't go where it is, that is a syntax error relative to the "while" loop syntax.

    Setting that aside we come to:

    Code:
    doublepointer = &((*doublepointer)->next_ptr);
    On first look it seems unwise to use doublepointer here. I'll get to that in a moment.

    What this says is that the current value of (*doublepointer) is a pointer to a list. If I had list *p, and it were earlier set with p = *doublepointer, this interior expression would be (p->next_ptr), which is a little easier to understand. It is the same as (*doublepointer)->next_ptr.

    That evaluates to a list pointer. That pointer has an address, which can be give with &((*doublepointer)->next_ptr), which is the same as &(p->next_ptr) given p from the previous example.

    This address is the address of a pointer, compatible with the "pointer to a pointer" of doublepointer.

    Yet, that is confusing. It works, fine, but isn't what you are actually doing.

    What you are actually doing is more like this:

    Code:
     list *p = *doublepointer;
    
      while ( p != NULL) { 
    
                p = p->next_ptr; 
    
          }; // notice the ';' I put here
    This loops through the list until p is NULL, but I doubt that's what you really need.

    When p is NULL, what do you have? You have NULL.

    Is the purpose not to find the last VALID p?

    Code:
     list *p = *doublepointer;
    
      while ( p != NULL && p->next != NULL) { 
    
                p = p->next_ptr; 
    
          }; // notice the ';' I put here
    Now the list refuses to loop if p is already null (and you have no list anyway).

    However, it stops when the next p is null, leaving you with the last valid p, the last "list *" in the series. It is then ready for the "new" list * to be appended.

  3. #3
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by Niccolo View Post

    Code:
    while (*doublepointer != NULL)
    Thanks for this correction!

    Quote Originally Posted by Niccolo View Post

    When I read further I see "ptrptr" used, but not declared, so I'm not sure what that should say, so I expect a crash (or that it is probably doublepointer), but that ignores the fact that this is not a valid "while" loop. When, exactly, should pre_insert be called? Is it to be called when the "while" finishes, or is it to be called at each loop? It can't go where it is, that is a syntax error relative to the "while" loop syntax.
    Sorry for that! It is a silly mistake. There isn't any 'ptrptr', I wanted to write doublepointer as you foresaw.

    Quote Originally Posted by Niccolo View Post

    Setting that aside we come to:

    Code:
    doublepointer = &((*doublepointer)->next_ptr);
    ...

    Yet, that is confusing. It works, fine, but isn't what you are actually doing.

    What you are actually doing is more like this:
    I'll try to comment your code, let me know if what I wrote is correct (if you want).

    Code:
     list *p = *doublepointer;/* the 'doublepointer' points to the object pointed by 'p'*/
    
      while ( p != NULL) { 
    
                p = p->next_ptr; /*I still don't understand what happen here.
    My pointer 'p' is pointing to one member of my list. 
                    And so what? I can't see how it can slide from a
                                             node of a list to another*/
    
    
          }; // notice the ';' I put here
    Quote Originally Posted by Niccolo View Post
    This loops through the list until p is NULL, but I doubt that's what you really need.

    When p is NULL, what do you have? You have NULL.

    Is the purpose not to find the last VALID p?

    Code:
     list *p = *doublepointer;
    
      while ( p != NULL && p->next != NULL) { 
    
                p = p->next_ptr; 
    
          }; // notice the ';' I put here
    Now the list refuses to loop if p is already null (and you have no list anyway).

    However, it stops when the next p is null, leaving you with the last valid p, the last "list *" in the series. It is then ready for the "new" list * to be appended.

    First of all, thank you very much Niccolo.
    Let me know if you'll be able to explain to me what I don't get about 'p = p->next_ptr'.

  4. #4
    Registered User
    Join Date
    May 2019
    Posts
    213
    Hey @letthem,

    All that I see seems right to me at the moment, you got it.

    As to this (simplified) common idiom:

    Code:
    struct link 
    {
     link *next_ptr;
     //....other values of the link
    };
    
    
    
    while ( p->next_ptr != NULL) 
    { 
      p = p->next_ptr; 
    };
    This assumes that p starts out non-NULL, and is a linked list structure with a member "next_ptr" of the same type as p.

    When such a list is constructed, the "top" of the list is merely an instantiated link, where next_ptr is default initialized to NULL. In that state the container has only one link.

    Subsequent links are added by one of two typical means. In the first approach a new link becomes the "root" of the container, pushing new entries on the front. For that type each new node is created such that it's next_ptr is assigned to the current root of the container, and the root becomes the new node. In this way, after multiple nodes have been added, the root's next_ptr points to the second link, it's next_ptr points to the third link, and continues until the last link which still holds a next_ptr of NULL (the end of the list).

    The second approach appends links to the end of the list. In a singlely linked list, like this link struct suggests, this requires the insert function to traverse the entire list looking for the last valid node (where it's next_ptr is NULL), at which point it appends the new node by setting that last link's next_ptr to the new node, and since the new node was default initialized for it's next_ptr to be NULL, it becomes the new "end" of the container.

    So, given any link *p = root, where root is the top of the list, where p results in a non NULL value, the loop posted above skips forward from link to link until it reaches the node where it's next_ptr is NULL, which is the last link of the container.

  5. #5
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by Niccolo View Post

    The second approach appends links to the end of the list. In a singlely linked list, like this link struct suggests, this requires the insert function to traverse the entire list looking for the last valid node (where it's next_ptr is NULL), at which point it appends the new node by setting that last link's next_ptr to the new node, and since the new node was default initialized for it's next_ptr to be NULL, it becomes the new "end" of the container.

    So, given any link *p = root, where root is the top of the list, where p results in a non NULL value, the loop posted above skips forward from link to link until it reaches the node where it's next_ptr is NULL, which is the last link of the container.
    Super, thanks a lot!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function which insert one Node in a List
    By letthem in forum C Programming
    Replies: 1
    Last Post: 06-24-2019, 03:00 PM
  2. Replies: 6
    Last Post: 04-25-2013, 01:50 AM
  3. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  4. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM

Tags for this Thread