Doubly Linked List

A doubly linked list is a linked list in which each node carries two pointers — prev to the previous node and next to the following node. The two-way connectivity unlocks O(1) deletion given only a node reference, O(1) backward iteration, and O(1) pop_back, all of which a Singly Linked List cannot achieve. The cost is one extra pointer per node (typically 8 bytes on 64-bit systems) and a doubled set of pointer updates per insertion or deletion. The doubly linked list is the structural backbone of three workhorses you will see in interviews and production code: the LRU cache (hash map of key → list-node + DLL of usage order), the double-ended queue (e.g., Python’s collections.deque, C++‘s std::list), and the navigation history in any GUI (browser back/forward, undo/redo stacks).

1. Intuition — Subway Cars Coupled Both Ways

A singly linked list is a chain of subway cars where each car has a hook only on its rear, dragging the next car behind. To remove a middle car, you have to walk the train from the engine forward until you find the car before the one you want to remove, then re-couple. There is no way to walk backward.

A doubly linked list adds a hook on the front of every car, too — each car is coupled both to the car ahead and the car behind. Now you can stand on any car and walk in either direction. To uncouple a middle car, you don’t need to walk anywhere: you just unhook from the car ahead and the car behind, hook those two together, and the middle car is free. Removing a car is O(1) given the car — no walking required.

The cost: every car has twice the coupling hardware, and any time you insert or remove a car, you have to update both hooks of both neighbors (plus both hooks of the new/removed car itself) — four pointer updates instead of two for a singly linked list. The work is still constant time, just with a larger constant.

2. Tiny Worked Example

Build a doubly linked list 1 ⇄ 2 ⇄ 3 with sentinel head and tail (§4.1), then trace insert and delete.

2.1 Initial State (Empty, with Sentinels)

  head_sentinel              tail_sentinel
   ┌──────┐                   ┌──────┐
   │ HEAD │ ← prev    next →  │ TAIL │
   │ next ●─────────────────→ │ prev ●
   │      │                   │      │
   └──────┘                   └──────┘

The two sentinel nodes are mutually linked: HEAD.next = TAIL, TAIL.prev = HEAD. There are no “real” nodes yet. This setup means every insertion is between two existing nodes, eliminating the special case for “insert into empty list.”

2.2 After push_back(1), push_back(2), push_back(3)

  HEAD ⇄ [1] ⇄ [2] ⇄ [3] ⇄ TAIL

Each node has a prev pointer (drawn implicitly here as ⇄) and a next pointer.

2.3 Delete the Node Carrying Value 2

Suppose we have a direct reference to node 2 (e.g., from a hash map’s lookup — this is the LRU cache trick).

Before:

  HEAD ⇄ [1] ⇄ [2] ⇄ [3] ⇄ TAIL
                ↑
              target

Step 1 — read target.prev (= node 1) and target.next (= node 3):

  prev_neighbor = [1]
  next_neighbor = [3]

Step 2 — rewire neighbors to skip target:

  prev_neighbor.next = next_neighbor   →  [1].next = [3]
  next_neighbor.prev = prev_neighbor   →  [3].prev = [1]

After:

  HEAD ⇄ [1] ⇄ [3] ⇄ TAIL

  [2]   ← orphaned, eligible for GC; its prev/next still point at [1] and [3],
         but no one points at [2], so it disappears

Total work: two pointer assignments. O(1). No walking. This is the operation that makes the doubly linked list the backbone of the LRU cache.

2.4 Insert Value 4 Before Node 2

Before:

  HEAD ⇄ [1] ⇄ [2] ⇄ [3] ⇄ TAIL

Step 1 — create new node, set its pointers to [1] and [2]:

  new_node = [4 | prev=[1] | next=[2]]

Step 2 — rewire neighbors:

  [1].next = new_node
  [2].prev = new_node

After:

  HEAD ⇄ [1] ⇄ [4] ⇄ [2] ⇄ [3] ⇄ TAIL

Total work: four pointer assignments (two on the new node, two on the neighbors). O(1).

