What's the point of using pointer to pointer?

Question

I found this code on a website for inserting a node in a linked list at the beginning of the list.

void push(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

/* 2. put in the data  */
new_node->data  = new_data;

/* 3. Make next of new node as head */
new_node->next = (*head_ref);

/* 4. move the head to point to the new node */
(*head_ref)    = new_node;
}

This is the function call-

push(&head, 7);

My question is why go the long way by passing the address of a pointer and then subsequently extracting the value at the address inside the function. Why can't we simply pass the pointer head in the function and later make the assignment like -

new_node->next=head_ref;

?

Answer 1

If you passed head and not &head, the line

(*head_ref)    = new_node;

will have to be changed to

head_ref    = new_node;

However, it will be a local change in the function. It won't change the value of head in the calling function. There are two problems with that:

1. The calling function will never get a working list.
2. The memory allocated in the function will be a memory leak.

Answer 2

Variable head in the calling program is a pointer to the head of the list. You need a pointer to this variable in order to update it within push(). So you pass a pointer to a variable that holds a pointer so you can update that variable.

Answer 3

You could also write the code as follows:

struct Node* 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;
    return new_node;
}

and call it as follows:

head = push(head, 7);

It achieves exactly the same thing, i.e. inserts a new node at the head of the list and then updates head to point at that new node. But it wouldn't be as good a solution, in my opinion, because it allows the caller of the push() function to forget to assign the returned value to head at which point you will have orphaned nodes and ultimately memory leaks.

Answer 4

This all related to a programming style you chose. Using a set of functions to manipulate lists makes the program structurally sound. This way you make it more readable. It will also avoid cut-n-paste if you need to manipulate the same list from multiple places or manipulate multiple lists.

The way you organize your function is up to you. I personally like the way in your example. In this case you need to specify your pointer to the head only once int the argument. If you return it from the function instead, you have a higher risk of using a wrong pointer in your program.

'C' has sufficient set of tools to write any type of a program. However sometimes you need to follow specific rules to apply them, like an address of a pointer in your case. Not very convenient but reliable and proven to work. As a 'C' programmer you will get used to it quickly.

You can also look into c++ which has better instruments to make this more convenient.