C++ Linked Lists

A linked list is a linear data structure made of individual objects called nodes, where each node stores a value and a pointer to the next node in the sequence. Unlike an array, a linked list does not need contiguous memory — nodes can live anywhere in the heap, connected only by pointers. This makes linked lists a foundational topic in C++: they teach you how pointers, dynamic memory (new/delete), and manual memory management actually work, and they underpin more advanced structures like stacks, queues, and graphs.

Overview / How Linked Lists Work

An array stores its elements in one contiguous block of memory, so the computer can jump straight to element i using simple arithmetic (base_address + i * sizeof(element)). A linked list gives up that contiguity in exchange for flexibility: each element is a separately allocated node, and the only way to reach the third node is to start at the first node and follow pointers one by one.

Each node typically contains two things: the data it holds, and a pointer (often named next) to the following node. The list itself is represented by a single pointer, usually called head, which points to the first node. The last node’s next pointer is set to nullptr, marking the end of the list. If head itself is nullptr, the list is empty.

Because nodes are scattered across the heap, insertion and deletion are cheap once you have a pointer to the right spot — you just rewire a couple of pointers, no shifting of elements required (unlike std::vector, where inserting in the middle shifts every element after it). The trade-off is that you lose random access: to reach the 1000th node you must walk through the 999 nodes before it, one pointer at a time, which is an O(n) operation instead of the O(1) array indexing you get with std::vector.

There are several variants of linked lists. A singly linked list (the focus of this lesson) has nodes that only point forward. A doubly linked list adds a prev pointer so you can walk backward too (this is essentially what std::list is, in the standard library). A circular linked list has its last node point back to the first instead of to nullptr. In production C++ code you will almost always reach for std::list or std::forward_list rather than writing your own — but understanding how to build one by hand is essential for learning pointers, for interviews, and for building custom structures later.

Syntax

A node is usually defined as a small struct holding a value and a pointer to the same type — this is called a self-referential structure:

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

Part	Meaning
data	The value stored in this node (can be any type)
Node* next	A pointer to the next node, or nullptr if this is the last node
new Node{...}	Allocates a node on the heap and returns a pointer to it
delete ptr	Frees the heap memory a node pointer refers to
ptr->field	Shorthand for (*ptr).field — accesses a member through a pointer

Building a list by hand means allocating nodes with new and linking them together by assigning to each node’s next pointer:

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};

Examples

Example 1: Building and traversing a simple list

#include <iostream>
using namespace std;

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

int main() {
    Node* head = new Node{10, nullptr};
    head->next = new Node{20, nullptr};
    head->next->next = new Node{30, nullptr};

    Node* current = head;
    while (current != nullptr) {
        cout << current->data;
        if (current->next != nullptr) cout << " -> ";
        current = current->next;
    }
    cout << endl;

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

Output:

10 -> 20 -> 30

Three nodes are allocated on the heap one at a time and wired together by setting each node’s next pointer. Traversal starts a temporary pointer current at head and follows next until it hits nullptr. At the end, a second loop walks the list again to delete every node — this is essential, because nothing frees heap memory automatically in C++.

Example 2: A LinkedList class with push_back and search

#include <iostream>
using namespace std;

class LinkedList {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };
    Node* head;
    Node* tail;

public:
    LinkedList() : head(nullptr), tail(nullptr) {}

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

    void push_back(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

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

    void print() const {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) cout << " -> ";
            current = current->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList list;
    list.push_back(5);
    list.push_back(15);
    list.push_back(25);
    list.push_back(35);

    list.print();

    cout << "Contains 15? " << (list.search(15) ? "yes" : "no") << endl;
    cout << "Contains 99? " << (list.search(99) ? "yes" : "no") << endl;

    return 0;
}

Output:

5 -> 15 -> 25 -> 35
Contains 15? yes
Contains 99? no

This is a much more realistic design: the Node type is hidden inside the class as a private implementation detail, a tail pointer is kept so push_back is O(1) instead of walking the whole list every time, and the destructor automatically frees every node when the LinkedList object goes out of scope. This is the Resource Acquisition Is Initialization (RAII) pattern — tying cleanup to an object’s lifetime so you never forget to free memory.

Example 3: Reversing a linked list

#include <iostream>
using namespace std;

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

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

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    cout << "Original: ";
    printList(head);

    head = reverse(head);

    cout << "Reversed: ";
    printList(head);

    while (head != nullptr) {
        Node* next = head->next;
        delete head;
        head = next;
    }
    return 0;
}

Output:

Original: 1 -> 2 -> 3 -> 4
Reversed: 4 -> 3 -> 2 -> 1

Reversal is the classic linked-list interview question because it forces you to juggle three pointers at once: prev (the node behind), current (the node being processed), and a saved nextNode (so you don’t lose the rest of the list once you overwrite current->next). Each iteration flips one pointer’s direction; by the time current reaches nullptr, prev is sitting on the new head.

