Doubly Linked List Explained: O(1) Delete With Sentinel Nodes

A doubly linked list is a singly linked list with one extra pointer per node, and that pointer changes which operations are cheap. Given a node, you can remove it, or move it, in constant time, without walking from the head. On its own that sounds minor. Paired with a hash map it is the engine of the LRU cache, one of the most common design-flavoured coding questions, and the version with sentinel nodes is the one you can write without a single None check.

The problem it solves

Some workloads keep a sequence and constantly reach into its middle: remove this entry, move that one to the front. An array pays O(n) to shift elements for either. A singly linked list can relink in O(1), but only once you know the node before the one you want to remove, and finding it means walking from the head: O(n) again.

A doubly linked list stores that predecessor in every node. Each node has prev and next, so a node you hold already names both neighbours. Removing it is two assignments. Inserting next to it is four. The list can also be walked in either direction, and both ends are reachable in O(1) if you keep a tail.

What it does not buy is lookup. Finding a node by value is still a walk. That is why real uses pair the list with a map from key to node: the map finds the node in O(1), and the list moves it in O(1).

The intuition

Think of the four pointers around a node b sitting between a and c: a.next and c.prev point at b; b.prev and b.next point out. To unlink b, make its neighbours point past it: a.next = c and c.prev = a. Nothing else in the list changes, and nothing needs to be searched, because b.prev told you who a was.

The awkward part of linked lists is the edges. Removing the first node changes the head; removing the last changes the tail; inserting into an empty list changes both. Each is an if, and each is a place for bugs. Sentinels delete those cases: a permanent HEAD node and a permanent TAIL node that hold no data. Every real node now always has a real prev and a real next, so one unlink and one insert handle the front, the back, the middle and the empty list alike. The dummy head in merging two sorted lists is the same trick on one side.

Watch it run

The animation holds two sentinels and three values, c, b and a, and every node shows a next above and a prev below. The target is b. A singly linked list would walk from the head to find whatever points at it. Here it does not: b.prev and b.next already name both neighbours, c and a. The links around b go dashed, because they are about to be written over rather than followed. Then c.next = a and a.prev = c: two assignments, no walking, O(1). b is unreachable from either direction, and the list now reads c, a.

The code

A complete list with sentinels. Every public operation reduces to insert_after and unlink, which is why there is no special case anywhere:

class Node:
    __slots__ = ("val", "prev", "next")
    def __init__(self, val):
        self.val, self.prev, self.next = val, None, None

class DoublyLinkedList:
    def __init__(self):
        self.head, self.tail = Node("HEAD"), Node("TAIL")   # sentinels, never removed
        self.head.next, self.tail.prev = self.tail, self.head
        self.size = 0

    def insert_after(self, at, node):    # O(1): four pointer writes
        node.prev, node.next = at, at.next
        at.next.prev = node
        at.next = node
        self.size += 1
        return node

    def unlink(self, node):              # O(1): both neighbours are in hand
        node.prev.next, node.next.prev = node.next, node.prev
        node.prev = node.next = None
        self.size -= 1
        return node

    def push_front(self, val): return self.insert_after(self.head, Node(val))
    def push_back(self, val):  return self.insert_after(self.tail.prev, Node(val))
    def pop_front(self):       return self.unlink(self.head.next).val
    def pop_back(self):        return self.unlink(self.tail.prev).val

    def move_to_front(self, node):       # the LRU cache's favourite move
        self.insert_after(self.head, self.unlink(node))

    def values(self, backwards=False):
        out, n = [], (self.tail.prev if backwards else self.head.next)
        while n is not self.tail and n is not self.head:
            out.append(n.val)
            n = n.prev if backwards else n.next
        return out

dll = DoublyLinkedList()
a, b, c = dll.push_back("a"), dll.push_back("b"), dll.push_back("c")
dll.unlink(b)
print(dll.values(), dll.values(backwards=True), dll.size)   # ['a', 'c'] ['c', 'a'] 2
dll.move_to_front(c)
print(dll.values())                                         # ['c', 'a']
print(dll.pop_back(), dll.pop_front(), dll.values())        # a c []

