Understanding linked list with C++?

Question

I get the idea of linked list being some kind of way of navigating through some kind of array/list/vector of sorts. I don't think i have the full idea of the concept. I've seen some charts explaining them but I don't seem to understand how they work. So I thought actually looking at the code might help. (My professor doesn't really go over the code that much)

I copied this code from some video.

#include<iostream>
using namespace std;

struct node
{
    int num;
    node *link;
}*p; // i'm not sure how this pointer was declared  

void main()
{
    node *root;

    root = new node;
    root -> num = 5;
    root -> link = p;
    p = root;

    node *q;
    for (q = p; q != NULL; q = q -> link) 
    {
        cout << q -> num << endl; 
    }
}

I guess I don't know what the -> operator does exactly. I know it has something to do with pointers and I'm not sure how that for loop is working.

If someone could take me through the code or if they may have a better example to show me and also if there is any more info that I should know please tell. It would be appreciated.

The best way to grasp what's going on in a linked list is to draw one. — user4581301, Mar 09 '16 at 06:08

score 3 · Accepted Answer · edited May 23 '17 at 12:31

I think the code is slightly incorrect (or maybe just bad style since it relies on the fact that the pointer is NULL after initialization) as is but I will try to explain this in detail.

Firstly the -> operator evaluates to a dereference followed by a dot ., so root->num is equivalent to (*root).num.

A linked list (in your case a singly linked list) is a structure like follows

NODE{1} --> NODE{3} --> NULL

Here a node is a struct object and has a pointer to another object. These objects together constitute the linked list. As you can see you need some sort of pointer to point to the first element in the linked list. In the example above that element would be the node with the 1 stored in it. This is the root pointer that you have in your code above.

The new is an allocation. You need to place the objects of your linked list somewhere in memory and the new operator helps you find some place in memory (particularly somewhere on the heap) you can store your object. And then it returns a pointer to this location. The best way to learn more about the heap is to research this online. This is an introductory concept (with a lot of "upper level" concepts at the implementation level but you do not have to worry about that at the moment) that is explained very well online. This will likely be better than reading my explanation so I will not explain more about the heap and the stack here. However I think the following links should be helpful

You also need to know where to stop in the linked list, i.e. you need to know which element is the last element. In the case above the last element is the node with the 3 in it. So this node will not point to another Node object but will rather point to NULL, 0 or the preferred nullptr in C++11 and C++14 (soon also C++17). So you could construct the linked list above with the following code.

#include <iostream>
using std::cout;
using std::endl;

struct Node {
    int element;
    Node* next;
};

int main() {
    Node* root = new Node;
    root->element = 1;
    root->next = new Node;
    root->next->element = 3;
    root->next->next = NULL;

    for (auto i = root; i != NULL; i = i->next) {
        cout << i->element << endl;
    }

    return 0;
}

Does that make sense?

This very helpful, but now I am remembering one of the things we went over. Like other ways of searching through list. — Ryan Henry, Mar 09 '16 at 06:39

Understanding linked list with C++?

1 Answers1