Doubly Linked Lists

July 2026 · 22 min read

A singly linked list can only ever look forward. That single limitation is behind almost every awkward case in the last two posts: deletion needed a trailing prev, pop_back was O(n), and reverse iteration was impossible without extra machinery. Add one pointer per node — a prev that points backward — and all three problems collapse at once. This post builds the doubly linked list from two tiny primitives, shows why std::list is really a ring around a single sentinel, and measures exactly what the extra pointer costs.

The prev Pointer and Its Invariant

A doubly linked node carries two links: next to its successor and prev to its predecessor.

struct Node {
    int   val;
    Node* prev;
    Node* next;
    explicit Node(int v) : val(v), prev(nullptr), next(nullptr) {}
};

With two links comes a paired invariant you must preserve on every mutation:

// For every node n that has a successor:
n->next->prev == n
// For every node n that has a predecessor:
n->prev->next == n

Read it aloud: my successor's prev is me, and my predecessor's next is me. The two pointers between any adjacent pair must agree. Half of all doubly-linked bugs are one of these four assignments left out, leaving a node reachable going forward but not backward (or vice versa) — a corruption that a forward-only traversal will not even notice until a reverse walk or an erase trips over it. The discipline is simple: whenever you touch a next, ask which prev must change to match.

Two Primitives: link_after and unlink

Here is the payoff for taking the invariant seriously: you never write insertion or deletion logic more than once. Every structural operation on a doubly linked list is either link_after (splice a detached node in after a given node) or unlink (cut a node out). Write these two correctly and build everything else on top.

// Insert detached node b immediately after node a.
void link_after(Node* a, Node* b) {
    b->prev = a;
    b->next = a->next;
    if (a->next != nullptr) a->next->prev = b;  // old successor points back at b
    a->next = b;                                // a points forward at b
}

// Cut node n out of the list (n keeps its own stale pointers; caller frees it).
void unlink(Node* n) {
    if (n->prev != nullptr) n->prev->next = n->next;
    if (n->next != nullptr) n->next->prev = n->prev;
}

Notice the two if checks in each: they exist only to handle the ends of a naked list, where prev or next may be null. Hold that thought — the sentinel design below deletes those branches entirely and leaves unlink as exactly two unconditional writes. Everything derives from the primitives:

void insert_after (Node* a, int v) { link_after(a, new Node(v)); }
void insert_before(Node* a, int v) { link_after(a->prev, new Node(v)); } // needs a->prev
void erase(Node* n) { unlink(n); delete n; }

Watch unlink(n)

The heart of the whole structure is two pointer writes. To remove C from A ↔ B ↔ C ↔ D, redirect the forward link of C's predecessor and the backward link of C's successor — then free the node. Step through and watch each write land in order.

The same two writes as an explicit trace — removing C from A ↔ B ↔ C ↔ D. Only two links in the whole structure change; every other pointer is untouched:

Note that between write 1 and write 2 the invariant n->next->prev == n is momentarily violated — D->prev still points at the doomed C. This is why the two writes must never be interrupted by code that trusts the invariant, and why sentinel-based lists (below) prefer to route every edit through this single unlink primitive rather than open-coding the pointer surgery. C's own prev/next are left stale, but C is now unreachable, so it does not matter.

O(1) Erase Given Only the Node

This is the doubly linked list's headline feature. Hand a singly linked list a pointer to a node and ask it to delete that node: it cannot, at least not in O(1), because it has no way to reach the predecessor whose next must change. It must walk from the head — O(n). A doubly linked node carries its predecessor, so erase(n) is unconditional O(1).

The singly linked list has one famous escape hatch — the value-copy hack (LeetCode 237). If you cannot reach the predecessor, overwrite the victim with its successor and delete the successor instead:

// Singly linked; 'node' is guaranteed NOT to be the tail.
void deleteNode(Node* node) {
    node->val  = node->next->val;   // copy successor's payload over ourselves
    Node* gone = node->next;
    node->next = gone->next;        // bypass the successor
    delete gone;
}

Push and Pop at Both Ends

