Doubly Linked Lists

The Extra Pointer Back

A singly linked list moves in one direction. Given a pointer to some node $x$, you can reach $x.\text{next}$, but you cannot, in $O(1)$, reach $x$'s predecessor. To delete $x$ you first have to find its predecessor by walking from the head — that is $O(n)$. To iterate backward, you must reverse the list or stack up pointers along the way. This asymmetry is the central pain of the singly linked list.

A doubly linked list fixes it with one structural change: every node carries an extra pointer back. Each node now holds three fields: a value, a forward pointer $\text{next}$, and a backward pointer $\text{prev}$.

That single extra pointer buys two superpowers:

1. Delete-by-pointer in $O(1)$. If you already hold a reference to the node, you can unlink it without ever touching the head — because the predecessor is one hop backward.
2. Reverse traversal in $O(n)$. Just as natural as forward traversal — start at the tail and walk $\text{prev}$ until you hit the front.

The Structural Invariant

The defining property of a well-formed doubly linked list is the bidirectional consistency invariant:

• For every non-tail node $n$: $n.\text{next}.\text{prev} = n$.
• For every non-head node $n$: $n.\text{prev}.\text{next} = n$.

Read this carefully. It says the two arrows between any pair of adjacent nodes are mirror images of each other. If you walk forward from $A$ to $B$, then walking backward from $B$ must land you exactly back at $A$.

Sentinel Head and Tail

The cleanest implementation uses two sentinel nodes: a dummy $\text{head}$ and a dummy $\text{tail}$, neither of which carries user data. The empty list is two sentinels wired together:

1HEAD <-> TAIL          # empty list (two sentinel nodes)
2HEAD <-> [7] <-> TAIL  # one real node
3HEAD <-> [7] <-> [3] <-> [9] <-> TAIL

Why pay for two extra node allocations? Because every real node now sits between two non-null neighbors. The first real node's $\text{prev}$ is the head sentinel, not $\text{None}$. The last real node's $\text{next}$ is the tail sentinel, not $\text{None}$. This is the entire reason sentinels exist: they erase boundary cases.

Without sentinels, every method has to special-case "is this the first/last node?". With sentinels, the same four pointer rewrites work for the front, the middle, and the back. The code is shorter, the bug surface is smaller, and the invariant is uniform. Both std::list in C++ and java.util.LinkedList in Java use this exact idiom.

Splice and Unlink: The Core Pointer Dance

Splice — inserting a new node between A and B

Suppose two adjacent nodes $A$ and $B$ already satisfy $A.\text{next} = B$ and $B.\text{prev} = A$. We want to insert a new node $X$ between them. Four pointer assignments:

1X.prev = A         # 1. X knows its predecessor
2X.next = B         # 2. X knows its successor
3A.next = X         # 3. A's forward link skips through X
4B.prev = X         # 4. B's backward link skips through X

Order matters within pairs. Lines 1–2 set up $X$ completely; lines 3–4 patch the neighbors. Crucially, you must capture the old neighbor before overwriting the pointer that points to it. If you wrote A.next = X first and then tried to read A.next.prev = X, you would be writing into $X$ itself — the link to $B$ would be lost.

Skipping any of the four lines is a silent corruption. Forward traversal might still appear to work even with line 4 missing — but B.prev still points at $A$, so backward traversal misses $X$ entirely.

Unlink — deleting node X between A and B

Now $X$ sits between $A$ and $B$, and we want to remove it. Two pointer assignments suffice:

1A.next = B         # 1. forward chain bypasses X
2B.prev = A         # 2. backward chain bypasses X

That is the entire delete. The neighbors close up around $X$, and $X$ becomes garbage (or in manual-memory languages, the caller frees it). Notice that nothing about this loop required the head pointer — and therefore nothing required $O(n)$ traversal. Given the node, the delete is $O(1)$. This is the crown jewel of the doubly linked list.

Interactive: Doubly Linked List Lab

Build a list, splice nodes into it, delete them by reference, and walk the cursor in either direction. The forward (cyan) and backward (amber) arrows are drawn separately so you can see both halves of the invariant at once. Click any node to select it; sentinels are dashed.

Implementation in Python

