Why did the author use double pointer in this linked list insert operation?

Question

In this implementation of linked list insertion, the author uses double pointer to pass the linked list to the method.

I couldn't understand why he didn't use single pointer. Could you explain the reason for using double pointer?

void insert_list(list **l, item_type x)
{
    list *p; /* temporary pointer */
    p = malloc( sizeof(list) );
    p->item = x;
    p->next = *l;
    *l = p;
}

In other words, what would be wrong with the following implementation?

void insert_list(list *l, item_type x)
{
    list *p; /* temporary pointer */
    p = malloc( sizeof(list) );
    p->item = x;
    p->next = l;
    l = p;
}

If he had used a single pointer he would not be able to transmit the allocated pointer to the caller. — Jabberwocky, Apr 14 '16 at 08:21
@MichaelWalz ... without using the return value (or global variable). — MikeCAT, Apr 14 '16 at 08:22
@MichaelWalz But AFAIU, he doesn't transmit the allocated pointer to the caller right? — Utku, Apr 14 '16 at 08:23

blazs · Answer 1 · 2016-04-14T08:34:51.953

4

Note that list** l is a pointer to a pointer to list. The statement p->next = *l says that p->next points to the node **l. And then we modify the pointer *l to point to p; we can do this because we were passed a pointer to a pointer.

Here's the changes that happen to the list (graphically):

... -> some_node -> ...

We insert a new node with item x just before l:

... -> new_node -> some_node -> ...

Nice thing about the code is that it avoids some cases that would emerge if you were not given a pointer to a pointer. It's much cleaner.

The code that you gave,

void insert_list(list *l, item_type x)
{
    list *p; /* temporary pointer */
    p = malloc( sizeof(list) );
    p->item = x;
    p->next = l;
    l = p;
}

receives a copy of a pointer to a node; this means it cannot modify the variable (i.e. it can only make "local" changes). When the function returns, l will still point to the same node. If you passed a pointer to that pointer, however, you would be able to modify it (this is the case in the first function).

edited Apr 14 '16 at 08:34

answered Apr 14 '16 at 08:23

blazs

4,705
24
38

I have edited the question. – Utku Apr 14 '16 at 08:25
I have edited the answer. :-) – blazs Apr 14 '16 at 08:31
1

I get it. Then, actually _everything_ in C is pass-by-value right? That's why we need the double pointer to modify the list, instead of some local copy pointer that will be demolished as soon as we leave the method. – Utku Apr 14 '16 at 08:34
If that's OK, I will accept the second answer, because it shows how calls to different versions of the method should be. But I have upvoted both answers :) – Utku Apr 14 '16 at 08:41
1

It's okay; I'm very glad the answer helped you with understanding that we need the double pointer because everything is passed by value. – blazs Apr 14 '16 at 08:43

score 4 · Answer 2 · answered Apr 14 '16 at 08:44

A simple way to think about it is this: if we want a function to be able to modify the value of an int then we pass a pointer to it (int*)

So if we want a function to be able to modify a pointer, then we pass a pointer to it.

An alternative approach, that avoids the pointer-to-pointer is for the function to return the new list* like this:

list* insert_list(list *l, item_type x)
{
    list *p = malloc( sizeof(list) ); // new node
    p->item = x;
    p->next = l;
    return p;
}

But that approach relies on the caller using the function correctly, like this:

my_list = insert_list(my_list, x);

which introduces a lot of scope for potential errors. In general you should always try to design APIs that are difficult to use incorrectly.

Also I know this is just example code, but in production code you would check that the `malloc` succeeds. If `malloc` fails then it returns null and the subsequent lines will crash due to null pointer dereferences. — GrahamS, Apr 14 '16 at 10:36
Good note about `NULL` concern. Detail: code _may_ crash due to null pointer dereferences. — chux - Reinstate Monica, Apr 14 '16 at 14:39

Jabberwocky · Accepted Answer · 2016-04-14T10:24:56.777

Ìn the second version of your function the last statement l = p; is pointless, because it just modifies the l parameter which is actually a local variable.

list *thelist = NULL;
insert_list(thelist, someitem);
// you expect thelist to point to some memory location allocated in insert_list
// but actually thelist will still be NULL here.

The first version will be called like this:

list *thelist = NULL;
insert_list(&thelist, someitem);
// we pass a pointer to thelist, which is actually a pointer to a pointer
// now thelist points to the memory location allocated in insert_list

Another way to write the function would be like this:

list *insert_list(list *l, item_type x)
{
    list *p; /* temporary pointer */
    p = malloc( sizeof(list) );
    p->item = x;
    p->next = l;
    return p;
}

...
list *thelist = NULL;
thelist = insert_list(thelist, someitem);

Why did the author use double pointer in this linked list insert operation?

3 Answers3