I don't understand how this code replaces the head of a linked list... Or how to do it in general

Question

The code that replaces the head:

void push(newnode ** head, int val) 
{
    newnode * new_node;
    new_node = (newnode *) malloc(sizeof(newnode));

    new_node->value = val;
    new_node->next = *head;
    *head = new_node;
}

// Defining head in main()
int main() {
    newnode* head = (newnode*) malloc(sizeof(newnode));
    //Calling push():
    addnode(*head, 4); 
    /* I assumed since push takes a newnode** argument, that head 
    should have an additional asterisk prefixed to it. */
}

The struct I'm using to create nodes:

typedef struct node
{
    int value;
    struct node* next;
} newnode;

head is the head of the linked list; the 1st node. I don't understand why we de-reference head in the argument list for the push function and what I'm Actually doing in the last line and the one before it in the function.

I tried experimenting with the code a little to understand it but I still didn't really get it...

Answer 1

void push(newnode ** head, int val) 
{
    newnode * new_node;
    new_node = (newnode *) malloc(sizeof(newnode));

This allocates a new node and makes new_node point to it.

    new_node->val = val;

This sets the new node's value to the value we want to add.

    new_node->next = *head;

This sets the next node after the new node to be the node that the head pointer currently points to, that is, the current first node.

    *head = new_node;

This makes the head pointer point to the new node, making the new node the first node in the list.

}

Answer 2

First: some issues in your code:

    newnode* head = (newnode*) malloc(sizeof(newnode));

This allocates a node, but leaves its members uninitialised. This is not good, as iterating such a list will lead to undefined behavior when the head->next is used for potentially finding a next node. It must be set to NULL. And as we are at it, there is no good reason to leave the node's value uninitialised either.

Secondly, this malloc duplicates code. You already have a function that performs such allocation and which initialises its members and makes a head pointer point to it. That's really all you want to happen here!

So change the above code to:

newnode* head = NULL;
addnode(*head, 0);

You write in a code comment:

I assumed since push (i.e. addnode) takes a newnode** argument, that head should have an additional asterisk prefixed to it.

Yes, that is correct. This is needed because addnode will want to assign a new pointer value to "your" head, and so it needs to get the address of where to put it. It is a bit misleading to use the name head for this address in addnode, as it really is not the same thing as head in the main function. I suggest to rename it to headPtr. Also in C it is consider better practice to not cast the pointer returned by malloc

void push(newnode ** headPtr, int val) 
{
    newnode * new_node = malloc(sizeof(newnode));

    new_node->value = val;
    new_node->next = *headPtr;
    *headPtr = new_node;
}

I will now assume that version of the code with this corrected code for main:

    newnode* head = NULL;
    addnode(*head, 0);
    addnode(*head, 4);

...and make a visualisation of what happens when this gets executed. We start with head set to NULL:

┌─head─┐
│ NULL │
└──────┘

The addnode function is called with the address of head and the value 0. addnode has its own variable headPtr which now is a pointer to head:

┌─headPtr─┐
│    ┬    │
└────│────┘
     ▼
  ┌─head─┐
  │ NULL │
  └──────┘

With malloc a new node is allocated and initialised with value 0:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │ NULL │      │    0    │
  └──────┘      ├───next──┤
                │   ???   │
                └─────────┘

Then the assignment new_node->next = *headPtr; is made, which copies the value from *headPtr, i.e. from head, i.e. NULL... to that next element:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │ NULL │      │    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

Still, this new node is not yet "in the list": the final assignment of addnode will do this: *headPtr = new_node. This will copy the address of the node to *headPtr, i.e. to head:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │   ├────────►│    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

Note how that will influence what the main function will see when that first call to addnode has returned. head is now no longer NULL. Because we passed a pointer to head, addnode was able to modify head's (pointer) value. This is what we see in main:

  ┌─head─┐      ┌──value──┐
  │   ├────────►│    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

Let's do the second call of addnode in the same way. headPtr will again point to head, and this time the value is 4. A new node is allocated with malloc, and the value member is assigned 4 (I have to make a bit of room in the diagram for it):

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │         │   ???   │
     ▼         └─────────┘
  ┌─head─┐                       ┌──value──┐
  │   ├─────────────────────────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

Now we get to the "magic" two assignments. First new_node->next = *headPtr;. This will establish the link between the new node, and the already existing one (from the previous call to add_node):

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │         │    ├──────┐
     ▼         └─────────┘ │
  ┌─head─┐                 │     ┌──value──┐
  │   ├────────────────────┴────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

And finally, *headPtr = new_node; will make the new node the first node of the list:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │     ┌──►│    ├──────┐
     ▼     │   └─────────┘ │
  ┌─head─┐ │               │     ┌──value──┐
  │   ├────┘               └────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

When back in main, this is what remains:

  ┌─head─┐     ┌──value──┐       ┌──value──┐
  │   ├───────►│    4    │       │    0    │
  └──────┘     ├───next──┤       ├───next──┤
               │    ├───────────►│   NULL  │
               └─────────┘       └─────────┘

Hope this clarifies it.