Changing Node passed to a function as argument

If a function in C/C++ takes a pointer argument and we try to change it (Not the value pointed to by pointer but the pointer itself). It should be done with caution to avoid undesired results ... Lets take an example of the function to insert an element in a linked list which is maintained in the sorted order. The structure of the Node is as shown below:

    struct Node
    {
        /* Keeping all public for simplicity reason, Not a good practice */
        public:
            int data;
            Node * link;
            Node(int value):data(value),  link(NULL) { }
            /* Good practice to initialize in the Member initialization list*/
    };

The insert function takes two arguments, The head of the list in which we want to insert and the value to be inserted. The below function is an INCORRECT IMPLEMENTATION of insert function.

    /* Function to insert a value in a sorted linked list.*/
    void  insert(Node *head, int value)
    {
        /* Creating new node with the value */
        Node* temp = new Node(value);
        if(head == NULL || head->data > value)
        {
            /* If no element in the list or the first element is larger than value */
            temp->link = head;
            /* Update the local variable ‘head' and not the actual argument */
            head = temp;
        }
        else
        {
            /* Loop to find the position to insert */
            while(head->link != NULL && head->link->data < value)
            {
                head = head->link;
            }
            /* inserting new node after head. */
            temp->link = head->link;
            head->link = temp;
        }
    }

If you have ever implemented linked list in C/C++ (on your own ) you may have found the problem in the above function. The above function does not ever update the pointer with which it is called, In fact it cannot update the actual argument because of the way argument is passed (i.e pass-by-value). Consider the below sequence of calls to this function:

    Node * list = NULL;
    list.insert(5);
    list.insert(7);
    list.insert(1);

We may expect variable list to point to a link list like below:

  But Computers are not intelligent enough to interpret our expectations. They can only interpret our code. In the Function we are updating the head pointer which is a local variable to the function. This does not update the actual argument of the calling function, which is list. So if we are attempting to modify the actual argument, which we do in two cases:

1. When the list is empty, then we create the first node and assign its address to the head.
2. If the element being inserted is the smallest in the list, then we insert it at the start of the list and update the head pointer.

Then our code will not behave in the desired way. In all other cases (where we are not modifying the head, the above function should works fine). Just to reiterate, If list is pointing to a valid memory and head is changing the content of that memory, then the change would have been reflected in the *list (value pointed to by list). But, If we make change to head and expect the list variable to change itself (and not the value-at-list), then we need to do it differently. Because, like other variable, a pointer variable is also passed-by-value. Below picture shows what happens when we change the value pointed to by a pointer in the called function. And below is the picture showing what happens when we change the pointer itself. Hence, we can change the value pointed to by a pointer inside the called function, but not the pointer itself. (At least, not the way we are doing it in the above example). Next: Solution to the problem ... Solution to the problem: If we want to change the actual pointer argument in the called function, then there are proper ways to do that.

In C++, there is a concept of reference variables, A reference variable is actually an alias of the original variable. We can modify the insert function to receive a reference to pointer variable. In which case head is not allocated a separate memory, but it will only be another name for the memory of list. So if we changehead, list gets changed.

    void insert(Node * & head, int value)
    {
        ... ...

In C language, there is no concept of reference, (In fact, pass-by-address is mistakenly used by some authors as pass-by-reference). So if we want the called function to be able to change a pointer we will have to pass a pointer to that pointer.

    void insert(Node ** head, int value)
    {
        ... ...

this will require us to use one more level of dereferencing in the above function in case of C language, but that's how it can be implemented.

If we don't want a function to change the pointer itself then we can declare the pointer variable (the formal argument in the called function) as a constant pointer, like below:

    void insert(Node *const head, int value);

Note that the above declaration (Node * const head) is different from

    const Node* head

The above indicates that the value pointed to be head is constant, and does not say that head itself is constant.