Design an LRU Cache (O(1) get & put) — Low-Level Design
Design an LRU cache with O(1) get and put — the classic data-structure question. Combining a HashMap with a doubly-linked list, sentinel nodes, Java code, and the thread-safety / LinkedHashMap notes.
🟠 Low-Level Design · Case Study · the classic data-structure problem
"Design an LRU cache" is a rite-of-passage coding/LLD question. An LRU (Least Recently Used) cache holds a fixed number of items and, when full, evicts the one used longest ago. The challenge is doing both get and put in O(1) time — which requires combining two data structures in a clever way. Let's build it.
Step 1 — Requirements
get(key)→ value if present (and mark it most-recently-used), else miss.put(key, value)→ insert/update; if over capacity, evict the least-recently-used item.- Both operations must be O(1). That constraint is the whole puzzle.
Step 2 — Why one data structure isn't enough
🟠 A HashMap gives O(1) lookup but no notion of order (which was used least recently?). A list/array gives order but O(n) to find or move an item. Neither alone hits O(1) for both. The trick is to combine them: a HashMap for instant lookup plus a doubly-linked list for instant reordering and eviction.
Step 3 — The design: HashMap + doubly-linked list
- The map points key → the list node, so you find any item in O(1).
- The list keeps items in recency order: head = most recently used, tail = least. Because it's doubly-linked, you can unlink any node and re-insert at the head in O(1).
class LRUCache {
private final int cap;
private final Map<Integer,Node> map = new HashMap<>();
private final Node head, tail; // dummy head/tail sentinels
int get(int key){
if(!map.containsKey(key)) return -1;
Node n = map.get(key);
moveToHead(n); // mark most-recently-used
return n.value;
}
void put(int key, int val){
if(map.containsKey(key)){ Node n=map.get(key); n.value=val; moveToHead(n); return; }
if(map.size()==cap){ Node lru=tail.prev; remove(lru); map.remove(lru.key); } // evict
Node n=new Node(key,val); addToHead(n); map.put(key,n);
}
// remove(), addToHead(), moveToHead() are all O(1) pointer updates
}
Every operation is O(1): the map finds the node instantly, and the doubly-linked list lets you unlink/insert/evict with a few pointer swaps. Using dummy head and tail sentinels avoids null-checks and edge cases — a clean implementation detail worth mentioning.
Step 4 — The senior notes
🔴 Things to raise: (1) thread-safety — the above isn't thread-safe; a real cache needs locking or a concurrent structure. (2) In Java, LinkedHashMap with accessOrder=true gives you an LRU almost for free (override removeEldestEntry) — good to know, but interviewers usually want the from-scratch map+DLL. (3) Other eviction policies exist (LFU, FIFO) — LRU is one choice; naming the family shows breadth. (4) This is the same idea behind the eviction in a distributed cache, just at a single-node level.
The interview-ready walkthrough
"An LRU cache needs O(1) get and put, which no single structure gives — so I combine a HashMap (key → node, O(1) lookup) with a doubly-linked list ordered by recency (head = most recent, tail = least). get looks up the node and moves it to the head; put inserts at the head and, if over capacity, evicts the tail and removes it from the map. Doubly-linked so unlinking is O(1); I'd use sentinel head/tail nodes to simplify. For production I'd add locking, and note Java's LinkedHashMap can do LRU out of the box." That's the canonical answer with the right nuances."
What to read next
- Design a Distributed Cache — this eviction at cluster scale
- Caching Strategies — eviction policies & write strategies
- Design Tic-Tac-Toe — the next compact LLD
- ← The complete System Design guide (hub)