Because a node knows both neighbours, both ends are symmetric and O(1) — a doubly linked list is the natural implementation of a deque. Using the sentinel we are about to introduce, each end operation is one call to a primitive:

void push_front(int v) { link_after(&sentinel,        new Node(v)); }
void push_back (int v) { link_after(sentinel.prev,   new Node(v)); }
void pop_front() { if (!empty()) erase(sentinel.next); }
void pop_back () { if (!empty()) erase(sentinel.prev); }

Compare with the singly linked list, where pop_back is O(n): it must find the new last node's predecessor by walking from the head. The back pointer turns that walk into a single dereference, sentinel.prev->prev, which the primitive handles for free.

Bidirectional and Reverse Iteration

A second win from prev: you can walk the list backward at no extra cost, which is why std::list is a bidirectional container and exposes rbegin()/rend().

// forward
for (Node* p = sentinel.next; p != &sentinel; p = p->next) use(p->val);
// reverse \u2014 impossible on a singly linked list without O(n) extra space
for (Node* p = sentinel.prev; p != &sentinel; p = p->prev) use(p->val);

On a singly linked list, iterating in reverse means either reversing the list first, pushing every node onto a stack (O(n) space), or recursing (O(n) stack frames). The prev pointer makes reverse traversal a mirror image of forward traversal — same loop, opposite field.

The Sentinel-Node List (How std::list Works)

Combine the doubly linked node with the sentinel idea from the previous post and something elegant happens. Use one dummy node that is simultaneously before-the-first and after-the-last by making the list circular: sentinel.next is the first real node, sentinel.prev is the last, and an empty list is just the sentinel pointing at itself.

struct List {
    Node sentinel{0};                 // not allocated; the ring anchor

    List() { sentinel.next = sentinel.prev = &sentinel; }  // empty ring

    bool  empty() const { return sentinel.next == &sentinel; }
    Node* first() const { return sentinel.next; }
    Node* last()  const { return sentinel.prev; }

    // With the ring, prev and next are ALWAYS non-null, so no branches:
    static void unlink(Node* n) {
        n->prev->next = n->next;       // two unconditional writes
        n->next->prev = n->prev;
    }
};

Because the sentinel guarantees every node has a real predecessor and successor — even the first and last, which point at the sentinel — unlink loses its if checks and becomes exactly the two writes the animation showed. Insertion is equally branch-free. There is no “is this the head?” case anywhere, because the head is not special: it is just sentinel.next. This is, essentially verbatim, how libstdc++ and libc++ implement std::list: a single non-allocating sentinel node closing a ring, so that begin() is sentinel.next and end() is &sentinel itself.

The Memory Cost: 24 vs 16 Bytes

The back pointer is not free. On a 64-bit platform a singly linked node is 16 bytes (a 4-byte int, 4 bytes of padding, an 8-byte next); the doubly linked node adds another 8-byte pointer for 24 bytes total — a 50% increase in per-node overhead, before the allocator's own header.

So the question is always: is O(1) erase-given-a-node, O(1) pop_back, and free reverse iteration worth 50% more memory and one extra write per structural edit? For an LRU cache, an editor's line buffer, or any structure that holds node handles and deletes through them, yes overwhelmingly. For a forward-only stack or a transient scratch list, no — use singly, or don't use a list at all.

Singly vs Doubly, Operation by Operation

Every row where doubly wins is a row where a singly linked list needed to find a predecessor. That is the entire trade: one pointer of memory buys you the predecessor for free, everywhere, forever.

Check Yourself

Each item is a situation; pick the statement that is actually correct for a doubly linked list.

Practice

• LeetCode 707 — Design Linked List build implement it doubly, then feel pop_back go O(1).
• LeetCode 430 — Flatten a Multilevel Doubly Linked List prev maintain both links while splicing child lists in.
• LeetCode 146 — LRU Cache handles the classic sentinel doubly linked list plus a hash map.
• LeetCode 237 — Delete Node in a Linked List contrast the value-copy hack a doubly list never needs.
• LeetCode 1472 — Design Browser History back/forward bidirectional movement is exactly what prev/next give you.
• LeetCode 432 — All O`one Data Structure buckets a doubly linked list of frequency buckets with O(1) splices.