Modifying head pointer in a linked list

Question

I am having trouble understanding this code. All I really need is to modify the head pointer to point to the first element. So why won't *head work ? Changing the value of *head changes where this pointer points to and that should work, right ? I have read the pass by reference/pass by value, but am finding it hard to understand. Can someone help clarify this ? Appreciate your help. Thanks.

In C/C++ it’s easier to make mistakes with pointer misuse. Consider this C/C++ code for inserting an element at the front of a list:

bool insertInFront( IntElement *head, int data ){
  IntElement *newElem = new IntElement;
  if( !newElem ) return false;

  newElem->data = data;
  head = newElem; // Incorrect!
  return true;
}

The preceding code is incorrect because it only updates the local copy of the head pointer. The correct version passes in a pointer to the head pointer:

bool insertInFront( IntElement **head, int data ){
  IntElement *newElem = new IntElement;
  if( !newElem ) return false;

  newElen->data = data;
  *head = newElem; // Correctly updates head
  return true;
}

Answer 1

Its fairly simple when you get your head around what a pointer is. In the first code IntElement *head, head is a pointer to the existing head of the linked list. So the caller is passing in the address of the head element of the list. Changing the value of head in the insert-in-front function doesn't change ANYTHING back at the caller. The value of that address was passed to your function - not what was holding that address back at the caller.

You need to pass your function 'the address of the address of the head' - or IntElement **head. This will allow this function to modify the address held by the caller - i.e. update the linked list to point to the new head.

Answer 2

You need help understanding the difference right?

Imagine the caller of the function in the first case:

IntElement *head;
int data;
...
insertInFront (head, data);

Now, in this case, the address pointed to by head is placed on the stack and passed in as an argument to insertInFront. When insertInFront does head = newElement; only the argument (on the stack) is modified.

In the second case, the caller would be:

IntElement *head;
int data;
...
insertInFront (&head, data);

In this case, the address of head is placed on the stack and passed in as an argument to insertInFront. When you do *head = newElement, this passed in address is de-referenced to get the address of the original list head, and that is modified.