How It Works Step by Step / Under the Hood

When you write new Node{10, nullptr}, the runtime asks the heap allocator for enough bytes to hold an int and a pointer (typically 16 bytes on a 64-bit system after padding), initializes those bytes, and hands back the address as a Node*. That address is a raw memory location — nothing ties it to any variable name. If you don’t store that pointer somewhere, the memory becomes unreachable and you have leaked it.

Traversal (current = current->next) is a pointer dereference followed by a copy: the CPU reads the 8 bytes stored at current‘s address (the value of the next field) and loads that address into current. Because each node can be anywhere in memory, this jump is not predictable the way array indexing is — the CPU cannot prefetch the next node ahead of time the way it can with contiguous array elements, which is one reason linked lists are slower in practice than arrays for pure iteration, despite having the same Big-O complexity.

Insertion at the head is O(1): allocate a node, point its next at the current head, then repoint head at the new node — three pointer operations, regardless of list size. Insertion at an arbitrary position requires first walking to that position (O(n)), then performing the same constant-time pointer rewiring. Deletion works the same way: find the node before the one you want to remove, splice it out by pointing its next around the removed node, then delete the removed node.

Common Mistakes

Mistake 1: Using a pointer after it has been deleted (dangling pointer)

delete frees the memory a pointer refers to, but it does not change the pointer’s value — the pointer still holds the old address. Dereferencing it afterward is undefined behavior: it might crash, might silently return garbage, or might appear to work by coincidence.

Node* head = new Node{1, nullptr};
delete head;
cout << head->data << endl; // UB: head is now a dangling pointer

The fix is to set the pointer to nullptr immediately after deleting it, and to always check for nullptr before dereferencing:

struct Node { int data; Node* next; };
Node* head = new Node{1, nullptr};
delete head;
head = nullptr;
if (head == nullptr) {
    cout << "head is null, safe" << endl;
}

Output:

head is null, safe

Mistake 2: Losing the only pointer to a node without deleting it (memory leak)

If you overwrite the last pointer that refers to a chain of nodes, that memory becomes permanently unreachable — the program can never free it again, and it stays allocated until the process exits.

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head = new Node{3, nullptr}; // the nodes holding 1 and 2 are now unreachable

Always walk and delete the existing chain before reassigning the pointer that owns it (or better, wrap the list in a class whose destructor does this automatically, as in Example 2):

struct Node { int data; Node* next; };
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};

Node* current = head;
while (current != nullptr) {
    Node* next = current->next;
    delete current;
    current = next;
}
head = new Node{3, nullptr};
cout << head->data << endl;
delete head;

Output:

3

Best Practices

• Prefer std::list (doubly linked) or std::forward_list (singly linked) from the standard library in real code — hand-rolled lists are for learning and interviews, not production.
• Wrap manual node management inside a class with a constructor, destructor, and (if you allow copying) a copy constructor, so cleanup is automatic and you avoid the “rule of three/five” pitfalls.
• Always set a pointer to nullptr right after calling delete on it, and check for nullptr before every dereference.
• Keep a tail pointer if you append frequently — it turns push_back from O(n) into O(1).
• When deleting an entire list, save next before calling delete on the current node — deleting first and then reading current->next is a use-after-free bug.
• Use a debugging tool like Valgrind or AddressSanitizer while developing linked-list code; pointer bugs are exactly the kind of error these tools are best at catching.

Practice Exercises

Exercise 1: Write a function int length(Node* head) that returns the number of nodes in a singly linked list without modifying it.

Exercise 2: Write a function void removeValue(Node*& head, int value) that removes the first node containing value from the list, correctly handling the case where the node to remove is the head, and freeing the removed node’s memory.

Exercise 3: Write a function bool hasCycle(Node* head) that detects whether a linked list contains a cycle (a node whose next chain eventually loops back on itself), using two pointers moving at different speeds (Floyd’s cycle detection, also called the “tortoise and hare” algorithm). Hint: move one pointer one step at a time and another two steps at a time; if they ever point to the same node, there’s a cycle.

Summary

• A linked list is a chain of heap-allocated nodes, each holding data and a pointer to the next node.
• Unlike arrays, linked lists don’t need contiguous memory, so insertion and deletion are O(1) once you have a pointer to the right spot — but random access is O(n).
• The list is accessed through a single head pointer; the last node’s next is nullptr.
• Every node allocated with new must eventually be freed with delete, or the memory leaks — wrapping the list in a class with a destructor automates this safely.
• Common bugs are dangling pointers (using memory after delete) and memory leaks (losing the only pointer to a node); both are avoided with disciplined pointer hygiene.
• In real C++ projects, use std::list or std::forward_list instead of writing your own, unless you have a specific reason not to.