3. Pseudocode — Insert and Remove

class Node:
    value
    prev
    next

# Generic "insert new node between left and right" operation —
# the workhorse from which push_front, push_back, insert_before, insert_after all derive.
insert_between(left, right, value):
    node := new Node(value, prev=left, next=right)
    left.next := node
    right.prev := node
    return node

# Equally generic "remove node" — assumes node has well-defined prev/next.
remove(node):
    node.prev.next := node.next
    node.next.prev := node.prev
    # Optional: node.prev = node.next = null  (helps GC, prevents accidental reuse)

# Public API derived from the two primitives:
push_front(value):       insert_between(head_sentinel, head_sentinel.next, value)
push_back(value):        insert_between(tail_sentinel.prev, tail_sentinel, value)
pop_front():             remove(head_sentinel.next)
pop_back():              remove(tail_sentinel.prev)

The two-sentinel design (head sentinel + tail sentinel) is what makes this code “branchless” — it never needs an if list is empty check because the sentinels are always there. Every real node always has a prev and a next (worst case, those are the sentinels). The cost is two extra nodes per list, which is negligible.

4. Patterns

4.1 Sentinel Head and Tail

A single sentinel head (as in the Singly Linked List note’s §4.2) eliminates the head edge case for a singly linked list. For a doubly linked list, you want two sentinels — head and tail — so that operations at both ends are uniform. With both sentinels:

• push_front(v) ≡ insert between HEAD and HEAD.next — works whether the list is empty or not.
• push_back(v) ≡ insert between TAIL.prev and TAIL — works whether the list is empty or not.
• pop_front() ≡ remove HEAD.next (must check it isn’t the TAIL sentinel — that means empty).
• pop_back() ≡ remove TAIL.prev (must check it isn’t the HEAD sentinel).

Many textbook DLL implementations use a single circular sentinel (HEAD.prev == TAIL_role; TAIL.next == HEAD), where one node plays both roles. CLRS and Linux kernel list.h both use this trick — saves one node, more elegant, but the two-sentinel form is easier to read and explain.

4.2 Doubly Linked List vs Singly Linked List + “Find Predecessor”

A subtle question: can you achieve everything a doubly linked list does with a singly linked list and clever bookkeeping?

• O(1) delete given a node reference — almost. There is a notorious trick to “delete a node in O(1) without prev pointer” by copying the next node’s value into the current node and removing the next node:

  def delete_in_place(node):
      node.value = node.next.value
      node.next = node.next.next

  This works for non-tail nodes only and invalidates external references to node.next (which is now a node with copied data, but the user thought it was a different object). LeetCode 237 (“Delete Node in a Linked List”) asks exactly this. It’s clever but fragile, and it doesn’t generalize to “rearrange a node from middle to head” the way DLL splicing does.

• O(1) pop_back — impossible with singly linked + tail-only, because you cannot reach the predecessor of the tail in O(1). Adding a prev pointer per node is upgrading to a doubly linked list. There is no shortcut.

• O(1) backward iteration — impossible without prev pointers.

So the doubly linked list earns its extra pointer cost for any application where you (a) hold node references externally and want O(1) splicing, (b) need to iterate backward, or (c) need O(1) operations at both ends.

4.3 Splicing Sublists

Moving a contiguous range of nodes from one list to another (or rearranging within the same list) is O(1) for a doubly linked list given references to the range’s first and last nodes:

move sublist [A...B] to position before node X:

  # detach [A...B] from its old neighbors
  A.prev.next := B.next
  B.next.prev := A.prev

  # insert [A...B] before X
  X.prev.next := A
  A.prev := X.prev
  B.next := X
  X.prev := B

Six pointer updates. Independent of the sublist’s length. This is what makes DLLs the structure of choice for editor-buffer rebalancing, MRU lists, and concurrent work-stealing queues.

5. Python Implementation

from typing import Optional, Iterator
 
class Node:
    """A doubly-linked list node — value plus prev/next pointers."""
    def __init__(self, value, prev: Optional["Node"] = None, next: Optional["Node"] = None):
        self.value = value
        self.prev = prev
        self.next = next
 
