Thread: appeand node in list

  1. #1
    Registered User
    Join Date
    Feb 2022
    Posts
    73

    appeand node in list

    I'm stuck with code shown in refrence link How to write C functions that modify head pointer of a Linked List?

    Code:
    voidpush_front(Node** head, int new_val){
    
        Node* new_node = newNode(new_val);
    
        new_node->next = (*head);
    
    
    
        *head = new_node;
    
    }
    
    
    
    intmain(){
    
        Node *head = NULL;
    
    push_front(&head, 2);
    
    }
    
    Pointer hold memory location of other variable and we can obtain the value pointed by pointer using derefrencing

    In code, function create new node I don't understand these two lines in code what does new node point in list and how does it point

    Code:
      new_node->next = (*head);
    
    
    
        *head = new_node;
    

  2. #2
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    Could you post what a Node is?

    Actually I see what's going on here.

    The first line:
    Code:
    new_node->next = (*head);
    Is setting the next field of the new node to the head pointer value.

    The second line:
    Code:
    *head = new_node;
    
    Is setting the head pointer value to the new node value.

    The function:
    Code:
    voidpush_front(Node** head, int new_val){
    ...
    }
    passes a Node** because it changes the original Node pointer value.
    Last edited by G4143; 03-01-2022 at 10:05 PM.

  3. #3
    Registered User
    Join Date
    Apr 2021
    Posts
    97
    This is one of a few fairly-common idioms in linked-lists.

    The key here is that you don't have a "List" structure. Instead, you're using a single Node * variable to hold the pointer to the first node in the list. (If you had a List structure, you would still have to pass a pointer to it. But the type would be different, which might make this whole thing less confusing.)

    Because all C functions get their parameters "by value," the only way to pass a function a modifiable parameter is to use a pointer. Want to change an integer? Pass the function an int * and it can write through the pointer. Want to update the contents of a text buffer? Pass a char *.

    One of the things that can happen with linked lists is an insertion or deletion that affects the very beginning of the list. You might insert "boy" into your list, then try to insert "apple" and need to make the "apple" Node the new first-in-line. Likewise, you might delete the "apple" node and need to set "boy" as the first-in-line. In either case, you need to modify the head variable. Which means you'll have to pass a pointer to it.

    Code:
    errpr_t
    push_front(pointer-to-head, new-value)
    {
    }
    So what type is the new-value? That depends on you. In your example code, it is int.

    What about pointer-to-head? Well, we know what head is. It's a Node *. So we just need the type of &head, which is going to be (Node *)*.

    So let's update our declaration:

    Code:
    error_t
    push_front(
        Node * * head_ptr,
        int new_value)
    {
    }
    Now, how does this work? Well, you will use the actual value of the head in order to work with the list, but in the case that you need to modify the head, you'll use the pointer to it.

    First, let's make an example. We'll start by calling the newNode() function directly in main to create a node and initialize our head variable to point to it. This means that when we start, the linked list pointed to by head already contains exactly one Node.

    Then we call push_front() on our already-set-up linked list. What happens?

    Code:
    void
    push_front(
        Node * * head,
        int new_val)
    {
        Node * new_node = newNode(new_val);
        
        new_node->next = *head;
    
        *head = new_node;
    }
    
    int 
    main(void)
    {
        Node * head = newNode(3);     // Our linked list starts with one node
    
        push_front(&head, 8);
    }
    In the case where we have a list with one or more nodes, we first create a new node, presumably with .value = new_val and .next = NULL. Then we set the ->next pointer of that node to the value of the list-head pointer (which remember we took the address of that, so we have to undo that by using *head in order to get back to where we started).

    At this point, the head variable in main points to (what used to be) the first node in the list. And the new_node variable inside push_front points to a brand-new Node structure that also points to the first node via it's ->next member.

    Then we update the *head pointer inside new_node, which is actually updating the head variable in main. The new_node is installed as the first-in-line value. The push_front function returns and the head list in main now has two elements.

    I think the problem here is that you've got the same names for two items with slightly different types. Instead of calling the variable in main "head" and also calling the first parameter to push_front also "head," maybe it would be better to call it head_ref to reflect that the parameter to push_front is really a pointer to the variable in main.

    Code:
    void
    push_front(
        Node ** head_ref,
        int new_value)
    {
        Node * new_node = newNode(new_value);
    
        new_node->next = *head_ref;  // get value of 'head'
    
        *head_ref = new_node;  // set 'head' to new_node
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 04-25-2013, 01:50 AM
  2. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  3. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  4. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM

Tags for this Thread