What is the reason for using a double pointer when adding a node in a linked list?

Question

The two code examples below both add a node at the top of a linked list. But whereas the first code example uses a double pointer the second code example uses a single pointer

code example 1:

struct node* push(struct node **head, int data) {         struct node* newnode = malloc(sizeof(struct node));         newnode->data = data;         newnode->next = *head;         return newnode; }  push(&head,1); 

code example 2:

struct node* push(struct node *head, int data) {         struct node* newnode = malloc(sizeof(struct node));         newnode->data = data;         newnode->next = head;         return newnode; }  push(head,1) 

Both strategies work. However, a lot of programs that use a linked list use a double pointer to add a new node. I know what a double pointer is. But if a single pointer would be sufficient to add a new node why do a lot of implementations rely on double pointers?

Is there any case in which a single pointer does not work so we need to go for a double pointer?

Answer 1

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.

Edit:

Pointer to pointer(Double pointers) also allows for creation for multiple user defined data types within a same program(Example: Creating 2 linked lists)

To avoid complexity of double pointers we can always utilize structure(which works as an internal pointer).

You can define a list in the following way:

typedef struct list {     struct node* root;     } List;  List* create() {     List* templ = malloc(sizeof(List));     templ->root = NULL;     return templ; } 

In link list functions use the above List in following way: (Example for Push function)

void Push(List* l, int x) {              struct node* n = malloc(sizeof(struct node));     n->data = x;     n->link = NULL;          printf("Node created with value %d\n", n->data);     if (l->root == NULL) {         l->root = n;     } else {         struct node* i = l->root;         while (i->link != NULL){             i = i->link;         }         i->link = n;     } } 

In your main() function declare the list in follow way:

List* list1 = create();  push(list1, 10);