class DoublyLinkedList:
    """Sentinel-head + sentinel-tail DLL. All operations branchless w.r.t. emptiness."""
 
    def __init__(self):
        self._head = Node(value=None)         # head sentinel
        self._tail = Node(value=None)         # tail sentinel
        self._head.next = self._tail
        self._tail.prev = self._head
        self._size = 0
 
    def __len__(self) -> int:
        return self._size
 
    def __iter__(self) -> Iterator:
        cursor = self._head.next
        while cursor is not self._tail:
            yield cursor.value
            cursor = cursor.next
 
    def __reversed__(self) -> Iterator:
        cursor = self._tail.prev
        while cursor is not self._head:
            yield cursor.value
            cursor = cursor.prev
 
    # ---- O(1) primitive ----
 
    def _insert_between(self, left: Node, right: Node, value) -> Node:
        node = Node(value, prev=left, next=right)
        left.next = node
        right.prev = node
        self._size += 1
        return node
 
    def _remove(self, node: Node) -> object:
        """Remove a node we already hold a reference to. O(1)."""
        if node is self._head or node is self._tail:
            raise ValueError("cannot remove sentinel")
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None      # help GC; surface bugs that re-use freed nodes
        self._size -= 1
        return node.value
 
    # ---- O(1) public API ----
 
    def push_front(self, value) -> Node:
        return self._insert_between(self._head, self._head.next, value)
 
    def push_back(self, value) -> Node:
        return self._insert_between(self._tail.prev, self._tail, value)
 
    def pop_front(self) -> object:
        if self._size == 0:
            raise IndexError("pop from empty list")
        return self._remove(self._head.next)
 
    def pop_back(self) -> object:
        if self._size == 0:
            raise IndexError("pop from empty list")
        return self._remove(self._tail.prev)
 
    def move_to_front(self, node: Node) -> None:
        """Splice node out of its current position and insert it at the head.
        Used by [[Least Recently Used Cache|LRU cache]] on every cache hit. O(1)."""
        if node is self._head.next:
            return                          # already at front
        # detach
        node.prev.next = node.next
        node.next.prev = node.prev
        # re-insert at front
        node.prev = self._head
        node.next = self._head.next
        self._head.next.prev = node
        self._head.next = node

The implementation choices to flag:

• Two sentinels. The _insert_between and _remove primitives never branch on emptiness, because every real node has well-defined prev and next (sentinels in the worst case).
• Insertion returns the node. The caller can hold the returned Node reference and later call _remove(node) for O(1) deletion. This is exactly the LRU cache pattern: the hash map maps key → Node, and on eviction the cache calls _remove directly.
• move_to_front is the LRU’s hot-path operation: O(1) splice-and-reinsert without any walking. Notice it does six pointer assignments and zero list traversal.
• prev = next = None after remove. Optional but recommended — it surfaces bugs where code accidentally uses a freed node, and it breaks reference cycles for the garbage collector.

6. Complexity

Operation	Time	Space	Notes
push_front	O(1)	O(1)
push_back	O(1)	O(1)
pop_front	O(1)	O(1)
pop_back	O(1)	O(1)	DLL’s signature win over Singly Linked List
insert_before(node, v)	O(1)	O(1)	given node reference
insert_after(node, v)	O(1)	O(1)	given node reference
_remove(node)	O(1)	O(1)	given node reference — the LRU primitive
find(value)	O(n)	O(1)	linear scan
move_to_front(node)	O(1)	O(1)	splice
Random access by index	O(n)	O(1)	no shortcut
Concatenate two lists	O(1)	O(1)	rewire 2 pointer pairs
Reverse	O(n)	O(1)	swap prev/next on every node

Memory. Per node: value + two pointers + allocator overhead. On 64-bit Linux/glibc, a node holding a 4-byte int costs roughly 32–40 bytes (value 4 + padding 4 + prev 8 + next 8 + allocator header 8–16). Compare to a Singly Linked List node at ~24 bytes and a list[int] (CPython array of pointers to boxed ints) at ~28 bytes per element. The DLL is the most memory-hungry of the three for small values.

