Linked Lists

Before you start, try using this visualizer to understand how a linked list works.

Now let us learn in detail what a linked list is.

What is a linked list?

A linked list is a collection of nodes. Each node has two things:

• The data — the value you want to store
• A pointer — where the next node is

You create a node, and when you need another one you just create it and connect them together.

With arrays you need to decide the size at the beginning of the program. With a linked list you do not have to decide anything upfront. You just add a new node whenever you need one and the linked list keeps growing.

Now let us see how to create a linked list.

How to create a node

Give this visualizer a try before reading.

You know a node consists of two things — data and the address of the next node. For that let us use a struct to define it. A struct is just a way to group related variables together under one name.

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

data holds the value you want to store. next holds the address of the next node.

Now let us create a node:

Node* p = new Node;

new Node creates the node in memory and p holds the address of that node.

Now let us add data to it and set the next pointer:

p->data = 10;
p->next = nullptr;

p->data = 10 stores the value 10 in the node. p->next = nullptr means this node is not pointing to any next node yet. nullptr just means nothing.

Here is how creating a node looks:

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

Node* p = new Node;
p->data = 10;
p->next = nullptr;

Adding a node

Play around with this visualizer first.

We already know how to create a node. Let us create our first node:

Node* node1 = new Node;
node1->data = 10;
node1->next = nullptr;

Now let us create one more node:

Node* node2 = new Node;
node2->data = 20;
node2->next = nullptr;

Right now these two nodes exist in memory but they are not connected. To connect them we just store the address of node2 inside the next part of node1:

node1->next = node2;

Now node1 knows where node2 is. That is how you connect two nodes.

Here is how adding and connecting two nodes looks:

Node* node1 = new Node;
node1->data = 10;
node1->next = nullptr;

Node* node2 = new Node;
node2->data = 20;
node2->next = nullptr;

node1->next = node2;

Head and tail

Every linked list has a starting point. That starting point is called the head. The head is just a pointer that points to the first node in the list.

The last node in the list is called the tail. Since there is no node after the tail, its next is set to nullptr.

Node* head = node1;

head points to node1. node1 points to node2. node2 points to nullptr because it is the last node.

Traversing a linked list

Before we start, try this visualizer to see how traversal works.

Traversing means going through every node in the list one by one. You have to start from the head node and go through each node one by one until you reach the end.

To traverse we use a pointer called current and start it at the head:

Node* current = head;

Now we will print the current node:

cout << current->data << "\n";

And then current will move to the next node:

current = current->next;

We keep doing this until current does not point to anything, which means we have reached the end of the list:

while (current != nullptr) {
    cout << current->data << "\n";
    current = current->next;
}

Inserting a node

At the beginning

Play with this visualizer to see how inserting at the beginning works.

To insert a node at the beginning let us first create a new node:

Node* newNode = new Node;
newNode->data = 5;
newNode->next = nullptr;

Now we will add this to the beginning of the list. For that we simply make the new node point to the current head. This way the new node knows where the rest of the list is:

newNode->next = head;

Now since the first node has changed we just make head point to the new node:

head = newNode;

Here is how inserting at the beginning looks:

Node* newNode = new Node;
newNode->data = 5;
newNode->next = head;
head = newNode;

At a specific position

Try this visualizer before reading.

To insert a node at a specific position we first need to walk to the node just before where we want to insert. Let us say we want to insert after the second node.

First we create a new node:

Node* newNode = new Node;
newNode->data = 15;
newNode->next = nullptr;

Now we need to reach the second node. We are just traversing the list but stopping there:

Node* current = head;
for (int i = 0; i < 2; i++) {
    current = current->next;
}

Now current is at the second node. We first point newNode to current->next so the new node knows where the rest of the list is:

newNode->next = current->next;

Now we make current point to the new node:

current->next = newNode;

Here is how inserting at a specific position looks:

Node* newNode = new Node;
newNode->data = 15;
newNode->next = current->next;
current->next = newNode;

Removing a node

From the beginning

Give this visualizer a try before we start.

To remove the first node we just make head point to the second node:

head = head->next;

That is it. The first node is now disconnected from the list and head is pointing to the second node which is now the new first node.

From the end

Play around with this visualizer first.

To remove the last node we need to walk to the second last node and set its next to nullptr.

First we start at the head and walk until we reach the second last node:

Node* current = head;
while (current->next->next != nullptr) {
    current = current->next;
}

Now current is at the second last node. We just set its next to nullptr:

current->next = nullptr;

The last node is now disconnected from the list.

From a specific position

Try this visualizer to see how it works before reading.

To remove a node from a specific position we need to walk to the node just before it and make it skip over the node we want to remove.

Let us say we want to remove the third node. We first walk to the second node:

Node* current = head;
for (int i = 0; i < 2; i++) {
    current = current->next;
}

Now current is at the second node. We just make current point to the node after the one we want to remove:

current->next = current->next->next;

The third node is now disconnected from the list. Nobody is pointing to it anymore.

Complete linked list code

#include <iostream>
using namespace std;

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

void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void insertAtPosition(Node* head, int value, int position) {
    Node* newNode = new Node;
    newNode->data = value;
    Node* current = head;
    for (int i = 0; i < position - 1; i++) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
}

void removeFromBeginning(Node*& head) {
    head = head->next;
}

void removeFromEnd(Node* head) {
    Node* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    current->next = nullptr;
}

void removeFromPosition(Node* head, int position) {
    Node* current = head;
    for (int i = 0; i < position - 1; i++) {
        current = current->next;
    }
    current->next = current->next->next;
}

void traverse(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << "\n";
        current = current->next;
    }
}

int main() {
    Node* node1 = new Node;
    node1->data = 10;
    node1->next = nullptr;

    Node* node2 = new Node;
    node2->data = 20;
    node2->next = nullptr;

    Node* node3 = new Node;
    node3->data = 30;
    node3->next = nullptr;

    node1->next = node2;
    node2->next = node3;

    Node* head = node1;

    insertAtBeginning(head, 5);
    insertAtPosition(head, 15, 2);
    removeFromBeginning(head);
    removeFromEnd(head);
    removeFromPosition(head, 2);

    traverse(head);

    return 0;
}