For contrast, removing the last node of a 10,000-node singly linked list. The removal itself is one assignment; finding the predecessor is the whole cost:

class SNode:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def singly_remove(head, target):         # must find the node *before* target
    steps, prev = 0, None
    node = head
    while node is not target:
        prev, node = node, node.next
        steps += 1
    if prev is None:
        return target.next, steps
    prev.next = target.next
    return head, steps

head = None
for v in range(10_000, 0, -1):
    head = SNode(v, head)
last = head
while last.next:
    last = last.next
head, steps = singly_remove(head, last)
print(steps)                                                # 9999

Checked on 500 seeded random sequences of pushes, unlinks, moves and pops at both ends, against a plain Python list doing the same work the slow way. After every step, the list must read the same forwards, the reverse backwards, and every node's next.prev must point back at it:

import random

def invariants_hold(dll):
    n, count = dll.head, 0
    while n is not dll.tail:
        if n.next.prev is not n:
            return False
        n, count = n.next, count + 1
    return count - 1 == dll.size

random.seed(28)
ok = True
for _ in range(500):
    dll, ref, where = DoublyLinkedList(), [], {}
    for step in range(random.randint(0, 80)):
        op = random.choice(["front", "back", "unlink", "move", "pop_front", "pop_back"])
        if op == "front" or not ref:
            where[step] = dll.push_front(step)
            ref.insert(0, step)
        elif op == "back":
            where[step] = dll.push_back(step)
            ref.append(step)
        elif op == "unlink":
            v = random.choice(ref)
            dll.unlink(where.pop(v))
            ref.remove(v)                            # the O(n) way, as the reference
        elif op == "move":
            v = random.choice(ref)
            dll.move_to_front(where[v])
            ref.remove(v)
            ref.insert(0, v)
        elif op == "pop_front":
            v = ref.pop(0)
            ok &= dll.pop_front() == v
            where.pop(v)
        else:
            v = ref.pop()
            ok &= dll.pop_back() == v
            where.pop(v)
        ok &= dll.values() == ref and dll.values(backwards=True) == ref[::-1]
        ok &= invariants_hold(dll)
print(ok)                                                   # True

The complexity

• Insert before or after a node you hold, unlink it, move it: O(1).
• Push and pop at either end: O(1), through the sentinels.
• Find by value or by index: O(n). Pair it with a hash map when you need to reach nodes by key.
• Space: O(n), with two pointers per node instead of one. The Big-O cheat sheet lists the singly and doubly linked rows side by side.

Where it goes wrong

• Updating pointers in the wrong order. In insert_after, overwrite at.next before reading it and the new node is linked to itself. Read first, write last, or use one tuple assignment.
• Leaving stale pointers on a removed node. A detached node that still points into the list lets later code follow it back in and corrupt the links. Clear its prev and next.
• Unlinking a sentinel. pop_front on an empty list would unlink TAIL. Check the size first in production code.
• Forgetting the count. Without a size field, "how long is it?" is a walk.
• Reaching for it when a deque will do. For ends-only access, Python's collections.deque is already a linked structure of blocks, with O(1) operations at both ends.

When it shows up in interviews

Most often inside the LRU cache: a map from key to node, a doubly linked list in recency order, move_to_front on every hit and pop_back on eviction. The LFU cache keeps one such list per frequency. It also appears as "design a browser history" (back and forward), a text editor's cursor, or an undo list, and as a pointer-manipulation warm-up next to reversing a linked list.

How to say it in an interview

"Each node stores prev and next, so given a node I can unlink it in O(1): point its predecessor's next at its successor, and its successor's prev at its predecessor. Lookup is still O(n), so when I need to find nodes by key I pair the list with a hash map, which is exactly the LRU cache. I use two sentinel nodes, a dummy head and tail, so every real node always has two neighbours and inserting or removing at the ends needs no special case."