Why double pointer is used in linked list?

Some implementations pass a pointer to pointer parameter to allow changing the head pointer directly instead of returning the new one. Thus you could write:

// note that there's no return value: it's not needed void push[struct node** head, int data] { struct node* newnode = malloc[sizeof[struct node]]; newnode->data=data; newnode->next=*head; *head = newnode; // *head stores the newnode in the head } // and call like this: push[&head,1];

The implementation that doesn't take a pointer to the head pointer must return the new head, and the caller is responsible for updating it itself:

struct node* push[struct node* head, int data] { struct node* newnode = malloc[sizeof[struct node]]; newnode->data=data; newnode->next=head; return newnode; } // note the assignment of the result to the head pointer head = push[head,1];

If you don't do this assignment when calling this function, you will be leaking the nodes you allocate with malloc, and the head pointer will always point to the same node.

The advantage should be clear now: with the second, if the caller forgets to assign the returned node to the head pointer, bad things will happen.

Although the previous answers are good enough, I think it's much easier to think in terms of "copy by value".

When you pass in a pointer to a function, the address value is being copied over to the function parameter. Due to the function's scope, that copy will vanish once it returns.

By using a double pointer, you will be able to update the original pointer's value. The double pointer will still be copied by value, but that doesn't matter. All you really care is modifying the original pointer, thereby bypassing the function's scope or stack.

Hope this answers not just your question, but other pointer related questions as well.

In your particular example there is no need for the double pointer. However it can be needed, if, for example, you were to do something like this:

struct node* push[struct node** head, int data] { struct node* newnode = malloc[sizeof[struct node]]; newnode->data=data; newnode->next=*head; //vvvvvvvvvvvvvvvv *head = newnode; //you say that now the new node is the head. //^^^^^^^^^^^^^^^^ return newnode; }

Video liên quan