the trick
Keep a hash map from key to node, and a doubly linked list ordered by recency. The map gives O(1) access; the DLL lets you unlink and move any node to the front in O(1).
What the structure has to do
Both get and put must be O(1), and every access makes the touched key the
most recently used. So I need two things at once: instant lookup by key, and
instant reordering by recency. No single container gives both.
A hash map gives lookup. A doubly linked list gives ordering I can splice in constant time. So I combine them: the map points at the list node holding each key.
Brute force, then the cut
The naive version is a single list in recency order. Lookup is a linear scan,
and moving an element to the front is O(n). That fails the time requirement.
The fix is to stop searching the list. Store key -> node in a dict so I jump
to any node directly. Because the node is doubly linked, I can detach it and
relink it at the front without touching anything else.
I keep two sentinel nodes, left and right. The node next to left is the
least recently used (the eviction target); the node next to right is the most
recently used. Sentinels mean I never special-case the empty list.
class Node:
def __init__(self, key: int, val: int) -> None:
self.key = key
self.val = val
self.prev: "Node | None" = None
self.next: "Node | None" = None
class LRUCache:
def __init__(self, capacity: int) -> None:
self.cap = capacity
self.cache: dict[int, Node] = {}
# left.next is LRU, right.prev is MRU
self.left = Node(0, 0)
self.right = Node(0, 0)
self.left.next = self.right
self.right.prev = self.left
def _remove(self, node: Node) -> None:
prev, nxt = node.prev, node.next
prev.next = nxt
nxt.prev = prev
def _insert(self, node: Node) -> None:
# insert just before right (most recent)
prev = self.right.prev
prev.next = node
node.prev = prev
node.next = self.right
self.right.prev = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._insert(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._insert(node)
if len(self.cache) > self.cap:
lru = self.left.next
self._remove(lru)
del self.cache[lru.key]Why every operation is constant
get does one dict lookup and one unlink/relink, all pointer swaps. put
optionally removes the old node, inserts the new one at the front, and evicts
from left.next if over capacity. Each step is a fixed number of pointer
assignments, so both stay O(1). Space is O(capacity) for the map and the
list. The sentinels are why _remove and _insert never check for None.