A fixed-size cache with constant-time get and put that evicts the least recently used key. A hash map finds the node, and a linked list keeps the order.
▼The problem
LeetCode 146 (Medium). Design a cache with a fixed capacity where get(key) and put(key, value) both run in O(1). get returns the value (or -1 if the key is missing); when a put takes the cache over capacity, the least recently used key is evicted. Every get or put of a key makes it the most recently used.
Example (capacity 3), each step's shelf order listed most recent first:
TRY IT ON LEETCODE ▶The solution
class Node:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
class LRUCache:
def __init__(self, cap):
self.cap, self.map = cap, {}
self.head, self.tail = Node(), Node()
self.head.next = self.tail
self.tail.prev = self.head
def unlink(self, n):
n.prev.next, n.next.prev = n.next, n.prev
def to_front(self, n):
n.prev, n.next = self.head, self.head.next
self.head.next.prev = n
self.head.next = n
def get(self, key):
if key not in self.map: return -1
n = self.map[key]
self.unlink(n); self.to_front(n)
return n.val
def put(self, key, val):
if key in self.map: self.unlink(self.map[key])
n = self.map[key] = Node(key, val)
self.to_front(n)
if len(self.map) > self.cap:
lru = self.tail.prev
self.unlink(lru); del self.map[lru.key]Transcript
LRU Cache. Design a cache with a fixed capacity, where get and put both run in constant time. When it's full, a put evicts the least recently used key.
Say the capacity is three. Picture a shelf of three slots: most recently used on the left, least recently used on the right. Every get or put moves its key to the front.
The simple way keeps one list ordered by use. But finding a key means a scan, and moving it shifts everything else. That's order n per call.
The fix pairs two structures. A hash map takes each key straight to its node. A doubly linked list keeps nodes in order of use. Each node links to both neighbors, so it can be unlinked and moved in constant time.
In code, sentinel nodes, head and tail, guard the ends. Get looks up the node, moves it to the front, and returns its value. Put inserts at the front; when there are too many keys, it unlinks the node before the tail and deletes its key.
Let's play it. Put A, seven; put B, three; put C, nine. Get A returns seven, and A slides to the front. Now put D, five. That's one too many, so the last item, B, is evicted. Without that get, A would have gone. Get B misses: minus one.
Each call is one hash lookup and a few pointer changes, so get and put are order one. Space is order capacity.
Look it up, move it up, drop the last. That's LRU Cache.