Below is a complete, sentinel-based implementation. Every meaningful line is annotated. Read the splice block (lines 22–25) and the unlink block (lines 34–35) carefully — those eight lines contain everything the data structure does.

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.prev = None
5        self.next = None
6
7
8class DoublyLinkedList:
9    def __init__(self):
10        self.head = Node(None)            # dummy head sentinel
11        self.tail = Node(None)            # dummy tail sentinel
12        self.head.next = self.tail
13        self.tail.prev = self.head
14        self.size = 0
15
16    def __len__(self):
17        return self.size
18
19    def insert_after(self, node, value):
20        new_node = Node(value)
21        nxt = node.next
22        new_node.prev = node              # 1. new -> node
23        new_node.next = nxt               # 2. new -> nxt
24        node.next = new_node              # 3. node -> new
25        nxt.prev = new_node               # 4. nxt -> new
26        self.size += 1
27        return new_node
28
29    def delete_node(self, node):
30        if node is self.head or node is self.tail:
31            raise ValueError("cannot delete sentinel")
32        a = node.prev
33        b = node.next
34        a.next = b                        # bypass node forward
35        b.prev = a                        # bypass node backward
36        node.prev = node.next = None      # help GC, prevent dangling refs
37        self.size -= 1
38        return node.value
39
40    def append(self, value):
41        return self.insert_after(self.tail.prev, value)
42
43    def prepend(self, value):
44        return self.insert_after(self.head, value)
45
46    def __iter__(self):
47        cur = self.head.next
48        while cur is not self.tail:
49            yield cur.value
50            cur = cur.next
51
52    def __reversed__(self):
53        cur = self.tail.prev
54        while cur is not self.head:
55            yield cur.value
56            cur = cur.prev

Implementation in C++

The C++ version makes two things explicit that Python hides: memory ownership (RAII, the destructor walks and frees the chain) and copy semantics (we delete the copy constructor, because shallow copying two list objects that share node pointers is a double-free disaster).

1#include <stdexcept>
2
3template <class T>
4class DoublyLinkedList {
5    struct Node {
6        T value;
7        Node* prev;
8        Node* next;
9        Node(T v) : value(v), prev(nullptr), next(nullptr) {}
10    };
11
12    Node* head;            // dummy head sentinel
13    Node* tail;            // dummy tail sentinel
14    std::size_t sz;
15
16public:
17    DoublyLinkedList()
18        : head(new Node(T{})), tail(new Node(T{})), sz(0) {
19        head->next = tail;
20        tail->prev = head;
21    }
22
23    ~DoublyLinkedList() {
24        Node* cur = head;
25        while (cur) {
26            Node* nxt = cur->next;
27            delete cur;
28            cur = nxt;
29        }
30    }
31
32    DoublyLinkedList(const DoublyLinkedList&) = delete;
33    DoublyLinkedList& operator=(const DoublyLinkedList&) = delete;
34
35    Node* insert_after(Node* node, T value) {
36        Node* n  = new Node(value);
37        Node* nx = node->next;
38        n->prev = node;
39        n->next = nx;
40        node->next = n;
41        nx->prev = n;
42        ++sz;
43        return n;
44    }
45
46    T erase(Node* node) {
47        if (node == head || node == tail)
48            throw std::invalid_argument("sentinel");
49        Node* a = node->prev;
50        Node* b = node->next;
51        a->next = b;
52        b->prev = a;
53        T value = node->value;
54        delete node;
55        --sz;
56        return value;
57    }
58};

Why O(1) Delete-by-Pointer Matters

Imagine a cache that maps keys to a position in a recency list — the most-recently used at the front, the least-recently used at the back. On every cache hit, we want to move that entry to the front. The naive plan with a singly linked list:

1. Hashmap gives us a pointer to the node holding the key. Good.
2. To move it, we first have to delete it from its current position.
3. To delete from a singly linked list, we need the predecessor.
4. Finding the predecessor is $O(n)$. Catastrophe — the cache lookup degrades from $O(1)$ expected to $O(n)$ worst case.