7. Use Cases

7.1 LRU Cache — The Canonical Application

A least-recently-used cache maintains a fixed-size set of key-value entries; on access, the touched key becomes “most recently used”; on insertion when full, the least recently used entry is evicted. The standard implementation:

• A hash map key → Node for O(1) lookup.
• A doubly linked list ordered by recency: head = most recent, tail = least recent.

On every get(key) cache hit: hash map lookup → node, then dll.move_to_front(node) — the recency update. O(1).

On every put(key, v): if key not in map, create a new node, push to front, insert into map; if cache is full, dll.pop_back() and remove that key from the map. O(1).

The DLL is essential — a singly linked list cannot do move_to_front in O(1) (no prev pointer means you can’t splice the node out without walking). See Least Recently Used Cache for the full implementation walkthrough.

7.2 Deque (Double-Ended Queue)

A deque is a sequence supporting O(1) push and pop at both ends. The DLL gives you exactly that. In practice, modern deque implementations (Python’s collections.deque, C++‘s std::deque) use a block-linked structure (an array of fixed-size blocks chained together) rather than a per-element linked list — better cache locality, less memory overhead. But the conceptual data structure is “DLL-with-O(1)-both-ends.” See Deque for the abstraction.

7.3 Browser History (Back/Forward)

Each visited URL is a node. The user’s current position is a cursor. Clicking “back” moves the cursor’s prev; clicking “forward” moves to next. Visiting a new URL while in the middle of history (i.e., after some “back” presses) prunes everything after the cursor and appends a new node — exactly the splice operation in §4.3.

7.4 Undo/Redo Stacks

Same shape as browser history. Each user action is a node carrying enough metadata to invert itself; the cursor is the current state. Undo = move cursor to prev; redo = move to next. Branching undo (some editors) corresponds to keeping multiple next chains — a tree, no longer a simple DLL.

7.5 Linux Kernel’s list.h

The Linux kernel’s intrusive circular doubly-linked list is one of the most-used data structures in the kernel — task_struct, file descriptors, network buffer queues, all use it. The implementation is in include/linux/list.h and uses a single sentinel (the “head” is itself a list_head struct, circular). The intrusive design — embedding the list_head struct inside the parent struct rather than allocating a wrapper — saves a memory allocation per element and is the standard kernel pattern.

7.6 Concurrent Data Structures

The Michael-Scott lock-free queue and several work-stealing deques (Chase-Lev) are essentially DLLs with carefully ordered atomic CAS operations on the prev/next pointers. The two-pointer structure makes coordinating producers and consumers (or victims and thieves) more tractable than singly-linked alternatives.

8. Common Interview Problems

Problem	LeetCode	Pattern
LRU Cache	LC 146	Hash + DLL with move-to-front
LFU Cache	LC 460	Hash + DLL of DLLs (one per frequency bucket)
Design Browser History	LC 1472	Cursor in a DLL (or two stacks)
Flatten a Multilevel Doubly Linked List	LC 430	DFS / recursion plus prev/next rewiring
Design Linked List	LC 707	Build singly or doubly from scratch
Add Two Numbers II	LC 445	Often easier with reverse + add (or stacks)

9. Pitfalls

9.1 Forgetting to Update Both Directions

Every insert and remove touches four pointers: the new/removed node’s prev and next, and the neighbors’ next and prev. Forgetting any one leaves the list in an inconsistent state — usually only the forward traversal works while reverse traversal crashes. Always count to four when writing DLL splices.

9.2 Double-Removing a Node

Calling _remove(node) twice on the same node (in code where ownership of a node is unclear) corrupts the list — the second call dereferences node.prev and node.next, which are now null (if you cleared them) or stale references into the list (if you didn’t). Defensive implementations either set prev = next = None after remove (to crash loudly on double-remove) or maintain a “removed?” flag.

9.3 Sentinel Confusion

