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}
}
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.