Double pointer on linked list in C

Question

In a simple linked list, why pass a double pointer when inserting a node? What is the difference with the second code?

void push(struct node **headRef, int data);
void push(struct node *head, int data);

Answer 1

C function calls always pass the value of the arguments. When you are inside the function, you have a copy of the values from the caller placed in new variables.

You can change the value of these copies inside the function but the values the caller have, will remain the same.

Example:

void foo(int n)
{
    n = 1;
    printf("In foo: %d\n", n);  // Will print 1
}

void bar()
{
     int n = 42;
     printf("In bar: %d\n", n);  // Will print 42
     foo(n);
     printf("Back in bar: %d\n", n);  // Will still print 42
}

As you can see, the change made to n inside foo doesn't change n inside bar.

So what if you really wanted n inside bar to change?

That's where you instead of passing n passes a pointer to n.

Like:

void foo(int *n)  // Note the *
{
    *n = 1;
    printf("In foo: %d\n", *n);  // Will print 1
}

void bar()
{
     int n = 42;
     printf("In bar: %d\n", n);  // Will print 42
     foo(&n);                    // Note the & to get a pointer to n
     printf("Back in bar: %d\n", n);  // Will now print 1
}

This is also the difference between your code lines:

void pushA(struct node **headRef, int data);
void pushB(struct node *head, int data);

struct node *head = NULL;
pushA(&head, 42);   // head may be changed after this call
pushB(head, 42);    // head is unchanged after this call

The first version is probably what you want, i.e. when push-ing a new element to the list you want to insert the element in the front and therefore need to change the value of head.

An alternative could be to have the function return a pointer to the new head:

struct node* push(struct node *head, int data);

struct node *head = NULL;
head = push(head, 42);

Answer 2

In the first case, you are pointing a reference to the head node while in the second case, you are pointing a reference to the first node of the linked list.

Diagramatically:

// Original List structure
head -> first node -> second node

// first case
void push(struct node **headRef, int data);

head -> first node -> second node
 ^
 |
headRef

--------------------------------------
// second case
void push(struct node *headRef, int data);

head -> first node -> second node
            ^
            |
        headRef

Should you prefer one over the other? It depends.

If you want to be able to modify the value of the head node then you should use double pointer else just use Case 2.

You should also take a look here: What is the reason for using a double pointer when adding a node in a linked list?