One practical reason why pointer to pointers are conceived lies within its use in linked lists:
This is demonstrated in Nick Parlantes free online linked list tutorial where he prompts the reader to write a simple push function that pushes a node in a linked list:
Originally Posted by
Nick Parlante
Unfortunately Push() written in C suffers from a basic problem: what should be the
parameters to Push()? This is, unfortunately, a sticky area in C. There's a nice, obvious
way to write Push() which looks right but is wrong. Seeing exactly how it doesn't work
will provide an excuse for more practice with memory drawings, motivate the correct
solution, and just generally make you a better programmer....
Code:
void WrongPush(struct node* head, int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head;
head = newNode; // NO this line does not work!
}
void WrongPushTest() {
List head = BuildTwoThree();
WrongPush(head, 1); // try to push a 1 on front -- doesn't work
}
Originally Posted by
Nick Parlante
WrongPush() is very close to being correct. It takes the correct 3-Step Link In and puts it an almost correct context. The problem is all in the very last line where the 3-Step Link
In dictates that we change the head pointer to refer to the new node. What does the line head = newNode; do in WrongPush()? It sets a head pointer, but not the right one. It sets the variable named head local to WrongPush(). It does not in any way change the variable named head we really cared about which is back in the caller WrontPushTest().
We are bumping into a basic "feature" of the C language that changes to local parameters
are never reflected back in the caller's memory. This is a traditional tricky area of C
programming. We will present the traditional "reference parameter" solution to this
problem, but you may want to consult another C resource for further information.
We need Push() to be able to change some of the caller's memory — namely the head variable. The traditional method to allow a function to change its caller's memory is to pass a pointer to the caller's memory instead of a copy. So in C, to change an int in the caller, pass a int* instead. To change a struct fraction, pass a struct fraction* intead.
To change an X, pass an X*. So in this case, the value we want to change is struct node*, so we pass a struct node** instead. The two stars (**) are a little scary, but really it's just a straight application of the rule. It just happens that the value we want to change already has one star (*), so the parameter to change it has two (**).
Or put another way: the type of the head pointer is "pointer to a struct node." In order to change that pointer, we need to pass a pointer to it, which will be a "pointer to a pointer to a struct node".
Instead of defining WrongPush(struct node* head, int data); we define Push(struct node** headRef, int data);. The first form passes a copy of the head pointer. The second, correct form passes a pointer to the head pointer. The rule is: to modify caller memory, pass a pointer to that memory. The parameter has the word "ref" in it as a reminder that this is a "reference" (struct node**) pointer to the head pointer instead of an ordinary (struct node*) copy of the head pointer.
Originally Posted by
Nick Parlante
Here are Push() and PushTest() written correctly. The list is passed via a pointer to the head pointer. In the code, this amounts to use of '&' on the parameter in the caller and use of '*' on the parameter in the callee. Inside Push(), the pointer to the head pointer is named "headRef" instead of just "head" as a reminder that it is not just a simple head pointer..
Code:
/*
Takes a list and a data value.
Creates a new link with the given data and pushes
it onto the front of the list.
The list is not passed in by its head pointer.
Instead the list is passed in as a "reference" pointer
to the head pointer -- this allows us
to modify the caller's memory.
*/
void Push(struct node** headRef, int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = *headRef; // The '*' to dereferences back to the real head
*headRef = newNode; // ditto
}
void PushTest() {
struct node* head = BuildTwoThree();// suppose this returns the list {2, 3}
Push(&head, 1); // note the &
Push(&head, 13);
// head is now the list {13, 1, 2, 3}
}
