Linked lists

A linked list stores each element in its own heap node, chained by pointers. It gives up random access and cache-friendliness in exchange for two things a vector can't do: elements never move (pointers to them stay valid forever), and any node can be unlinked or relinked in O(1) — including whole ranges spliced between lists without copying.

1. Singly vs doubly linked

A singly linked list (std::forward_list) can only go forwards. To remove a node you need its predecessor (to re-point its next), which is why forward_list has insert_after / erase_after instead of insert / erase. A doubly linked list (std::list) stores prev too, so given an iterator to a node you can remove it in O(1) and walk both ways — for two extra pointers per node.

2. The sentinel: delete the edge cases

With null-terminated ends, every operation has special cases: inserting into an empty list, at the front (update head), at the back (update tail), erasing the only element. Each is a branch, and each branch is a place for a bug.

Instead, add one extra node — the sentinel — that sits between the last element and the first, turning the list into a ring:

The empty list is the sentinel pointing at itself. Now every real node always has a real prev and next, and insert/erase have no branches:

#include <cassert>
#include <print>

struct Node {
    Node* prev;
    Node* next;
    int value;
};

void link_before(Node* pos, Node* n) {   // insert n in front of pos
    n->prev = pos->prev;
    n->next = pos;
    pos->prev->next = n;
    pos->prev = n;
}

void unlink(Node* n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

int main() {
    Node sentinel{&sentinel, &sentinel, 0};    // empty list
    Node a{nullptr, nullptr, 1}, b{nullptr, nullptr, 2}, c{nullptr, nullptr, 3};
    link_before(&sentinel, &a);                // push_back: insert before end()
    link_before(&sentinel, &c);
    link_before(&c, &b);                       // insert in the middle — same code
    unlink(&a);                                // erase the first — same code
    for (Node* p = sentinel.next; p != &sentinel; p = p->next) std::print("{} ", p->value);
    std::println();
    assert(sentinel.prev == &c && c.next == &sentinel);
}

end() is simply an iterator to the sentinel, so --end() reaches the last element with no special case either. One detail for a generic List<T>: if the sentinel were a Node holding a T, every list would need to construct a dummy T — impossible if T has no default constructor. Split the node into NodeBase {prev, next} and Node : NodeBase {T value}, and make the sentinel a plain NodeBase.

3. Ownership: who deletes the nodes?

Two common designs:

• Raw pointers + an owning container: nodes are linked with raw pointers, and the List destructor walks and deletes them. Simple and fast; the container class is the one owner.
• std::unique_ptr<Node> next: each node owns the next. It looks self-managing — but destroying the head destroys its next, which destroys its next… a recursion one stack frame per node.

#include <memory>
#include <print>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int i = 0; i < 1000; ++i) head = std::make_unique<Node>(i, std::move(head));
    // Fine for 1,000 nodes. For a few million, ~Node recursing through
    // next would overflow the stack. The fix is an iterative teardown:
    while (head) head = std::move(head->next);
    std::println("destroyed iteratively");
}

The loop works because each assignment destroys exactly one node (the old head) after detaching its successor. A List destructor with raw pointers does the same: save next, delete, move on.

4. O(1) insert and erase — given the position

"Linked lists have O(1) insertion" is only half true: it's O(1) once you have an iterator to the position. Finding the position is O(n). In a std::list, insert(it, x), erase(it) and splice(it, other) are O(1), and they invalidate nothing except the erased elements:

#include <list>
#include <print>

int main() {
    std::list<int> a{1, 2, 3};
    std::list<int> b{10, 20};
    auto two = std::next(a.begin());       // iterator to 2
    a.splice(two, b);                      // move all of b in front of 2: O(1)
    for (int x : a) std::print("{} ", x);  // 1 10 20 2 3
    std::println("| b has {} elements, *two = {}", b.size(), *two);
}

splice moves nodes, not values: no allocation, no copies, and iterators to the moved elements stay valid (they now point into a). That's something no contiguous container can do.

5. Reversal and the two-pointer tricks

Iterative reversal of a singly linked list — three pointers, one pass:

#include <print>

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

Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* next = head->next;  // save before overwriting
        head->next = prev;        // flip the link
        prev = head;
        head = next;
    }
    return prev;                  // the old tail
}

