Linked Lists C++?

[christinetom]

Hi everyone.. :), me again.

I've never used Linked Lists.. They don't make sense to me.
I kind of understand them though. There's plently of online explanations explaining what they are but they all go down the same path.

I'm trying to undertstand how one Note (via the next pointer) points to the next node when after each node is declared dynamically. So I can't understand why when the second, third or fourth node is declared why it doesn't replace a noted already instantiated with the same name.

Intuitively I see it this way: The 'HEAD' pointer points to the first node. The 'NEXT' pointer in the first node points to the second node (which is instantiated dynamically). For one, why is it that when this second node is instantiated it does not totally overwrite the first node? Secondly.. Does the 'NEXT' pointer in the first node point just to a memory location of the second node.. and so on... which I assume is why the 'HEAD' pointer is the starting point and the only identifiable pointer to access the linked list.

Intuitevly.. I would think that there would have to be some form of increment to identify each node so this is where I'm getting confused.

Thanks..

[Ancient Dragon]

For one, why is it that when this second node is instantiated it does not totally overwrite the first node?

Because they are in different memory locations. It's somewhat the same concept as declaring simple variables inside a function

void foo()
{
   int x; // one variable
   int z; // another variable
}

In the above example x and z are completely different variables with occupy different memory locations.

void foo()
{
   int* x = new int;
   int* z = new int;
}

The above example is almost the same as the first except the integers are allocated dynamically, each integer has a different memory location so tha one does not overwrite the other

struct node
{
    struct node* next;
}

void foo()
{
    int* head = NULL;

    struct node* newnode;
    newnode = new struct node; // allocate a node
    head = newnode; // save address in head
    newnode = new struct node; // allocate another node
    nead->next = newnode; // save it's memory location
    newnode = new struct node; // allocate another node
    nead->next->next = newnode; // save it's memory location
}

The above code allocates new memory for each node then saves those locations in the head node. After the address of the new node is stored in head we can throw away the address contained in newnode as it is no longer needed. Yes, the address in newnode is overwritten each time and that is why we have to save it somewhere else before allocating another node.

[Ancient Dragon]

Secondly.. Does the 'NEXT' pointer in the first node point just to a memory location of the second node

Yes, exactly right.

Intuitevly.. I would think that there would have to be some form of increment to identify each node

Yes, you have to create one so that the program can iterate through all the nodes

void foo(struct node* head)
{
    struct node* iterator; 

    iterator = head;
    while( iterator != NULL)
    {
        // do something

        iterator = iterator->next; // point to the next node
    }
}

[deceptikon]

Each node is just an anonymous variable that the pointer points to. It seems like your confusion is more about self-referential structures than anything. So let's take a look at a simple linked list:

#include <iostream>

struct node {
    int data;
    node *next;

    node(int data, node *next = nullptr): data(data), next(next) {}
};

int main()
{
    node *head = nullptr;

    for (int i = 0; i < 5; i++) {
        head = new node(i, head);
    }

    for (node *x = head; x != nullptr; x = x->next)  {
        std::cout << x->data << '\n';
    }
}

Your question is about why all of those next pointers don't overwrite each other, but conceptually the list looks like this if you unroll the loop and name each anonymous variable:

#include <iostream>

struct node {
    int data;
    node *next;

    node(int data, node *next = nullptr): data(data), next(next) {}
};

int main()
{
    node *head = nullptr;
    node a{0}, b{1}, c{2}, d{3}, e{4};

    head = &e;
    e.next = &d;
    d.next = &c;
    c.next = &b;
    b.next = &a;

    for (node *x = head; x != nullptr; x = x->next)  {
        std::cout << x->data << '\n';
    }
}

Each pointer points to a unique entity in both cases, the first case simply hides that from you by using anonymous objects versus named variables.

[christinetom]

Yup.. thanks for that. I get it now.
For some reason these have been difficult to understand but I get it now.