Doubly Linked List

Intuition

Picture a train where every carriage has a coupling at both ends. To remove carriage 5 from the middle, the crew does not need to walk from the engine counting carriages. Standing at carriage 5, they can see carriage 4 behind and carriage 6 in front, uncouple both, and join 4 directly to 6. That is the superpower of a doubly linked list: a node knows both of its neighbours.

A singly linked list can only look forward, so deleting a node requires its predecessor, which means a walk from the head. Adding a prev pointer costs one extra reference per node but turns 'delete this node' and 'insert before this node' into constant-time operations. Pair it with a hash map that jumps straight to any node, and you get structures where every operation is O(1), most famously the LRU cache.

How it works step by step

The cleanest implementations use two sentinel nodes, head and tail, that never hold data. Real nodes always live between them, so every real node has a non-null prev and next, and no operation needs an empty-list special case.

1. Initialise: head.next = tail and tail.prev = head. The list is empty when head.next == tail.
2. Insert node after `p`: set the new node's own pointers first (n.prev = p, n.next = p.next), then fix the neighbours (p.next.prev = n, p.next = n). Inserting at the front is inserting after head; at the back, after tail.prev.
3. Unlink node `n`: n.prev.next = n.next and n.next.prev = n.prev. Two writes, no traversal, O(1).
4. Move to front: unlink the node, then insert it after head.
5. Remove from back: the last real node is tail.prev; unlink it (only if it is not head).
6. Traverse: forward from head.next until tail, or backward from tail.prev until head.

Dry run: an LRU cache of capacity 2

An LRU (least recently used) cache keeps the most recently used key right after head and the least recently used one right before tail. A hash map from key to node lets us find any node instantly. Here H and T are the sentinels and <-> means the nodes point at each other.

Step 3 is the crucial one. The map hands us node 1 directly, and because node 1 knows its own prev (node 2) and next (tail), we detach it with two writes. With a singly linked list we would have to walk from the head to find node 2 first, and the cache would no longer be O(1).

Code

The Java version builds the LRU cache directly on a hand-written doubly linked list, which is what interviewers usually expect for LeetCode #146. The Python version separates a reusable list class from the cache.

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // sentinel, most recent side
    private final Node tail = new Node(0, 0); // sentinel, least recent side

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void addAfterHead(Node n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        addAfterHead(n);
        return n.val;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        Node n = map.get(key);
        if (n != null) {
            n.val = value;
            unlink(n);
            addAfterHead(n);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key); // the node stores its key for exactly this
        }
        n = new Node(key, value);
        map.put(key, n);
        addAfterHead(n);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1)); // 10
        cache.put(3, 30);                 // evicts key 2
        System.out.println(cache.get(2)); // -1
    }
}

class Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key=None, val=None):
        self.key, self.val = key, val
        self.prev = self.next = None


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

    def push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None
        self.size -= 1

    def pop_back(self):
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

    def __iter__(self):
        cur = self.head.next
        while cur is not self.tail:
            yield cur.key, cur.val
            cur = cur.next


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.order = DoublyLinkedList()

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self.order.remove(node)
        self.order.push_front(node)
        return node.val

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self.map.get(key)
        if node is not None:
            node.val = value
            self.order.remove(node)
            self.order.push_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.order.pop_back()
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self.order.push_front(node)


cache = LRUCache(2)
cache.put(1, "A")
cache.put(2, "B")
print(cache.get(1))           # A
cache.put(3, "C")             # evicts 2
print(cache.get(2))           # -1
print(list(cache.order))      # [(3, 'C'), (1, 'A')]

Time and space complexity

Unlinking touches only the node's two neighbours, which it can reach directly, so the cost does not depend on list length. Finding a node by value still requires a walk; the hash map in the LRU cache is what removes that walk. The memory cost is one extra pointer per node compared with a singly linked list, typically 4 or 8 bytes per node depending on the runtime.

Edge cases

• Empty list: with sentinels, head.next == tail; guard pop_back so you never unlink the head sentinel.
• Single real node: unlinking it must leave head.next == tail and tail.prev == head, which the two-write unlink does automatically.
• Updating an existing key in an LRU cache: change the value and move it to the front; do not insert a second node.
• Capacity of 0 or less: every put should be a no-op; otherwise eviction tries to unlink a sentinel.
• Removing a node twice: clear its prev and next after unlinking so a stale reference fails fast instead of corrupting the list.

Common mistakes

• Wrong order of writes on insert. If you set head.next = n before head.next.prev = n, the second line now updates n.prev instead of the old first node. Set the new node's pointers first, then the neighbour that is reachable through the old link, then the one you overwrite.
• Updating only one direction. Fixing next but forgetting prev leaves a list that looks correct when printed forward and breaks the moment you evict from the tail.
• Not storing the key in the node. On eviction you get a node from the tail and must remove its key from the map; without node.key you cannot.
• Skipping sentinels and drowning in null checks. Without them, every insert and delete needs separate branches for empty list, head, and tail.
• Forgetting to move a node on `get`. Reading a key counts as a use; if it is not moved to the front, eviction order is wrong.

Variations and when to use it

A deque (double-ended queue) is a doubly linked list exposing push and pop at both ends; Java's ArrayDeque uses a circular array instead, but LinkedList is doubly linked. A circular doubly linked list joins tail to head, which simplifies rotation. Browser history with back and forward is naturally a doubly linked list of pages. LFU caches use a doubly linked list per frequency bucket. Python's collections.OrderedDict, whose move_to_end and popitem(last=False) make a three-line LRU cache, is backed by exactly this hash map plus doubly linked list combination.

Choose a doubly linked list when you must delete or move arbitrary nodes in O(1) given a reference, or need efficient traversal in both directions. If you only ever touch the front, a singly linked list is lighter. If you need indexing, use an array.

Related LeetCode problems

• #146 LRU Cache — hash map to nodes plus a doubly linked list ordered by recency, exactly the code above.
• #460 LFU Cache — one doubly linked list per frequency, with O(1) moves between buckets.
• #707 Design Linked List — implement index-based get, add, and delete; sentinels make it short.
• #1472 Design Browser History — visit truncates forward history; back and forward walk prev and next.
• #641 Design Circular Deque — insert and delete at both ends in O(1).
• #430 Flatten a Multilevel Doubly Linked List — splice each child list between a node and its next, fixing prev pointers.
• #432 All O(1) Data Structure — buckets of keys kept in a doubly linked list sorted by count.
• #206 Reverse Linked List — in a doubly linked list, reversal is swapping each node's prev and next.

FAQ