int main() {
    Node c{3, nullptr}, b{2, &c}, a{1, &b};
    for (Node* p = reverse(&a); p; p = p->next) std::print("{} ", p->value);
    std::println();
}

For a doubly linked ring with a sentinel it's even simpler: swap prev and next in every node, sentinel included.

Fast and slow pointers. Move slow one step and fast two steps:

• When fast falls off the end, slow is at the middle (for an even length, the second of the two middles if you stop when fast is null).
• If the list has a cycle, fast laps slow and they meet — Floyd's algorithm detects a cycle in O(n) time and O(1) memory.

#include <print>

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

bool has_cycle(const Node* head) {
    const Node* slow = head;
    const Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node d{4, nullptr}, c{3, &d}, b{2, &c}, a{1, &b};
    std::println("{}", has_cycle(&a));   // false
    d.next = &b;                         // 4 → 2: a cycle
    std::println("{}", has_cycle(&a));   // true
}

6. Worked example: merging two sorted lists

Merging is where linked lists shine: no buffer, no copies — just relinking. With a dummy head node (a sentinel again), there's no special case for "which list provides the first node":

#include <print>

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

Node* merge(Node* a, Node* b) {
    Node dummy{0, nullptr};
    Node* tail = &dummy;
    while (a && b) {
        if (b->value < a->value) {   // strict: equal elements keep a's first (stable)
            tail->next = b;
            b = b->next;
        } else {
            tail->next = a;
            a = a->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;          // append whatever is left
    return dummy.next;
}

int main() {
    Node a3{6, nullptr}, a2{4, &a3}, a1{1, &a2};
    Node b3{7, nullptr}, b2{3, &b3}, b1{2, &b2};
    for (Node* p = merge(&a1, &b1); p; p = p->next) std::print("{} ", p->value);
    std::println();
}

O(n + m) time, O(1) extra space. Merge sort on a linked list is O(n log n) with O(log n) stack — and needs no extra array, unlike merge sort on a vector.

Faded example — your turn

Find the middle node with fast/slow pointers: for 1 2 3 4 5 return 3; for 1 2 3 4 return 3 (the second middle). Fill in the loop condition and body.

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (/* ??? */) {
        /* ??? */
    }
    return slow;
}

7. Why vectors usually win anyway

Big-O says inserting in the middle of a list is O(1) and in a vector O(n). Hardware says something else: a vector's elements are contiguous, so the CPU prefetches them and each cache line delivers 16 ints; a list's nodes are scattered, and every ->next is a dependent load that may miss the cache. Even a traversal is several times slower:

Run both traversals through a toy cache (4 sets × 2 ways of 16-byte lines) — 16 ints in a vector, and 16 list nodes of 16 bytes (value + next) that the allocator scattered around a pool:

#include <chrono>
#include <list>
#include <numeric>
#include <print>
#include <vector>

template <class C>
double sum_ms(const C& c, long long& out) {
    auto t0 = std::chrono::steady_clock::now();
    out = std::accumulate(c.begin(), c.end(), 0LL);
    return std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
}

int main() {
    constexpr int n = 200'000;
    std::vector<int> v(n, 1);
    std::list<int> l(v.begin(), v.end());
    long long a = 0, b = 0;
    double tv = sum_ms(v, a), tl = sum_ms(l, b);
    std::println("vector {:.2f} ms, list {:.2f} ms (sums {} {})", tv, tl, a, b);
}

(Run it — this lesson's snippets are built with sanitizers, so the absolute numbers are inflated, but the ratio is real; with -O2 the gap usually grows.) And a vector "insert in the middle" is a memmove of contiguous memory, which is very fast for thousands of elements. Reach for a list when you need stable addresses, O(1) splice of ranges, or iterators that must survive insertions — not by default.

Summary

• Doubly linked + sentinel = no null checks, no special cases; end() is the sentinel.
• Keep T out of the sentinel (NodeBase / Node : NodeBase).
• Tear down iteratively; unique_ptr chains recurse.
• Insert/erase are O(1) given an iterator; keep a size counter for O(1) size().
• Reverse by flipping links; find middles and cycles with fast/slow pointers.
• Merge and splice relink nodes: no allocation, iterators stay valid.
• Measure before choosing a list over a vector.