Why is a double pointer needed to make changes to head but not elsewhere in a linklist

Question

void insertAtTop(node** head, int value){
    node* temp=new node();
    temp->data=value;
    temp->next=*head;
    *head=temp;
}

void insertAtLast(node*head, int value){
    while(head->next!=NULL){
        head=head->next;
    }
    node*temp=new node();
    temp->data=value;
    temp->next=NULL;
    head->next=temp;
}

I can't understand why you need to use a pointer to pointer to make changes to the head but if you want to add an element elsewhere you can do it simply by sending node* head instead of node** head. Like for insertatLast node*head as argument works but if I did the same for insertAtTop it wouldn't.

Answer 1

You can achieve both insertAtTop and insertAtLast by using both pass by reference and pass by value. I suggest you to read difference between pass by reference and pass by value. You can also read this.

I assume head is declared as node* head;

Pass by reference:

void insertAtTop(node** head, int value){
    node* temp=new node();
    temp->data=value;
    temp->next=*head;
    *head=temp;
}

Call: insertAtTop(&head, value);

void insertAtLast(node** head, int value){
    node* h = *head;
    while(h->next!=NULL){
        h = h->next;
    }
    node* new_node=new node();
    new_node->data=value;
    new_node->next=NULL;
    h->next=new_node;
}

Call: insertAtLast(&head, value);

Pass by value:

node* insertAtTop(node* head, int value){
    node* temp=new node();
    temp->data=value;
    temp->next= head;
    head = temp;
    return head;
}

Call: head = insertAtTop(head, value);

node* insertAtLast(node* head, int value){
    node* original_head = head;
    while(head->next!=NULL){
        head=head->next;
    }
    node*temp=new node();
    temp->data=value;
    temp->next=NULL;
    head->next=temp;
    return original_head;
}

Call: head = insertAtLast(head, value);

Answer 2

You don't have to use a double pointer. See the code below:

node* front(int n, node* head)
{
    node *tmp = new node;
    tmp -> data = n;
    tmp -> next = head;
    head = tmp;
    return head;
}

Answer 3

With a double pointer, you’re passing a pointer to a pointer. When you have a single pointer, dereferencing it gives you the value of the variable. With a double pointer, dereferencing gives you the address of the variable in memory. When you’re adding the node to the front of the list, you’re taking the node you’ve already created for the head node and passing in the address of the pointer to it. And the reason you have to do this for adding to the head of the linked list specifically is that you already have a reference somewhere in memory to the head of the list since a linked list struct is defined as having a head node originally pointing at null and subsequent additions to the front of the list are going to change where to look for the start of that linked list.

Answer 4

There is a double pointer in both. Look at these two analogous lines from the two functions:

*head=temp;  // from insertAtTop

head->next=temp; // from insertAtLast

Note that head->next = temp can be equivalently written as (*head).next = temp.

There is a "double pointer" there: head is a pointer to a structure, and that structure contains a pointer next. Basically these two pictures:

Diagram for *head = temp:

head --> [ *--]---> old_head
            ^
            `-- temp is stored here, replacing the old_head

Diagram for head->next = temp, or (*head).next = temp. For the sake of example, the node structure is represented as three memory cells, the third of which is the next field. The exact memory details depend on your compiler and how you defined the structure!

head  --> [    ]
          [    ] 
          [ *--]--> old_next
             ^
             `-- temp is stored here, replacing old_next

Basically, the only difference is that you we have a structure instead of a just a single pointer object.

In both cases, a pointer is being updated to refer to the newly inserted node. In the insertAtTop case, we have to replace that very pointer which represents the list itself. We are representing a list object as a pointer to the first node. If the list is changed so that it has a different first node, that pointer has to change. When inserting elsewhere in the list, we must update the previous node's next pointer to point to the new node, so we assign to (*head).next.

We could rewrite insertAtLast to use insertAtTop as a subroutine:

node* insertAtLast(node* head, int value){
    /* find the insertion point */
    node* original_head = head;
    while(head->next!=NULL){
        head=head->next;
    }
    /* now treat that as the head */
    (void) insertAtTop(&head->next, value);
    return original_head;
}

If you trace what happens in the call to insertAtHead, you will find that it does exactly the same thing as the code which we replaced. We took out this code:

    node* new_node=new node();
    new_node->data=value;
    new_node->next=NULL;
    h->next=new_node;

But that's almost the same as the body of insertAtHead which is this:

   node* temp=new node();
   temp->data=value;
   temp->next=*head;
   *head=temp;

We pass the value of the expression &h->next as the head parameter. So temp->next = *head is really temp->next = *&h->next where the *& cancel out, leaving temp->next = h->next. But we know that h->next is NULL: our while loop has ensured that. So this is temp->next = NULL, effectively. And of course *head = temp is the same as *(&h->next) = temp, which is h->next = temp.