Doubly Linked Lists & the LRU Cache

The LRU cache problem

Implement a fixed-capacity cache that supports two operations:

• get(key), return the value for key if present (and mark as most recently used), or -1 if not.
• put(key, value), insert/update the pair (and mark as most recently used). If the cache is full, evict the least-recently-used entry.

Both operations must run in O(1) average time. The cache is used in operating systems (page replacement), databases (buffer pools), and CDNs (object caching), anywhere recently used data is more likely to be needed again than data that hasn't been touched in a while.

Why one data structure is not enough

A hash map answers get in O(1) but doesn't track ordering, there is no way to ask "what's the least recently used key?". An ordered list answers "least recently used" trivially (the last element) and supports inserting at the front in O(1), but lookup is O(n).

The combination, a hash map keyed by the cache's key, valued by a node in a doubly linked list, plus the doubly linked list itself ordered by recency, gets all three operations to O(1).

Why doubly linked, not singly

The "mark as most recently used" operation must remove a node from its current position in the list and re-insert it at the front. Removal is O(1) only if you have a reference to the node's predecessor, so you can rewire prev.next = node.next. With a singly linked list, finding the predecessor requires a linear scan from the head. O(n), defeating the purpose.

A doubly linked list stores both prev and next on each node. Given a reference to any node, you have its predecessor instantly: node.prev. Removal becomes:

def remove(node):
    node.prev.next = node.next
    node.next.prev = node.prev

Dummy head and tail nodes

The first time someone writes a doubly linked list with raw boundaries, half the bugs are "is this the head?" and "is this the tail?" special cases. The fix is sentinels: two dummy nodes that bookend the real list and are never removed. Real nodes always have a real prev and a real next, so the removal code above never null-derefs.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}                       # key -> node
        # Sentinel nodes - never removed.
        self.head = Node()                    # most-recently-used end
        self.tail = Node()                    # least-recently-used end
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.cap:
            lru = self.tail.prev              # the real LRU node
            self._remove(lru)
            del self.cache[lru.key]

Why store the key in the node: when we evict, we have the node (it's tail.prev), but we need the key to remove the corresponding entry from the hash map. Without storing the key on the node, eviction would require a reverse lookup. O(n).

A trace

Capacity 2. Operations: put(1, 1), put(2, 2), get(1), put(3, 3), get(2).

after put(1, 1):  list = [1]                cache = {1}
after put(2, 2):  list = [2, 1]             cache = {1, 2}
after get(1):     list = [1, 2]   returns 1; 1 is now most recent
after put(3, 3):  list = [3, 1]   cache = {1, 3}; 2 evicted
after get(2):     returns -1; 2 is no longer present

Each operation: O(1) hash map work, O(1) doubly-linked-list pointer updates. No traversal anywhere.

Complexity, reasoned

Time: O(1) average for both get and put. The hash map has expected O(1) lookup; the linked list operations are constant-time pointer rewires. Memory: O(capacity), one node per cached entry plus two sentinels, plus the hash map's bucket array.

When NOT to roll your own

Production languages ship LRU caches. Python's functools.lru_cache is built on the same pattern; Java's LinkedHashMap with accessOrder=true is an LRU; C++'s standard library doesn't ship one but Boost's lru_cache does. Use them.

You should write the LRU yourself when (a) you're in an interview and the question is the LRU itself, (b) you need a custom eviction policy that isn't pure LRU (LFU, ARC, 2Q), or (c) the language's built-in lacks a feature you need (e.g., per-entry TTLs).

Where else doubly linked lists earn their keep

• Browser history. Forward and back are both O(1) given a reference to the current node. Singly linked would make "back" O(n).
• Free-block lists in memory allocators. Coalescing adjacent free blocks needs both directions.
• Undo stacks with branching. Each operation is a node; branching off creates a new "next" while preserving the old branch via "prev".
• Editor's gap buffer / piece table. The classic data structures behind text editors with O(1) cursor movement.

Where beginners go wrong

• Forgetting to store the key on the node. Eviction can find the LRU node from the tail sentinel but cannot remove its entry from the hash map without the key.
• Skipping sentinels. Every prev and next assignment becomes a null check. Bugs everywhere.
• Using a singly linked list to save memory. Each node loses 8 bytes but every "touch" becomes O(n), the LRU stops being LRU in spirit.
• Updating the hash map but forgetting to move the node. The hash map says key exists; the linked list still has key at its old position. Future evictions remove the wrong entry.

What to read next

The In-Place Reversal Patterns piece is the other core linked-list technique. The Hash Maps module formalises why O(1) lookup matters here. And the LRU pattern recurs in many systems-design problems, anywhere "recency matters more than time".