Why should we use double pointer for adding node in front/back, but not in the middle?

Question

I have this code which creates new node at the very front:

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   
    new_node->data  = new_data;
   
    new_node->next = (*head_ref);
   
    (*head_ref)    = new_node;
}

And I have this code which creates a new node after another one:

void insertAfter(struct Node* prev_node, int new_data) 
{ 
    if (prev_node == NULL) 
    { 
       printf("the given previous node cannot be NULL");     
       return; 
    } 
          
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); 
  
    new_node->data = new_data; 
  
    new_node->next = prev_node->next; 
  
    prev_node->next = new_node; 
}

I understand that if we pass a single pointer a.k.a. head in the first case, the changes will take effect only in the push function, rather than the whole program. That's why we use reference to head to change what it points to.

In the second case, though, we pass a single pointer. I just don't understand why when we are not using reference to the previous node, the code will still work even though we are changing next to point to the new node.

Shouldn't these changes remain only in the insertAfter function?

Answer 1

In the first function

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   
    new_node->data  = new_data;
   
    new_node->next = (*head_ref);
   
    (*head_ref)    = new_node;
}

there is changed the pointer itself to the head node. So the function needs to deal with the original pointer not with a copy of its value.

So you need to pass the pointer to th head node by reference.

In C passing by reference means passing an object indirectly through a pointer to it. In this case dereferencing the pointer like in this statement of the function

    (*head_ref)    = new_node;

the function has a direct access to the original passed object.

In the second function

void insertAfter(struct Node* prev_node, int new_data) 
{ 
    if (prev_node == NULL) 
    { 
       printf("the given previous node cannot be NULL");     
       return; 
    } 
          
    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); 
  
    new_node->data = new_data; 
  
    new_node->next = prev_node->next; 
  
    prev_node->next = new_node; 
}

the pointer prev_node itself is not being changed. It is the node pointed to by the pointer that is being changed. So there is no need to pass the original pointer to the function by reference. On the other hand the node pointed to by the pointer prev_node is passed by reference due to the pointer. And using the pointer you can change data members of the pointed node.

Answer 2

The explanation for both cases lies in the fact that pointers, as any other variable in C, are passed by value.

When you change the value of a pointer passed as parameter, within a function, you need to pass a pointer to that pointer because you will be changing the pointer itself.

If you want to change the value of the variable where it points to you can just pass a copy of the pointer. It will still work because you will be changing the value stored in the address stored in that pointer, a copy of the address will do just fine.

Example:

void func(int *ptr)
{
    static int a = 20;
    *ptr = 10; // changing the value stored in the address pointed by ptr
    ptr = &a;  // changing ptr itself, (spoiler, won't reflect in the original)
}

int main()
{
    int var;
    int *ptr = &var;

    func(ptr);
    printf("%d", *ptr);
}

You'll see that the variable where ptr is pointing to is still var, not a, and the output will be 10, because, again, you are able to change the value of the variable to which the pointer is pointing to.

---

Whereas if you pass a pointer to the pointer:

void func(int **ptr)
{
    static int a;
    *ptr = &a;  // changing the value of the pointer
    **ptr = 20; // changing the value of the variable stored int the address stored in ptr
}

int main()
{
    int var = 10;
    int *ptr = &var;
  
    func(&ptr);
    printf("%d", *ptr);
}

Now ptr will be pointing to a, not to var and the output will be 20, we were able to change both the pointer value and the value stored in the address stored in the pointer.