Why do we use double pointers while passing a Structure argument in C?

Question

I was writing some C-code to implement basic Stack data structure operations like push,pop,etc. I'm using the Linked List implementation of the stack. In this implementation, every time I push a value into the stuck, I create a new node, and set it as the head node of my Linked List. So this involves changing the references of the head node.

void push(stack **t, int ele)
{
stack *new, *temp;
temp=*t;
new=(stack *)malloc(sizeof(stack));
if(new==NULL)
{
    printf("\n stack overflow");
    return;
}
new=(stack *)malloc(sizeof(stack));
new->val=ele;
new->next=*t;
*t=new;

}

If I were to write a similar code using single pointers, then it would be like this

void push(stack *t, int ele)
{
stack *new, *temp;
temp=t;
new=(stack *)malloc(sizeof(stack));
if(new==NULL)
{
    printf("\n stack overflow");
    return;
}
new=(stack *)malloc(sizeof(stack));
new->val=ele;
new->next=t;
t=new;

}

In the function, the head node(**t) appears on the RHS of assignment in all steps but this

 *t=new;

Basically the first code assigns 'new' to the pointer of **t, that is *t, and the second code assigns 'new' to the pointer of *t, that is t. Both seem to be requiring only the single pointer to the head node to be assigned as 'new', yet only the first code works, and second doesn't actually modify the head node value.

What is the explanation for this to happen? Why doesn't the second code work in a similar way to the first?

Answer 1

Because everything in C is passed by value. So, if you need to assign a new value to an argument to a function, you must add a level of indirection. if you don't you simply receive a local copy, so any value assigned to that copy will be visible only within the function itself.

On a side note, don't cast the return value of malloc in C. It is unnecessary, clutters you code, and can hide an error for compilers which allow default int.

On.. another side note, instead of writing something like:

new_stack = malloc(sizeof(stack));

Use this instead:

new_stack = malloc(sizeof(*new_stack));

Now you don't have a problem if the type of new_stack ever changes.

Answer 2

In case of single pointer say

int addInBeginning(int *s)
{
 ... // add a node in the beginning of the linked list
}

int main()
{
 int *t;
 ... // make t point to a linked list say t ---> 1 -> 2 -> 3
 f(t);
}

Initially, s and t point to the same list. But when we add a node in the beginning, s points to the new node while t still points to the node it was earlier pointing to. When push returns, the new node is inaccessible from t.

0 -> 1 -> 2 -> 3
^    ^
|    |
s    t

In case of double pointer, s will point to t which in turn points to the list. So all pointer manipulations happen on the original pointer t.

s ----> t ----> 0 -> 1 -> 2 -> 3