C++ passing pointers by Refrence or Value

Question

Consider this code :

#include <iostream>
using namespace std;

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

void append(Node* h1, Node* h2)
{

    cout << h1 << ":" << h2;
    cout << endl;

    Node *ptr;
    ptr = h1;

    while ( ptr->next != NULL)
    {
        ptr = ptr->next;
    }

    ptr->next = h2;
}

void insertAtHead(Node* head, int k)
{

    Node *tmp = new Node;
    tmp -> x = k;
    tmp -> next = head;

    head = tmp; 
}

int main()
{
    Node *n1  = new Node;
    n1->x = 1;
    n1->next = NULL; 


    Node *n2  = new Node;
    n2->x = 2;
    n2->next = NULL;

    Node *n3  = new Node;
    n3->x = 3;
    n3->next = n2;

    cout << n1 << ":" << n3;
    cout << endl;

    append(n1,n3);

    insertAtHead(n1,4);

    while(n1 != NULL)
    {
        cout << n1->x;
        n1 = n1->next;
    }
    cout << endl;
}

The append function works even if we have Node* h1 but insertAtHead does not work even though we have the same Node* head. Why??

We need Node* &head for appendAtHead to work. Why?

Answer 1

In function append pointer h1 is not changed

In function insertAtHead head should be changed but instead of that a local variableis changed. You should take into account that parameters are local variables of the function. So after exiting the function all local variables are destroyed.

You could get the same effect if function append deal with an empty list. In this case you had to allocate the head inside the function and these changes of head would not influence the original head.

There are three approaches to write these functions correctly. Either each function returns updated head or the head must be passed either by reference or indirectly by pointer to head.

Consider for example how function append would work if the list was empty i.e. when the first argument is equal to NULL.

void append(Node* h1, Node* h2)
{

    cout << h1 << ":" << h2;
    cout << endl;

    if ( h1 == NULL ) 
    {
        h1 = h2;
    }
    else
    {
        Node *ptr = h1;

        while ( ptr->next != NULL) ptr = ptr->next; 

        ptr->next = h2;
   }
}

As you see in this case it would have the same error as function insertAtHead. Changes of h1 inside the function would not influence the original value of head. Only local variable h1 would be changed and after that destroyed after exiting the function. Original variable head would keep the same old value as before.

Answer 2

Passing by value means that the function will create a copy of the parameter so it will not change the actual parameter that was passed while passing by reference will let you modify the parameters within the function. Knowing this, it is the reason why Node* &head will work but Node* head won't work for your insertAtHead() function.

For the append() function it is being modified because a Node* ptr variable is pointing to the address of h1, which is letting you set the next value to be h2 (parameter set to n3) without having to set the parameter to pass by reference. Before n1 reached the append function, it had next node set to NULL, while after the append function was called, it now has the next node set to n3. (IMO I think you should give them different names, it gets kind of confusing to see n1, h1, n2, h2, etc...)

Answer 3

The reason is simple :

In the case void insertAtHead(Node* head, int k), as you pass head by value, you're working on a copy of the actual head, copy existing on the stack, so it gets discarded when exiting the function.

That is why you must pass by reference, so head is not a copy of your node on the stack, but the actual node you want to act upon.

Edit to answer your comment:

append works because you're getting a copy of the pointer, so you can modify the subjacent data it points to, but you can't change the actual pointer you got, as it is a transient copy living on the stack.

Answer 4

Pointers are passed by value (you pass a copy of the value of the pointer - i.e. a copy of the memory address pointed to).

References are passed by reference (i.e. when a function parameter has an &prefix in the function signature). In this case if you make the reference point to something else inside the function, the original reference is also pointing to that other thing when program flow exits the function scope and returns.

Here's an illustration of the difference for Java (using C++ as an example of being able to pass by reference which Java can't do):

http://blog.aaronshaw.net/2014/02/13/java-is-always-pass-by-value/