LRU Cache From Scratch: Hash Map + Doubly Linked List

"Design an LRU cache" sounds like a system-design question and is really a data-structure question with a very specific answer. In Python you can pass it in three lines with OrderedDict, and the next thing the interviewer says is "now without that". This is the version without it — and the reasoning that makes the two-structure design feel inevitable rather than memorised.

The problem it solves

A cache with a fixed capacity. get(key) returns the value or -1. put(key, value) inserts or updates. When a new key arrives and the cache is full, evict the least recently used key — the one that has gone longest without a get or put. Both operations must be O(1).

That last line is the whole difficulty. Without it, a list of keys sorted by last use would do.

The intuition

List what the cache must do in constant time, and notice each requirement rules something out:

• Find a key. Needs a hash map. A list would be a linear scan.
• Move a key to "most recent". Needs a linked list, where moving a node is a few pointer swaps. An array would shift everything.
• Remove the least recent key. Needs quick access to one end of that list.
• Remove a node from the middle. Needs the node's predecessor. A singly linked list only knows its successor, so finding the predecessor means walking from the head — O(n). Hence doubly linked.

Neither structure can do the job alone. The map can find but has no order; the list has order but cannot find. So you use both, glued together:

The map does not store values. It stores pointers to list nodes — so finding a key and knowing where it sits in the recency order are the same lookup.

Watch it run

Watch the chain as keys are read and written. A hit does not just return a value: the node is unlinked from where it sits and relinked at the front. When the cache overflows, the node at the tail end is the one that leaves.

The lesson shows the idea with OrderedDict, which is exactly this structure packaged up. Here is what is inside.

The code

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 LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                          # key -> Node
        self.head, self.tail = Node(), Node()  # sentinels, never evicted
        self.head.next, self.tail.prev = self.tail, self.head

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

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

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)                     # a read is a write:
        self._push_front(node)                 # it changes the order
        return node.val

    def put(self, key, val):
        if self.cap <= 0:
            return
        node = self.map.get(key)
        if node:                               # update in place, then refresh
            node.val = val
            self._unlink(node)
        else:
            if len(self.map) == self.cap:      # full: drop the tail
                lru = self.tail.prev
                self._unlink(lru)
                del self.map[lru.key]          # why the node keeps its key
            node = Node(key, val)
            self.map[key] = node
        self._push_front(node)

    def order(self):                           # most to least recent
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key)
            n = n.next
        return out

c = LRUCache(2)
c.put("a", 1); c.put("b", 2)
print(c.order())               # ['b', 'a']
print(c.get("a"))              # 1
print(c.order())               # ['a', 'b']   the read moved a to the front
c.put("c", 3)                  # full: evicts b, the least recently used
print(c.order(), c.get("b"))   # ['c', 'a'] -1
c.put("a", 10)                 # an update refreshes too
print(c.order(), c.get("a"))   # ['a', 'c'] 10

We also ran this class against an OrderedDict reference on hundreds of random sequences of get and put, with capacities from zero to five; the recency order matched after every single operation.

Three design choices in there are doing more work than they look.

Sentinel nodes. head and tail are dummy nodes that are never evicted. Every real node therefore always has a real prev and next, and _unlink is one line with no if node is self.first branches. Without sentinels, insert and remove each need special cases for an empty list, a one-node list, and the ends — and that is where most hand-written versions break.

The node stores its key. On eviction you hold the tail node and must delete its entry from the map. If the node only held the value, you would have no way to find which key to delete short of scanning the map.

Two small helpers. Every operation is "unlink, then push to front", composed differently. Writing those two once is less code and fewer places to get a pointer wrong.

The complexity

Every operation is a dictionary lookup plus a constant number of pointer assignments: O(1) time for get and put. Space is O(capacity) — one node and one map entry per stored key, plus two sentinels.

Where it goes wrong

• Treating get as read-only. A hit must move the node to the front. Skip it and the cache degrades to "least recently inserted", which is FIFO.
• Forgetting to refresh on update. put on an existing key changes its value and its recency.
• Evicting before checking for an existing key. Updating a key in a full cache must not evict anything — the size does not change.
• Removing from the list but not the map (or the reverse). The two structures must change together, every time, or they drift apart silently.
• Capacity zero. Either reject it at construction or make put a no-op, as above. Evicting from an empty list otherwise unlinks a sentinel.

Beyond the interview answer

The design is O(1), but a hit is a write, and that has consequences a follow-up question may probe. A cache shared across threads needs a lock on reads, which is exactly where traffic is heaviest; production caches often approximate LRU — sampling a few keys, or a "clock" bit per entry — to avoid that. LRU is also fooled by one large scan of cold keys, which flushes everything useful. A frequency-aware policy resists that, at a higher bookkeeping cost; the LFU lesson builds one.

How to say it in an interview

"I need O(1) lookup and O(1) reordering, and no single structure does both. A hash map gives lookup; a doubly linked list gives reordering and removal in constant time, because each node knows its predecessor. The map stores key to node. On get, I find the node, unlink it, and push it to the front. On put, I update or create the node at the front, and if I am over capacity I remove the node before the tail sentinel and delete its key from the map — which is why each node stores its key. Sentinels at both ends remove every edge case."

Then write the two helpers first. Everything else is composed from them, and the interviewer can see it.