What you will learn
- Why an LRU cache needs two data structures.
- A clean O(1) implementation with sentinel nodes, in Python and Java.
- How to make it thread-safe, and common follow-up questions.
The problem
A cache with fixed capacity. get(key) returns the value (or a miss) and marks the key as recently used. put(key, value) inserts or updates; if the cache is full, it evicts the least recently used key. Both must be O(1).
- A hash map gives O(1) lookup but no order.
- A list gives order, but moving an item to the front is O(n) unless you can reach its neighbours directly.
Solution: a hash map from key to node, plus a doubly linked list ordered from most to least recently used. The map finds the node; the links let us unlink and move it in O(1).
head <-> [4] <-> [3] <-> tail
MRU LRU
map = {4: node4, 3: node3}
Sentinel head and tail nodes remove all the “is the list empty?” special cases.
Python
"""LRU cache with O(1) get and put: hash map + doubly linked list."""
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.map: dict = {} # key -> Node
self.head, self.tail = Node(), Node() # sentinels: head.next is most recent
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node: Node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node: Node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key, default=-1):
node = self.map.get(key)
if node is None:
return default
self._unlink(node) # mark as most recently used
self._push_front(node)
return node.value
def put(self, key, value):
node = self.map.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) == self.capacity:
lru = self.tail.prev # least recently used sits just before the tail
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
def keys_mru_to_lru(self):
out, n = [], self.head.next
while n is not self.tail:
out.append(n.key)
n = n.next
return out
if __name__ == "__main__":
c = LRUCache(2)
c.put(1, "one")
c.put(2, "two")
print(c.get(1)) # one (1 becomes most recent)
c.put(3, "three") # evicts 2
print(c.get(2)) # -1
c.put(4, "four") # evicts 1
print(c.get(1), c.get(3), c.get(4)) # -1 three four
print("order:", c.keys_mru_to_lru())
Output:
one
-1
-1 three four
order: [4, 3]
Java
import java.util.HashMap;
import java.util.Map;
/** LRU cache with O(1) get/put, generic over key and value. */
public class LRUCache<K, V> {
private static final class Node<K, V> {
K key;
V value;
Node<K, V> prev, next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<K, Node<K, V>> map = new HashMap<>();
private final Node<K, V> head = new Node<>(null, null); // most recent after head
private final Node<K, V> tail = new Node<>(null, null); // least recent before tail
public LRUCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public synchronized V get(K key) {
Node<K, V> node = map.get(key);
if (node == null) return null;
unlink(node);
pushFront(node);
return node.value;
}
public synchronized void put(K key, V value) {
Node<K, V> node = map.get(key);
if (node != null) {
node.value = value;
unlink(node);
pushFront(node);
return;
}
if (map.size() == capacity) {
Node<K, V> lru = tail.prev;
unlink(lru);
map.remove(lru.key);
}
node = new Node<>(key, value);
map.put(key, node);
pushFront(node);
}
private void unlink(Node<K, V> n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void pushFront(Node<K, V> n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
}
public static void main(String[] args) {
LRUCache<Integer, String> c = new LRUCache<>(2);
c.put(1, "one");
c.put(2, "two");
System.out.println(c.get(1)); // one
c.put(3, "three"); // evicts 2
System.out.println(c.get(2)); // null
c.put(4, "four"); // evicts 1
System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4)); // null three four
}
}
Output (compiled with javac and run with java LRUCache):
one
null
null three four
synchronized makes each method atomic. Note that even get modifies the list, so a read/write lock wouldn’t help: every operation is a write to the ordering.
Shortcuts and when to use them
- Python:
collections.OrderedDictwithmove_to_end(key)andpopitem(last=False);functools.lru_cachefor memoising functions. - Java:
LinkedHashMapwithaccessOrder=trueand an overriddenremoveEldestEntry.
In interviews, say you know the shortcut, then implement the linked list unless told otherwise.
Follow-up questions
- Thread safety at high concurrency: one lock serialises everything. Shard the cache into N segments by key hash, each with its own lock and capacity (approximate LRU, much higher throughput).
- TTL: store an expiry per node; treat expired entries as misses on
get, and optionally sweep in the background. - LFU instead of LRU: evict the least frequently used key; an O(1) design keeps a map of frequency → doubly linked list plus a
min_freqpointer. - Distributed cache: that becomes an HLD question; see caching in the System Design course. Redis itself offers approximate LRU eviction policies.
This problem is also LeetCode 146 and appears on the LeetCode 150 sheet.
Key takeaways
- LRU = hash map (find node) + doubly linked list (order); both operations are O(1).
- Sentinel nodes remove empty-list edge cases.
- Every
getchanges the order, so the whole operation needs the lock; shard for throughput. - Know the library shortcuts but be ready to build it from scratch.
Exercises
- Add
ttl_secondstoputand make expired keys behave like misses. - Implement a
ShardedLRUCachewith 8 segments, each guarded by its own lock. - Implement an LFU cache with O(1) operations.
Quiz
- Why must the linked list be doubly linked?
- What do sentinel nodes save you from?
- Why doesn’t a read/write lock help an LRU cache?
Show answers
- To unlink a node in O(1) you need its previous node; a singly linked list would require an O(n) search.
- Special cases for an empty list and for inserting or removing at the ends; every real node always has non-null neighbours.
getalso updates recency order, so every operation mutates shared state and needs exclusive access.