Original head pointer not being changed in the printList function, but the list does change when ins-CodePudding

I've read these two posts/answers regarding the use of double pointers/passing by reference

When printing out a linked list, why is the original head pointer not changed

but one thing still puzzles me.

The head pointer in printList function (with head = head->next traversal) does not get changed in main, because even though we pass it by reference, the function receives a copy of the pointer/address. Which I can understand.

But how come then the whole list gets changed (updated) when inserting a node like

struct node* addLast(struct node* head, struct node* new_node) {
    if (head == NULL)
    {
        head = new_node;
        return head;
    }

    struct node* current = head;
    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = new_node;

    return head;
}

and we call it in main

head = addLast(head, node)

I get that the principle applies to the case when head == NULL (because we return the "new" head), but if not, then we traverse the list again and insert the node.

How come then that the list gets updated (not necessarily in this particular add function only)? Is it not then that the new_node (node created by another function with malloc()) is also a "copy"?

CodePudding user response：

how come then the whole list gets changed (updated) when inserting a node?

As you rightly remark, there are two cases here:

I get that the principle applies to the case when head == NULL (because we return the "new" head)

Indeed. So your question is about the remaining cases where the list is not empty and a node is appended to it.

In that case the returned value is the same pointer as was given as argument: head does not change.

However, the node that head points to has its own next pointer, and that pointer might have changed from NULL to a pointer to the new node. So, although head does not change, the chain of next pointers will have become longer.

Just visualise what happens when we start with an empty list, and then add nodes to it with the following script:

node* createNode(int value) {
    node* newNode = malloc(sizeof(node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    node* head = NULL;
    head = addLast(head, createNode(1));
    head = addLast(head, createNode(2));
    head = addLast(head, createNode(3));
    // ...
    return 0;
}

I just added a function to create a node instance: no surprises there (I hope!)

So when the script starts, we have head:

head: NULL

Then we call createNode(1) which returns a pointer to a node. We can represent that node with a box:

┌────────────┐
│ value: 1   │
│ next: NULL │
└────────────┘

The pointer to this node is passed as second argument to addList, so in that function we have:

 new_node         head: NULL
  ↓
┌────────────┐
│ value: 1   │
│ next: NULL │
└────────────┘

As you correctly noticed, this node reference is returned from the function addList to the caller, and the caller assigns it to its own head variable. So in the main program we now have this state:

 head
  ↓
┌────────────┐
│ value: 1   │ 
│ next: NULL │
└────────────┘

Now to the second node: it is created with createNode(2), and then addList is called with these arguments:

 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘

addList then creates another variable current which starts out with the same reference as head:

 current
 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘

The while loop condition is not true, so it will not iterate. Then current->next = new_node is executed, and this is the most important assignment: it establishes the link between the last node of the list with the new node:

 current
 head                new_node
  ↓                   ↓
┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │ 
│ next: ──────────> │ next: NULL │
└────────────┘      └────────────┘

And finally, head is returned to the caller, who assigns it to their head variable -- this is really a dummy assignment, because head didn't change. What did change is the length of the linked list that head points to.

This should explain it, but let's just add one more node: create_node(3) is passed to addList, so in addList we have this state:

 current
 head                                    new_node
  ↓                                       ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

This time the while condition is true, so current = current->next will bring us into this state:

 head                current             new_node
  ↓                   ↓                   ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: NULL │      │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

The while loop will then exit, and current->next = new_node gets executed:

 head                current             new_node
  ↓                   ↓                   ↓
┌────────────┐      ┌────────────┐      ┌────────────┐
│ value: 1   │      │ value: 2   │      │ value: 3   │ 
│ next: ──────────> │ next: ──────────> │ next: NULL │
└────────────┘      └────────────┘      └────────────┘

And addList terminates by returning the (unchanged) head pointer. The main program performs again the assignment to its own head even though there was no change to that pointer.

I hope this clarifies that even though head does not change anymore, the chain of next pointers does change: the tail node's next pointer changes from NULL to the address of the new node.