Linked Lists in C++

A linked list is a data structure made of individual pieces called nodes, where each node holds a value and a pointer to the next node in the sequence. Unlike arrays, a linked list does not store elements in contiguous memory — each element can live anywhere in memory, and the pointers connect them in order.

Think of a linked list like a treasure hunt. Each clue (node) tells you the answer (data) and where to find the next clue (pointer). You follow the chain until you reach the end.

Linked List vs Array

Array:
[10][20][30][40][50]  ← all in one block, fixed size

Linked List:
[10|→] → [20|→] → [30|→] → [40|→] → [50|NULL]
 Node1      Node2      Node3      Node4      Node5

Node Structure

Each node in a linked list contains two parts: the data it holds and a pointer to the next node.

struct Node {
    int data;      // the value stored
    Node* next;    // pointer to the next node
};

Building a Linked List Manually

#include <iostream>
using namespace std;

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

int main() {
    // Create 3 nodes
    Node* n1 = new Node();
    Node* n2 = new Node();
    Node* n3 = new Node();

    n1->data = 10;  n1->next = n2;
    n2->data = 20;  n2->next = n3;
    n3->data = 30;  n3->next = nullptr;

    // Traverse and print
    Node* current = n1;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;

    // Clean up
    delete n1; delete n2; delete n3;
    return 0;
}

Output:

10 20 30

Linked List Class with Operations

A proper linked list is managed through a class. The class keeps track of the head (first node) and provides methods to insert, delete, and display nodes.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}

    // Insert at front
    void insertFront(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    // Insert at end
    void insertEnd(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Delete a node by value
    void deleteNode(int val) {
        if (head == nullptr) return;
        if (head->data == val) {
            Node* toDelete = head;
            head = head->next;
            delete toDelete;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr && temp->next->data != val) {
            temp = temp->next;
        }
        if (temp->next != nullptr) {
            Node* toDelete = temp->next;
            temp->next = toDelete->next;
            delete toDelete;
        }
    }

    // Display the list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data;
            if (temp->next != nullptr) cout << " → ";
            temp = temp->next;
        }
        cout << " → NULL" << endl;
    }

    // Destructor to free all memory
    ~LinkedList() {
        Node* temp = head;
        while (temp != nullptr) {
            Node* next = temp->next;
            delete temp;
            temp = next;
        }
    }
};

int main() {
    LinkedList list;

    list.insertEnd(10);
    list.insertEnd(20);
    list.insertEnd(30);
    list.insertFront(5);
    list.display();

    list.deleteNode(20);
    list.display();

    return 0;
}

Output:

5 → 10 → 20 → 30 → NULL
5 → 10 → 30 → NULL

How insertFront Works

Before: HEAD → [10] → [20] → NULL
Insert 5 at front:
  newNode = [5]
  newNode→next = HEAD (points to 10)
  HEAD = newNode
After:  HEAD → [5] → [10] → [20] → NULL

How deleteNode Works

List: HEAD → [5] → [10] → [20] → NULL
Delete 10:
  Find node before 10 → that is node [5]
  Set [5]→next = [20]  (skip over [10])
  delete [10]
After: HEAD → [5] → [20] → NULL

Searching in a Linked List

bool search(int val) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == val) return true;
        temp = temp->next;
    }
    return false;
}

Types of Linked Lists

┌────────────────────┬───────────────────────────────────────────────┐
│ Type               │ Description                                   │
├────────────────────┼───────────────────────────────────────────────┤
│ Singly Linked      │ Each node points to the next node only        │
│ Doubly Linked      │ Each node points to next AND previous node    │
│ Circular Linked    │ Last node points back to the first node       │
└────────────────────┴───────────────────────────────────────────────┘

Doubly Linked Node:

struct DNode {
    int data;
    DNode* next;
    DNode* prev;   // extra pointer to previous node
};

Doubly Linked List Diagram:

NULL ← [5] ⇄ [10] ⇄ [20] ⇄ [30] → NULL

A doubly linked list lets you traverse in both forward and backward directions. It uses slightly more memory per node but makes certain operations (like delete) faster because you always know the previous node.

When to Use a Linked List

• You need frequent insertions or deletions at the beginning or middle.
• The size of your data changes unpredictably at runtime.
• You do not need random access by index (arrays are faster for that).
• You are building stacks, queues, or graphs using custom structures.

Key Takeaways

• A linked list is a chain of nodes where each node stores data and a pointer to the next node.
• It grows and shrinks dynamically unlike arrays with a fixed size.
• Inserting at the front is O(1); inserting at the end requires traversal (O(n)) unless a tail pointer is maintained.
• Always free dynamically allocated nodes to prevent memory leaks.
• Doubly linked lists allow traversal in both directions using two pointers per node.