LRU Cache

Medium·⚙️ Design & Simulation·Open on LeetCode ↗

Build a fixed-capacity key-value store where reads and writes are both O(1), and when it overflows the entry that was used least recently is the one discarded.

capacity = 3step 1/10

map: key → node

empty

An empty cache of capacity 3: a map from key to node, and a list kept in order of use.

1class Node:
2    def __init__(self, key, val):
3        self.key, self.val = key, val
4        self.prev = self.next = None
5 
6class LRUCache:
7    def __init__(self, capacity):
8        self.cap = capacity
9        self.map = {}
10        self.head, self.tail = Node(0, 0), Node(0, 0)
11        self.head.next, self.tail.prev = self.tail, self.head
12 
13    def _remove(self, node):
14        node.prev.next, node.next.prev = node.next, node.prev
15 
16    def _push_front(self, node):
17        node.prev, node.next = self.head, self.head.next
18        self.head.next.prev = node
19        self.head.next = node
20 
21    def get(self, key):
22        if key not in self.map:
23            return -1
24        node = self.map[key]
25        self._remove(node)
26        self._push_front(node)
27        return node.val
28 
29    def put(self, key, value):
30        if key in self.map:
31            self._remove(self.map[key])
32        node = Node(key, value)
33        self.map[key] = node
34        self._push_front(node)
35        if len(self.map) > self.cap:
36            lru = self.tail.prev
37            self._remove(lru)
38            del self.map[lru.key]

Read the 10 steps as text

1An empty cache of capacity 3: a map from key to node, and a list kept in order of use.
2put(A) — new node goes straight to the front, the most-recent end.
3put(B) — new node goes straight to the front, the most-recent end.
4put(C) — new node goes straight to the front, the most-recent end.
5get(A) — a hit. Reading counts as a use, so it moves from position 2 to the front.
6put(D) — new node goes straight to the front, the most-recent end.
7Over capacity. The last node, B, is the least recently used — evict it.
8Unlink B and delete its key from the map. Both must happen, or the map leaks.
9get(B) — not in the map. It was evicted earlier, so the answer is -1.
10B was evicted because it was last in line — not because it was the oldest write, but the oldest use.

Start with the obvious solution

Store the entries in a hash map alongside a last-used counter. On eviction, scan every entry to find the smallest counter and drop it.

get and put O(1), but eviction O(capacity)

Why that isn't enough: Eviction turns into a linear search for a minimum, so put is no longer constant time once the cache is full. Keeping the entries *ordered* by use instead means the victim is always the last element — no search, no timestamps to compare.

The idea

Two requirements pull in opposite directions. O(1) lookup by key says hash map. 'Which entry was used least recently' is a question about *order*, and a hash map has none. Neither structure alone can do this, which is the actual insight: use both, over the same nodes.

Keep the entries in a list ordered by recency, most recent at the front. Then the least recently used is always the last element — no searching, no timestamps, no scanning for a minimum.

The list has to be doubly linked, and this is the part worth being able to defend. Every operation moves a node from the middle of the list to the front, and to unlink a node in O(1) you need its neighbour on *both* sides. With only next-pointers you'd have to walk from the head to find the predecessor, which makes the whole thing O(n) and defeats the point.

The map doesn't store values, it stores *nodes*. That's what makes the jump from a key straight into the middle of the list O(1). Storing values instead leaves you with no way to find the node to move.

Both operations count as a use, which is easy to overlook: a get must promote its entry to the front, not just return it. An LRU that only reorders on writes is a different, wrong cache.

The approach

1Keep a hash map from key to list node, and a doubly linked list ordered most-recent to least-recent.
2Use sentinel head and tail nodes so insertion and removal never need a null check.
3get: miss returns -1. On a hit, unlink the node, push it to the front, and return its value.
4put: if the key exists, unlink the old node. Create the node, store it in the map, push it to the front.
5If the map is now over capacity, take the node before the tail sentinel, unlink it, and delete its key from the map.

Complexity

Time

O(1)

Space

O(capacity)

Both operations are constant time: a hash lookup plus a fixed number of pointer writes. The space is one node per stored entry.

Code

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(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):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._push_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

What goes wrong

•Not promoting on get. The cache then evicts by write-recency, which passes small tests and fails the moment a key is read repeatedly and never rewritten.
•Storing values in the map instead of nodes, leaving no O(1) way to find the node to unlink.
•Using a singly linked list. Unlinking then costs a walk from the head and every operation quietly becomes O(n) — interviewers ask about this specifically.
•Forgetting to delete the evicted key from the map. The list shrinks but the map doesn't, so the map grows without bound and a later get returns a node that isn't in the list any more.
•On a put to an existing key, pushing a second node without unlinking the first. The map points at the new one and the old one is stranded in the list, corrupting the eviction order.
•Reaching for Python's OrderedDict or Java's LinkedHashMap without being able to describe what's underneath. They're the right production answer and often accepted, but the follow-up is always 'now implement it'.