{ }SolveLogs
⌕
Home / Linked List / #146
LeetCode #146 Medium

LRU Cache

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

Constraints
  • 1 <= capacity <= 3000
  • 0 <= key <= 10⁴
  • 0 <= value <= 10⁵
  • At most 2 * 10⁵ calls will be made to get and put.
designhash-tabledoubly-linked-list
Open on LeetCode ↗
02

Intuition

An lru cache holds a fixed number of keys and evicts the least recently used one when full. Both get and put must run in O(1), and that requirement is what forces the design. Two separate jobs need doing, and no single structure does both: - Find a key instantly — a hash map does this, but has no notion of order. - Reorder by recency instantly — a list has order, but finding a key in it is O(n). So combine them. The hash map stores key to node reference, and the nodes live in a doubly linked list ordered by recency. Looking up a key gives you the node directly; because the node knows its own neighbours, unlinking it and moving it to the front is O(1) — no scanning. The list must be doubly linked. Removing a node from the middle requires rewiring the node before it, and only a prev pointer makes that node reachable in constant time. A singly linked list would force a scan to find the predecessor, which is exactly the O(n) you are trying to avoid. One implementation detail removes most of the bugs: dummy head and tail sentinels. With them, every real node always has a real neighbour on both sides, so unlinking and inserting need no null checks and the empty-cache case behaves like every other.

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

Try it first

Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(1) per op time and O(capacity) space.

1

Understand why one structure is not enough

A hash map gives O(1) lookup but no ordering; a list gives ordering but O(n) lookup. Pairing them lets each do the job it is good at — the map finds the node, the list orders it.

2

Map keys to list nodes

The hash map stores key to a reference to the node itself, not to the value. That reference is what makes reordering O(1): you arrive at the node without traversing anything.

3

Use a doubly linked list for recency

Front means most recently used, back means least. The prev pointer is essential — unlinking a middle node requires reaching its predecessor, and a singly linked list would need an O(n) scan to find it.

4

Add dummy head and tail sentinels

Allocate permanent nodes at both ends. Every real node then has real neighbours, so unlink and insert are branch-free. This removes the empty-list and single-element special cases that cause most of the bugs in this problem.

5

Implement get as lookup plus move

Find the node through the map, unlink it from its current position, and reinsert it at the front. Return its value. If the key is absent, return −1 without touching the list.

6

Implement put as upsert plus evict

If the key exists, update its value and move it to the front. Otherwise create a node, insert at the front, and add it to the map. If the size now exceeds capacity, unlink the node before the tail sentinel and delete its map entry — deleting from only one of the two structures is the classic leak.

7

Cost of the design

Both operations do a constant number of hash lookups and pointer rewires, so both are O(1) time. Space is O(capacity) for the map and the list together.

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:
▶18 return -1
▶19 node = self.map[key]
▶20 self._unlink(node); self._to_front(node)
▶21 return node.val
▶22 
▶23 def put(self, key, value):
▶24 if key in self.map:
▶25 self._unlink(self.map[key])
▶26 node = Node(key, value)
▶27 self.map[key] = node
▶28 self._to_front(node)
▶29 if len(self.map) > self.cap:
▶30 lru = self.tail.prev
▶31 self._unlink(lru)
▶32 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.
← Prev · #145
Binary Tree Postorder Traversal
Next · #147 →
Insertion Sort List