With a doubly linked list, step 3 becomes $O(1)$: we already have $x.\text{prev}$. The whole move becomes two unlinks plus four splice rewrites — eight pointer assignments, constant time. This single property is why the canonical LRU cache implementation is a hashmap plus a doubly linked list and not anything else.

The slogan: the doubly linked list is what you reach for when you already know which node you want to delete, and you can't afford to find its predecessor.

Singly linked lists have a famous workaround — delete a node given only a pointer to it by copying the next node's value into the current node and unlinking the next instead. This works only if the deleted node is not the tail, and it has the side effect of changing addresses, which breaks any external iterator pointing at the next node. In production, the doubly linked list is the clean solution.

Memory Cost

Each node carries an extra pointer compared to a singly linked list. On a 64-bit machine that is $8$ bytes per node. For a node holding a 64-bit integer, the structural overhead per node is roughly:

The doubly linked list is 6× more memory per element than a contiguous array of int32, and 1.5× the singly linked variant. In addition, every node lives at a heap-scattered address, so cache locality is poor — a forward walk of $n$ nodes can incur $n$ cache misses.

The two sentinels are a fixed $O(1)$ overhead — irrelevant for any list with more than a handful of elements, and well worth the simplification.

Comparison vs Singly Linked

The big-O column for forward operations is identical, but the constant factors differ — and several rows that were $O(n)$ for the singly version collapse to $O(1)$. When the workload involves deletions by reference, bidirectional iteration, or insertion before a known node, the doubly linked list is the right tool.

Where Doubly Linked Lists Live

1. LRU caches. Hashmap of key $\to$ doubly-linked-list-node, with the list ordered by recency. Every hit is $O(1)$. We will build this in Chapter 9.
2. Browser tab and history navigation. Forward and back buttons walk a doubly linked list of visited pages. Inserting a new page in the middle (after navigating back, then visiting somewhere new) is a one-step splice.
3. Undo/redo stacks in editors. Each command is a node; the cursor moves backward (undo) or forward (redo) through the list of edits. Modern editors like VS Code build their command history this way.
4. Music and video players. Playlists with prev/next buttons — the queue is a doubly linked list (often circular).
5. The Linux kernel. struct list_head in include/linux/list.h is an embedded doubly linked list head with sentinel — used for almost every dynamic list inside the kernel (process lists, file descriptor tables, etc.).
6. Standard library containers. C++ std::list and Java java.util.LinkedList (which also implements Deque) are doubly linked with sentinels.
7. Window managers. Alt-Tab walks a doubly linked list of focusable windows so you can step both directions through the cycle.
8. Text editor line buffers. Some editors store the document as a doubly linked list of lines so that splitting and merging lines (Enter, Backspace at column 0) is constant time.

Pitfalls and How to Avoid Them

1. Forgetting one of the four splice writes. Forward traversal still works; reverse traversal silently skips the new node. Defense: always write splices as four lines in the same order, and run a symmetry assertion in tests: assert n.next.prev is n for every node.
2. Forgetting one of the two unlink writes. Same failure mode. Defense: same assertion, run it on the neighbors after every delete in test mode.
3. Memory leak when destroying the list. In manual-memory languages, you must walk the chain and free every node. The destructor in the C++ implementation above does exactly this.
4. Accidental cycles. Setting node.next = node by mistake creates an infinite loop on iteration. Hard to catch; use a visited-set in debug mode.
5. Iterator invalidation. If a user holds an iterator pointing at a node and you delete that node, the iterator now references freed memory. C++ std::list handles this by documenting that erase invalidates only the erased iterator — but you must clear node.prev and node.next on delete (as Python's delete_node does on line 36) so a stale iterator at least fails fast instead of walking back into the live list.
6. Touching a sentinel. Iterating to node is None instead of node is self.tail walks past the sentinel into $\text{None}$ on the first wraparound. Always test with sentinel identity.

Quick Checks

The doubly linked list adds one pointer per node and earns two superpowers: $O(1)$ delete-by-reference and natural reverse iteration. Combined with sentinels, it becomes the rare data structure where the implementation has zero edge cases — every real node is uniformly "in the middle." In the next section we look at circular linked lists, where the tail loops back to the head and a third class of problems (round-robin schedulers, ring buffers, Josephus-style rotations) becomes natural.