Pointer to a pointer as an argument for functions that manipulate linked lists

Question

I'm trying to brush up on my C and have been reviewing data structures and pointer manipulation. Can someone please explain to me why it is necessary to use a pointer to a pointer for head in this linked list reverse function? Since head is always dereferenced once (*head) in the function, couldn't we just accept a normal Node* as an argument to this function and forgo the dereferencing? Thanks in advance!

struct Node{
    int key;
    struct Node *next;
};



struct Node* reverse(struct Node** head){
    Node *parent = *head;
    Node *me = parent->next;
    Node *child = me->next;

    parent->next = NULL;
    while(child) {
        me->next = parent;
        parent = me;
        me = child;
        child = child->next;
    }
    me->next = parent;
    *head = me;
    return *head;
}

@Manu343726 The concept is still perfectly valid for C++ . I don't think you should have removed the C++ tag as the OP clearly stated he is working on C++ — mathematician1975
– mathematician1975, Commented Feb 14, 2014 at 17:50

mathematician1975 · Accepted Answer · 2014-02-14 17:56:52Z

1

If you did not pass in a Node** argument and just used a Node* argument, then this line

 *head = me;

would need to be implemented as

 head = me;

But as head would then be passed by value this results in a copy of head being passed to the function. Then modification your function makea would ONLY apply to this copy and NOT the argument you pass.

Whenever you need a function to modify an argument you need to pass it by reference or via a pointer. In your case you need Node** to modify the Node* that it points to.

You could also use a reference to a Node* argument.

As a ridiculous example consider this function

void ChangePointer(int* x)
{
    x = NULL;
}

void ChangePointer_2(int** x)
{
    *x = NULL;
}

int main()
{
    int* p = new int(1);
    ChangePointer(p); 
    // p is not NULL. The function changed the copy
    // of p because it was passed by value.

    ChangePointer_2(&p);
    // now p == NULL;
}

edited Feb 14, 2014 at 17:56

answered Feb 14, 2014 at 17:19

mathematician1975

21.3k6 gold badges65 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

MRT89 Over a year ago

First, I believe you, and I know this to be true, but I'm just trying to understand properly. So, if i used Node* as an argument, the pointer to the node would be passed by value... Since this is still a pointer, why wouldn't changes in the function affect the actual argument passed in?

mathematician1975 Over a year ago

@MRT89 You could change things that the pointer points to via dereferencing, but not the value of the pointer itself (ie its address). Code up a function that takes a pointer argument (by value), and try setting it to NULL. When you examine the address of the argument that you passed once the function has returned, it will not be NULL. You changed the value of the copy, not the pointer itself.

mathematician1975 Over a year ago

@MRT89 I have added an example that I hope better illustrates what I am trying to say.

Collectives™ on Stack Overflow

Pointer to a pointer as an argument for functions that manipulate linked lists

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related