Why use a pointer to a pointer to the stack when creating a push function?

Question

I am looking at a textbook example of a linked list that implements a stack. I don't understand why using a pointer to a pointer to the stack is necessary for the push operation. See the following example:

bool push( Element **stack, void *data)
{
    Element *elem = new Element;
    if(!elem) return false;

    elem->data = data;
    elem->next = *stack;
    *stack = elem;
    return true;
}

If anyone can help clarify why the first parameter of the push method is a pointer to a pointer, I would greatly appreciate it. Thanks.

Amazing, thank you for all of the excellent help.

Answer 1

The function needs to modify the value of the Element pointer, so it needs a pointer to that pointer.

Put it another way: a function takes a pointer of something when it needs to modify that thing.

In this case, that something is a pointer itself. So the function ends up taking a pointer to a pointer.

Answer 2

You'll have to update a pointer.

A list is nothing but a pointer to an Element. So you may rewrite this to

bool push(List* stack, void* data);

Not you see that, in case you wouldn't use the double pointer, your actual declaration was

bool push(List stack, void* data);

which wouldn't change the original list at all.

But alternately,

bool push(Element* &stack, ...)

is OK too since it allows you updates.

Answer 3

A pointer is simply a variable that holds a value, that value is a memory address.

A pointer to a pointer is also simply a variable that holds a value. That value is the memory address of a pointer.

You use a pointer to a pointer when you want to change the value of a pointer.

//Not a very useful example, but shows what I mean...
void getOffsetBy3Pointer(const char *pInput, char **pOutput)
{
  *pOutput = pInput + 3;
}

And you call this function like so:

const char *p = "hi you";
char *pYou;
getOffsetBy3Pointer(p, &pYou);
assert(!stricmp(pYou, "you"));

---

Now consider what would happen if we tried to implement this function with a single pointer.

//Note: This is completely wrong
void BadGetOffsetBy3Pointer(const char *pInput, char *pOutput)
{
  //*pOutput refers to the first actual char element that pOutput points to.
  pOutput = pInput + 3;
  //pOutput now points to pInput + 3, but the variable we passed in remains distinct.
}

And you call this function like so:

const char *p = "hi you";
char *pYou = NULL;
BadGetOffsetBy3Pointer(p, pYou);
assert(pYou == NULL);

Note in the BadGetOffsetBy3Pointer, we could have changed some of the characters, but we couldn't change what pYou points to.

Answer 4

The stack is represented by a pointer to the last element that was pushed onto it. In order to change the stack by pushing an element onto it, this pointer must be updated, so we pass a pointer to it to the push function.

Answer 5

Look at how someone would use this push function:

Data d1, d2;

Stack *s = null; // s := null
push(&s, &d1); // s := {d1}->null
push(&s, &d2); // s:= {d2}->{d1}->null

Now you can continue to use the variable s, which has been modified by push to point to the top of the growing stack.

In a stack, you always want to maintain a pointer to the top, and the push function makes it easier to maintain this pointer.

Answer 6

A stack is basically a linked list of pointers. Each one pointing to the one below it. Because you have a new element and you want that element to come first in your list (hence the term "stack", you have to change what points to the start of your list.

To change the value in the "pointer to the head of the list", you need the Address of that pointer.

Answer 7

Because of this line:

    *stack = elem;

Basically you are modifying the original pointer inside the function.