LeetCode #146 Medium

LRU Cache

Fixed-capacity cache: get and put in O(1), evicting the least recently used key when full.

designhash-tabledoubly-linked-list

02

Intuition

You need O(1) lookup (hash map) AND O(1) reordering by recency (doubly linked list). Marry them: map key → list node; every touch unlinks the node and reinserts at the front; eviction pops the tail. Neither structure alone can do both jobs.

How to spot this pattern

Whenever a data-structure question demands O(1) for operations that seem to need ordering, the answer is usually two structures glued together, each covering the other's weakness. A hash map finds any key instantly but knows nothing about recency; a doubly linked list maintains order and splices in O(1) but can't search. Store the node as the map's value and you get both — the map hands you the node, and the node already knows its neighbours.

03

Approach

1

Why a doubly linked list

Removing a node from the middle in O(1) needs prev and next pointers — recency order is exactly 'move to front on touch'.

2

Sentinels kill edge cases

Dummy head and tail mean every real node has real neighbours — no null checks on unlink/insert.

3

The two ops

get: look up, move node to front. put: update-or-create at front; if over capacity, unlink tail.prev and delete its map entry.

04

Solution & live demo

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

05

Common pitfalls

Using a singly linked list

✗ Wrong

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

✓ Right

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

Unlinking a node needs its predecessor. With only forward pointers you must walk from the head to find it, making every get O(n) and destroying the whole point. The backward pointer is what makes removal O(1).

Storing only the value in the map

✗ Wrong

self.map[key] = value

✓ Right

self.map[key] = node

The map's job isn't just to return the value — it's to locate the node so it can be spliced to the front. Keeping the raw value means searching the list for it, which is O(n).

Not storing the key inside the node

✗ Wrong

class Node:
    def __init__(self, v):
        self.val = v

✓ Right

class Node:
    def __init__(self, k, v):
        self.key, self.val = k, v

On eviction you find the least-recent node from the list tail, but you must also delete its entry from the map — and that needs the key. Without a back-reference the map keeps a dead entry forever and the cache leaks.

06

Edge cases

put on an existing key

Update value and refresh recency — must NOT evict.

capacity 1

Every distinct put evicts the previous key; sentinels keep the list sane.

07

Complexity

Time

O(1) per op

Space

O(capacity)

Map + doubly linked list in lockstep.