Linked Lists in C++

Linked Lists

Linked lists can be quite a brain-twister when encountered first, especially if described in plain language. In programming, when going into higher levels of complexity, it is essential to be able to visualize concepts - blocks of memory, pointers pointing to them, dereferencing them etc. I decided to make a quick tutorial on linked lists, first in plain old English, then step by step with pictures.

Linked Lists are a way of linking structures between each other, each structure having in it a pointer to the next one. Thus, by linking blocks of memory through pointers, each individual struct can be accessed.

There are two pointers in use, one is always at the beginning of the linked list, the head (or root), so points to the first node and is used to iterate (traverse is the right term here) the linked list by being assigned to the pointer in the struct (which holds the next struct) until the last struct, until NULL, (since the last struct points to NULL). This pointer can access all the attributes of the struct it currently points two.

The second pointer is used to dynamically allocate memory for a new struct. While doing so, the pointer in this struct is set to point to the head of the list, the first node, (at this point two pointers are pointing to the first node), while the head pointer is assigned to this new node, so it is at the beginning again, while the pointer from the new struct is now pointing to the struct that was previously pointed to by head, thus completing the link. Essentially, it is what the push_front() method of a vector does.

So, remember:

Two pointers:

• One is the head and always points to the first element of the linked list
• The second is used to allocate new memory

Here a simple program that lets you add nodes to a linked list:

#include <iostream>



using namespace std;



struct Node //new struct

{

    string name;

    Node *next_node; //stores position to nex node

};



Node* Add_Node(Node* head, string name); //Add_node, return type Node pointer, takes the current head



int main()

{

    int choice;

    string name;



    Node* head = NULL; //head, currently pointing to NULL



    while (true)

    {

        cout << "Add person(1), exit (0): ";

        cin >> choice;

        cout << endl;



        if (choice)

        {

            cout << "Enter name: ";

            cin.ignore();

            getline(cin,name);

            cout << endl;



            head = Add_Node(head,name); //Add_node returns the new head, the new first node



        } else return 0;

    }

}



Node* Add_Node(Node* head,string name)

{

    Node* new_node = new Node; //create a new pointer and get memory for a new struct

    new_node->name = name; //since we are using a pointer, the . becomes a ->

    new_node->next_node = head; //assign the next_node pointer to the current head



    return new_node; //return the new_node as the new head

}

Here the important part:

Node* Add_Node(Node* head,string name)

{

    Node* new_node = new Node; //create a new pointer and get memory for a new struct

    new_node->name = name; //since we are using a pointer, the . becomes a ->

    new_node->next_node = head; //assign the next_node pointer to the current head



    return new_node; //return the new_node as the new head

}

So, inside this function, we first create a new node, a new struct. Then, we set the name attribute of that struct to the passed name and set the next_node attribute to the current first element of the linked list, the head. At this point both the head pointer and the pointer in this new struct are pointing to the first element of the list, none of them though are pointing to this struct. So, we return this node and it becomes the new head in the main function, thus we have completed the link: Head -> Node1.next_node-> NULL. If we add another, it will be pushed before the first node: Head -> Node2.next_node -> Node1.next_node-> NULL.

Visualize it: 

1) Two unused pointers of type Node. Head needs to point to NULL, new_node can in fact stay uninitialized.

2) Then, new_node is assigned to a new struct. I am leaving out name here since it's not really relevant.

3) new_node->next_node is assigned to Head, so NULL and new_node is returned, so assigned to Head.
    Both pointers are at this point pointing to the new Node.

4) Round 2: new_node goes and grabs a new struct. Below you can see the linked up list.

4) new_node->next_node, so the pointer inside the new struct, is assigned to head again. Sorry for the weird line, I had limited space. Also, Head is assigned to the new node by returning new_node to Head (in the  main function).

5) The linked list nicely lined up:

So, as you can see here, each time a new node is created, it's pointer is linked up on the right with the next node, which is pushed to the right, and linked up with Head on the left side. As mentioned earlier, this is like the push_front method from STL vectors.

Finally, you may wonder how to iterate over these nodes. Quite simply, you just assign head to the pointer in the current struct, which points to the next struct, thus moving along, while head is not NULL, indicating that the linked list is over.

In Code, display all names of the previous list:

void Display(Node* head)
{
    while (head != NULL)
    {
        cout << head->name << endl;
        head = head->next_node;
    }
}

Horrendously simple!

That's it for this post. Thanks for reading!