I am looking at the following paragraph in the book "Programming Interviews Exposed" in reference to the implementation of a linked list stack in C:
typedef struct Element {
struct Element *next;
void *data;
} Element;
void push( Element *stack, void *data );
void *pop( Element *stack );
Now consider what will happen in these routines in terms of proper
functionality and error handling. Both operations change the first
element of the list. The calling routine’s stack pointer must be
modified to reflect this change, but any change you make to the
pointer that is passed to these functions won’t be propagated back to
the calling routine. You can solve this problem by having both
routines take a pointer to a pointer to the stack. This way, you can
change the calling routine’s pointer so that it continues to point at
the first element of the list. Implementing this change results in the
following:
void push( Element **stack, void *data );
void *pop( Element **stack);
Could someone explain, in different words, why we need to use a double pointer here? I'm a bit unsure about the explanation provided.
Ramy Al Zuhouri :
In C everything is passed by value, let's say that I have this function: \n\nvoid foo(void* ptr)\n{\n ptr=NULL;\n}\n\n\nIf you call this method in the main, the pointer that you pass will not be NULL (unless it wat already NULL).Because a copy of the pointer is made before passing it to the function.So if you want to modify it's value, you have to pass a double pointer: \n\nvoid foo(void** ptr)\n{\n *ptr=NULL;\n}\n\n\nThe same is valid for the stack, of which you want to modify the value.",
2012-11-05T21:19:48
aakash :
It is similar to the famous swap() function in C.\n\nCase 1:\n\nvoid swapFails(int x, int y) {\n int temp = x;\n x = y;\n y = temp;\n}\n\n\nCase 2:\n\nvoid swapOk(int *x, int *y) {\n int temp = *x;\n *x = *y;\n *y = temp;\n}\n\n\nand we invoke swap like this:\n\nint x = 10;\nint y = 20;\n\n\nCase 1:\n\nswapFails(x, y);\n\n\nCase 2:\n\nswapOk(&x, &y);\n\n\nRemember, we wanted to CHANGE the values of x and y. For CHANGING values of a datatype, we need pointers. Take this to the next level for pointers. For CHANGING values of a pointer, we would need double pointers.\n\nFor Stack using linked list:\nIf you push values 10, 20 and 30, they are stored like this:\n\ntop --- bottom\n30 -> 20 -> 10\n\n\nSo you see every time you push or pop values from the stack, which is a linked list, the top or the first node of the linked list changes. Hence you need double pointers.",
2012-11-05T21:26:26
iabdalkader :
The first version sends a copy of the pointer, if it's changed inside the function then the local copy would only be changed, when the function returns to the caller the caller still has a pointer to the old address. \n\nElement *stack =...\npush (stack)\nvoid push( Element *stack, void *data ) {\n stack = ... // this changes the local pointer allocated on the function's stack\n}\n//call returns\nstack //still points to old memory\n\n\nThe second version, however, passes a pointer to the stack pointer, so when that is changed, it changes the stack pointer in the calling function.",
2012-11-05T21:17:32