C double pointer meaning

Question

I cannot understand the meaning of a C code about linked lists that is using double pointers. Here is the code I am reading

    struct list
{
    int value;
    struct list *next;
};
//Insert an element at the begining of the linked list
void insertBegin(struct list **L, int val)
{
    //What does **L mean?
    //Memory allocation for the new element temp
    struct list *temp;
    temp = (struct list *)malloc(sizeof(temp));
    //The new element temp points towards the begining of the linked list L
    temp->next = *L;
    //Set the beginning of the linked list
    *L = temp;
    (*L)->value = val;
}
void loop(struct list *L)
{
    printf("Loop\n");
    //Run through all elements of the list and print them
    while( L != NULL )
    {
        printf("%d\n", L->value);
        L = L->next;
    }
}
struct list* searchElement(struct list *L,int elem)
{
    while(L != NULL)
    {
        if(L->value == elem)
        {
            printf("Yes\n");
            return L->next;
        }
        L = L->next;
    }
    printf("No\n");
    return NULL;
}

int main()
{
    struct list *L = NULL;
    insertBegin(&L,10); // Why do I need 
    return 0;
}

What does **L in the insertElement mean and what is the difference between the **L and the *L in the loop function? Why in the main when struct list *L = NULL is declared I should call the function insertBegin with the argument &L and not a simple L?

I guess *L is a pointer towards the first node of the linked list while **L may point toward any element of the list. However, I am not sure this is correct.

Thank you for your help!

`temp = (struct list *)malloc(sizeof(temp));` --> `temp = malloc(sizeof *temp);` — joop, Mar 12 '15 at 16:42

dtech · Answer 1 · 2015-03-12T16:35:09.167

It means "pointer to a pointer". In C pointers are passed by value, so if you want to be able to modify a pointer passed to a function outside of that function, you have to pass a pointer to it. Passing the pointer will only pass another value for it, which will be modified in the function but will not reflect a change to the value outside of it. Passing as a pointer to pointer essentially allows you to modify the value at the address passed rather than just to modify the local.

Consider those two functions:

void foo(int * p, int * t) {
  p = t;
}

void foo2(int ** p, int * t) {
  *p = t;
}

And the code:

int a = 1, b = 2;
int * p = &a;

foo(p, &b);
// in foo *p == 2, but here *p is still == 1, because p didn't change, only the copy that was passed to foo changed
foo2(&p, &b); // now *p == 2, p was changed in foo2

score 1 · Answer 2 · answered Mar 12 '15 at 16:25

1

The type **L is read as pointer to a pointer to L. So if you have a pointer to an L and takes its address, that is what you get. The pattern of **L in a function argument (in C) is usually used to implement an "out parameter" - a parameter the code can update. To insert at the beginning, you need to update the pointer to the head of the list - that is why that function takes a pointer to the head as a parameter. When assigning to *L, the function updates the parameter.

answered Mar 12 '15 at 16:25

DrC

7,528
1
22
37

What does *L point to? To the head of the list? If yes, it seems to me that you don't really need to use the **L pointer, you could directly change the adress contained in the *L pointer. – George Mar 12 '15 at 16:33
A memory location that can hold a pointer to L. Basically it has the address of a variable or member of type pointer to L. – DrC Mar 12 '15 at 16:34

score 1 · Answer 3 · answered Mar 12 '15 at 16:35

L stores address of the first link in the list. Thus: *L is contents of the first link in the list, and &L is the address of the variable that stores the address of the first link in the list.

In other words, your only way to allocate memory for and initialize a list by passing the argument into a function is by providing &L as an argument. If you pass L as an argument, the function will receive the address of the first link, whereas instead it needs a place where to store the address of the first link.

So you want to modify the adress of the first node, in other words *L. To change *L, you need to use a pointer to *L. That's why we should use the **L? Am I right? — George, Mar 12 '15 at 16:46

score 0 · Answer 4 · answered Mar 12 '15 at 16:27

0

The double pointer in insertBegin is for when you are changing the location of L from where ever L is to the node you are inserting. When calling the function you need &L because you need to pass it by reference because you are changing L

answered Mar 12 '15 at 16:27

Sythe

143
1
1
9

score 0 · Accepted Answer · answered Mar 12 '15 at 17:38

If you want a function to write to a parameter and have that new value reflected in the caller, then you must pass a pointer for that parameter:

void foo( T *p ) // for any type T
{
  *p = new_value(); // write a new value to the thing p points to
}

void bar( void )
{
  T var;
  foo( &var ); // foo writes a new value to var
}

If we substitute T with a pointer type Q *, then the code is

void foo( Q **p ) // for any type Q
{
  *p = new_value(); // write a new value to what p points to
}

void bar( void )
{
  Q *var;
  foo( &var ); // foo writes a new value to var
}

The semantics in both cases are exactly the same; we want foo to update the value stored in var through the pointer p. The only difference is that in the second case var already has a pointer type, so p has to be a pointer to that pointer type.

In the code you posted, the insertBegin function updates the value stored in L, which is a pointer to the head of the list. Since the variable L in main has type struct list *, the type of the parameter L in insertBegin needs to be struct list **.

C double pointer meaning

5 Answers5