If your sentinels are real Node objects with payload null, code that doesn’t check for the sentinel can read null and crash. The two-sentinel design (this note) keeps the sentinels behind the _head/_tail private fields — the public iterator never yields them. The one-sentinel circular design (CLRS, Linux kernel) requires every consumer to check “is this the sentinel?” before reading its value.

9.4 Memory Overhead at Small Scales

For lists of millions of small values (e.g., ints), the per-node overhead can dwarf the actual data — 32+ bytes per node for a 4-byte payload is an 8× memory blowup. Profile before choosing a DLL for tight-memory workloads. Modern deques (Python collections.deque, C++ std::deque) use block-linked structures specifically to cut this overhead.

9.5 Cache-Unfriendliness

Even more than singly linked lists, doubly linked lists scatter their nodes through the heap, defeating the prefetcher. A linear scan of a DLL is typically 5–20× slower than a linear scan of a vector<int> of the same length. If your workload is “iterate from front to back,” a vector (or block-linked deque) almost always wins. The DLL’s edge is in point operations (insert/remove given a node) — not bulk traversal.

9.6 External References Outliving the List

If a caller holds a Node reference and the DLL is then destructed (or the node is removed), the caller’s reference is dangling. Most languages with GC make this a non-issue (the node simply lives until the last reference releases), but in C/C++/Rust you need explicit ownership rules. Rust’s borrow checker prevents the common forms but makes implementing a DLL famously painful — the Learning Rust With Entirely Too Many Linked Lists book exists precisely to walk through the four(+) ways to satisfy the borrow checker.

9.7 Reversing a DLL

Reversing a DLL is O(n) — swap prev and next on every node, then swap the head and tail sentinels’ roles. Not a one-liner. Surprisingly easy to get wrong because the loop’s “advance” pointer must be saved before the swap (very similar to the Linked List Reversal iterative pattern but doubled).

9.8 Iterating While Mutating

Removing nodes while iterating forward can break the iteration if the iterator’s “advance” reads cursor.next after the remove (when cursor.next is now None because of cleanup). The safe pattern: read cursor.next into next_cursor before removing cursor, then advance cursor = next_cursor.

10. Diagram — Doubly Linked List with Sentinels

flowchart LR
    H((HEAD))
    A((1))
    B((2))
    C((3))
    T((TAIL))
    H ---|next| A
    A ---|next| B
    B ---|next| C
    C ---|next| T
    T ---|prev| C
    C ---|prev| B
    B ---|prev| A
    A ---|prev| H

What this diagram shows. A four-real-node DLL (values 1, 2, 3, plus the two sentinels) with bidirectional connectivity. Every edge in the diagram represents a next-or-prev pointer. The two sentinels (HEAD and TAIL) bracket the real nodes and never carry payload — their sole purpose is to give every real node well-defined prev and next neighbors, eliminating empty-list edge cases. From any node, you can walk in either direction in O(1) per step. The structure is not circular in this presentation — the sentinels’ outward pointers are typically null or self-loops depending on implementation; the shown form is the most common.

11. Open Questions

• At what hardware cache-line size does a block-linked deque (e.g., 64 elements per block) decisively outperform a per-element doubly linked list for typical sequence-mutation workloads? The answer almost certainly is “always” for cold caches, but the crossover for hot workloads varies.
• Is there any production reason left to use Python’s list rather than collections.deque for queue-like workloads? deque is O(1) at both ends; list is O(1) at the back but O(n) at the front (list.pop(0) is the classic gotcha).

12. See Also

• Singly Linked List — when one pointer per node suffices
• Linked List Cycle Detection — Floyd’s algorithm
• Linked List Reversal — iterative pattern (and adapts to DLLs by swapping prev/next)
• Merge Two Sorted Lists — the merge operation
• Least Recently Used Cache — the canonical DLL application
• Deque — the double-ended-queue abstraction
• Stack, Queue — both implementable on top of a DLL
• Skip List — multi-level singly linked structure with similar O(log n) random access
• Big-O Notation
• SWE Interview Preparation MOC