Struct and pointer to pointer

Question

I am learning about linked lists and how to create them in C with structs and pointers. I have an example below. From my understanding the called push() passes the beginning memory location of our struct where the head node lies as an argument. The parameter of our push() function takes a struct node as a pointer to pointer so it is passed as a reference, not an actual copy. So the first pointer of our struct node** headref is just a pointer to the memory location of our head node and the second pointer points to the value, which is the next memory location that the head node points to. We create a new node called newnode inside our struct node by assigning it some memory. We then create an int type data inside this node.

Okay assuming everything I said is correct, the next part is what i am confused on.

newNode->next= *headRef; 

This line from what i can understand dereferences the headref so this would just have the headref pointing to the head node. Then we have a pointer operation where what the headref is pointing to will then also be what our pointer next will be pointing to. Based on that the pointer next in our new node(newnode) will be pointing to the head pointer.

The next line which i am also confused on is:

*headRef = newNode;

What the dereferenced headref pointer is pointing to, which is the head node, will be pointing now to our newnode.

Based on that there should be a new node called newnode with an int data and a next pointer linking our newnode to the head. Then the headref pointer(or is it the head node?) will point to the new node. I know this isn't correct because the pointer next of our newnode should be pointing to the second node so our newnode can be linked in the struct. I also don't believe that i am understanding the pointer to pointer and dereferencing in the above two lines of code.

Code:

void Push(struct node** headRef, int data) {
  struct node* newNode = malloc(sizeof(struct node));

  newNode->data = data;
  newNode->next = *headRef;
  *headRef = newNode;
}

void PushTest(void) {
  struct node* head = BuildTwoThree(); // suppose this returns the list {2, 3}

  Push(&head, 1);
  Push(&head, 13);
  // head is now the list {13, 1, 2, 3} 
}

Answer 1

You are actually both correct and not correct at the same time. The push function adds a new node at the head of the list. After this function is called the new node is the new head, and the previous head node is now the second (next) node in the list. So your observations are correct, but your conclusion is not.

I recommend you step through the code in a debugger, while watching all pointers and their contents, to see what happens. It might make things clearer for you.

Answer 2

Ok. I think I can explain.

head is the head pointer of linked list. headRef points to head. So *headRef is head pointer(pass by reference).

so newNode->next will now point to head of the struct ( which has value 2, thats why the nodes are getting inserted at front).

Now in this line *headRef = newNode; *headRef is assigned the value of newNode so the head is now changed to newNode in the original structure.

Again when you pass &head, you are passing the head which contains value 1 now.

Answer 3

Let's copy this here, for simpler reference:

1   void Push(struct node** headRef, int data) {
2     struct node* newNode = malloc(sizeof(struct node));
3     newNode->data = data;
4     newNode->next = *headRef;
5     *headRef = newNode;
6   }

For the sake of simplicity, I numbered the lines.

Now, headRef itself is just a pointer to the variable that held the header of the list -- therefore, it contains no useful information by itself. By dereferencing that pointer, you're gaining access to the contents of the variable itself (head in PushTest()). Therefore, *headRef is essentially the way you get access to head. Now, since head is the top node, so is *headRef -- they hold the same value, since they are the same address. What line 4 does is, assign the value of *headRef (i.e., the value of head) to the new node's next link. In the same fashion, line 5 assigns the new node to *headRef, which is the same as assigning it to head, since headRef is a pointer to head -- meaning that *headRef is the value of head.

The key point here is, headRef is a reference (a pointer) to head, so *headRef and head are equivalents (scope rules aside).

Answer 4

void Push(struct node** headRef, int data) {

headRef contains an address of address where struct node is located. It is an address of the head variable in PushTest function.

struct node* newNode = malloc(sizeof(struct node));

Here we created a newNode. It contains an address of memory where node struct is located.

newNode->data = data;

set the data of newNode to the value of the data parameter passed into the Push function - OK.

newNode->next = *headRef;

set the newNode->next to the address of the structure located in the head variable. For example, if we have written

 void Push(struct node* head, int data) {
 ...
 newNode->next = head;

Next, we need to change the head variable to the newNode. If head variable was passed by reference, we could simply write this, like in C++:

void Push(struct node* &head, int data) {
...
head = newNode;

But in plain C we have to pass the address where head variable is located, so we can write into that address the pointer to the structure newNode we created in the Push function:

*headRef = newNode;

is equivalent to the write the newNode pointer to the variable whose address is located inside the headRef variable

And there is a problem in your logic:

The parameter of our push() function takes a struct node as a pointer to pointer so it is passed as a reference, not an actual copy.

Actually, we pass a copy of temporary variable that contains an address of node variable, not the reference. There is pass-by-reference method in C++, it uses ampersand to declare that the variable passed to function is a reference, not a copy of original variable.