Linked list head double pointer passing

Question

I have seen this in some book/ tutorial.

When you pass in the head pointer (of linked list) into a function, you need to pass it as a double pointer.

For eg: // This is to reverse a linked list where head points to first node.

void nReverse(digit **head)
{
    digit *prev=NULL;
    digit *curr=*head;
    digit *next;

    while(curr!=NULL)
    {
        next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    *head=prev;
    return;
}

This works fine.

It also works when I use single pointer like,

void nReverse(digit *head)
{
    digit *prev=NULL;
    digit *curr=head;
    digit *next;

    while(curr!=NULL)
    {
        next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    head=prev;
    return;
}

I tried printing the list by using the head pointer. Both the functions work fine.

Am I missing something ?

Thanks,

Answer 1

This is very C-like code, not C++.

Basically, when something is passed by-value the function operates on a copy of the data:

void foo(int i)
{
    i = 5; // copy is set to 5
}

int x = 7;
foo(x);
// x is still 7

In C, you instead pass a pointer to the variable, and can change it that way:

void foo(int* i)
{
    *i = 5; // whatever i points to is set to 5
}

int x = 7;
foo(&x);
// x is 5

For you, instead of an int it's a digit*. (Resulting in a pointer to pointer.)

---

In C++, references were introduced. A reference is an alias to another object. So you'd do something like this:

void foo(int& i) // i is an alias to another value
{
    i = 5; // x is set to 5
}

int x = 7;
foo(x); // pass x as alias, not address of x.
// x is 5

A reference is generally preferred, since it enforces that you actually refer to an object, and simplifies both calling and operating code.

Of course in C++ you wouldn't implement a list yourself, you'd use std::list.

Answer 2

That last head=prev; does not change the passed pointer's value in the second example. Whether or not that line is necessary for the purposes of this function is up to you. But there is a difference.

How did you test that it "worked fine"? Were you able to iterate the list and print out the node's values and see that they had in fact been reversed? The first function (presumably called like nReverse(&list); changes what list points to, the second do not (so for the second how do you know which node is the beginning of the list, after all it was just changed...).