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,

BTW: If a function returns `void` there is no need for the last line of it to be a `return;`. — Evan Teran, Jul 22 '10 at 20:42
You might need a [better book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — GManNickG, Jul 22 '10 at 20:45
@DeadMG: while that is good advice for the general case, this person is clearly looking to do this as a learning exercise. In which case using the "pre-done" solution is of no help. — Evan Teran, Jul 22 '10 at 21:07
Thanks all. As I mentioned in my tags, I was working with C++. Found the answer in the same book :) Is there any good online resource to learn all these differences between C and C++ ? — JohnH, Jul 23 '10 at 01:33
@John: They are two different languages. C++ started as an extension of C but that's really all that's left, some C hold-overs and syntax. Online resources for learning generally fail, you'll want a good C++ book from the page I linked above to learn C++ properly. (By the way, click the check mark next to an answer if you feel it solved your problem.) — GManNickG, Jul 23 '10 at 01:48

score 5 · Accepted Answer · answered Jul 22 '10 at 20:43

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.

Hey Thanks. I just figured that out :) And yea. Found the answer in the same book :) — JohnH, Jul 23 '10 at 01:29

score 2 · Answer 2 · answered Jul 22 '10 at 20:40

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...).

score 0 · Answer 3 · answered Jul 22 '10 at 20:43

0

In the first example, what you passed in still points to the "beginning" of the list.

In the second example, it points to the end of the list (which was the beginning when you started, but has since moved).

answered Jul 22 '10 at 20:43

corsiKa

81,495
25
153
204

score 0 · Answer 4 · answered Jul 22 '10 at 20:46

The reason for the double indirection is so nReverse can modify the caller's pointer, since after reversing the list, the head of the list is now a different node.

In the second version, you are modifying the copy of head that is local to the function, so the caller still has a reference to the old head node, which is now the tail.

score 0 · Answer 5 · answered Jul 22 '10 at 20:54

The reason for having double pointer passing (the first example) is that you want to change the head of the list. Since you are reversing the list, the head should point to the last element of the list after you have done the reversing.

digit* list; 
// initialize list
nReverse(&list); 
// now list is pointing to the last element of the chain (and not the first)

If you don't use double pointers, then list will still point to the original first element which next now points to NULL because its the last element after the reversing. So you loose all your other elements.

Linked list head double pointer passing

5 Answers5

Linked

Related