CODEWITHSUNDEEP
c++linked-list
Danny Rancher
Danny Rancher

Reputation: 2005

Confusion with pointers whilst inserting to the head of a linked list

I'm working through a linked list example. However, I currently cannot understand the head_insert method. Please would someone explain it a little further. Thank you.

#include <iostream>
using namespace std;

struct node_ll
{
    int payload;
    node_ll* next;  // pointer to the next node
};

void head_insert(node_ll** list, int pload)
{
    node_ll* temp = new node_ll;//Declare temp, a pointer to a node.
    temp->payload = pload;//Set the payload of the struct at the address of temp to pload.
    temp->next = *list;//Set the next of the struct at the address of temp to the pointer to the old head of the list.
    *list = temp;//Set the pointer to the old head of the list to the pointer to the temp node.
    //Why doesnt the temp->next = temp?
};

void print_ll(node_ll** list)
{
    node_ll* temp;
    temp = *list;
    while (temp) // != NULL
    {
        cout << temp->payload << '\n';
        temp = temp->next;
    };
}

int main()
{
    node_ll* alist = NULL;  
    cout << "Empty list a to start\n";
    head_insert(&alist, 2); 
    head_insert(&alist, 4);
    head_insert(&alist, 6);
    cout << "List a after head insertion of 2,4,6 is \n";
    print_ll(&alist);
    cout << '\n';
    system("PAUSE");
    return 0;
}

My confusion is detailed in the comments. If I have the lines

temp->next = *list;
*list = temp;

why doesn't my newly created node point to its own address in next?

Upvotes: 0

Views: 563

Answers (3)

999k
999k

Reputation: 6565

In your head_insert function new Node is added to the beginning. ie new new node will be the head of your linked list

temp->next = *list;//Store pointer to earlier head as the next node
*list = temp;  // Make pointer new node as the head node

In your Code a double pointer is passed as argument into the function. ie if A is your pointer header node then an address B which contains A is passed as argument into your function.

Upvotes: 0

Karl Knechtel
Karl Knechtel

Reputation: 61509

//Declare temp, a pointer to a node.

No. "Create a new node, and let temp be the address of that node."

//Set the payload of the struct at the address of temp to pload.

No. "Set the payload of the struct whose address is temp to pload". That's probably what you meant, but you really need to be precise about these things. Anyway, this is filling in the payload of the new node that we just created.

//Set the next of the struct at the address of temp to the pointer to the old head of the list.

Similarly... "Set the next of the struct whose address is temp to the address of the old head of the list."

//Set the pointer to the old head of the list to the pointer to the temp node.

Careful. Here's the thing: "the address of the old head of the list" is a value, not a variable. It can exist at multiple places in memory, in the same way that the number 4 can be stored at multiple places in memory.

The function was given a node_ll**, i.e. a (node_ll*)* - a pointer to a node_ll*. Specifically, when we called the function from main, we gave it a pointer to the variable a_list in the current call to main.

Thus, when we do *list =, we are writing to that memory location - in effect, replacing the a_list variable. Playing with memory addresses like this allows us to simulate "pass by reference" and change the value of variables that come from the caller (we can't just access these from the parameters, because we were given a copy; and we can't access them as globals because they aren't globals).

//Why doesnt the temp->next = temp?

Why would it? Code runs from top to bottom (control structures notwithstanding). temp->next was set to the old head of the list, before we set the new head of the list.

It seems like you expected temp->next to change simply because, at that point in the process, it happened to point to the old head of the list, and then we changed a variable that also happened to have the same value - i.e., to point to the old head of the list. But they are quite clearly separate variables. If I write a = 4; a *= 3, the value 4 does not change; the variable a does. So it is with pointers, as well; they're just another kind of value.

Upvotes: 1

Collin Dauphinee
Collin Dauphinee

Reputation: 13973

This is confusing code.

list is a pointer to a pointer to a node. *list = temp is not changing any nodes, it's changing the pointer that was passed in, so it points to the inserted node.

Upvotes: 0

Related Questions