Design an LRU Cache
O(1) get/put with a hashmap + doubly-linked list — the most-asked data-structure design in machine coding.
Problem Statement
Design a fixed-capacity LRU cache that supports get and put in O(1) time. When the cache is full, inserting a new key must evict the entry that has not been used for the longest time. A successful get and every put for an existing key both count as usage and must make that key the most recently used entry.
The interview-standard solution combines a HashMap for direct key lookup with a doubly linked list for recency ordering. The map gives O(1) access to a node, and the list lets us remove or move that node in O(1).
Business context
LRU Cache is the compact version of many production cache designs: API response caches, database row caches, image caches, and compiler memoization tables all need bounded memory and predictable eviction. Interviewers like it because it looks small but forces the candidate to maintain two data structures with one shared invariant.
The core lesson is that a cache is not just a map. Without the linked list, eviction is slow. Without the map, lookup is slow. The design succeeds only when both structures are updated atomically on every operation.
Functional Requirements
Initialize the cache with a positive fixed capacity.
Return the cached value for a key in O(1) time when the key exists.
Return a miss value for a key that is absent without changing cache contents.
Insert a new key-value pair in O(1) time when space is available.
Update an existing key in O(1) time and mark it as most recently used.
When inserting into a full cache, evict exactly the least recently used entry.
Maintain recency after both read hits and writes.
Expose a small demonstration that shows recency updates and capacity eviction.
Non-Functional Requirements
Constant-time operations
Both get and put must avoid scans. Lookup is through the map; list operations use direct node references.
Bounded memory
The cache stores at most capacity entries. Extra memory is linear in capacity for the map and list nodes.
Invariant safety
The map and linked list must agree: every live key maps to exactly one node that appears between the sentinels.
Thread-safety awareness
The sample implementation synchronizes public operations. In a production cache, this may become a lock strategy or segmented cache decision.
Generic key and value support
The design should work for any key and value types supported by the host language hash map, not only integers.
Requirement Clarification
QWhat should get return on a miss?
For the generic Java implementation, return null on a miss and disallow null keys and values so null is unambiguous. In LeetCode 146 with integers, the usual miss value is -1.
QDo get operations update recency?
Yes. A successful get means the entry was just used, so its node must move to the front of the recency list.
QWhat happens when put is called for an existing key?
Update the value in the existing node, then move that node to the front. It must not create a second node or change the cache size.
QAre capacity zero or negative caches valid?
No for this base design. The constructor rejects non-positive capacity because a cache that can never store entries only complicates the core invariant.
QDoes the base cache need LFU behavior?
No. LRU evicts by recency only. LFU evicts by access frequency and needs extra bookkeeping, usually frequency buckets plus recency within each bucket.
UML Class Diagram
Sequence Diagram
Entity Identification
LRUCache
Public facade for clients. Owns capacity, the key-to-node map, and the sentinel-headed recency list. It is the only class that mutates both structures together.
Node
Internal entry in the doubly linked list. Stores the key so eviction can remove the matching map entry, stores the value for get, and links to neighbors.
HashMap
Provides direct O(1) average lookup from key to list node. It never stores values directly because the node is the value plus recency position.
Recency list
Doubly linked list ordered from most recent to least recent. Moving a node to the front and removing the tail-side node are constant-time operations.
Sentinel nodes
Dummy head and tail nodes that remove edge cases. Adding to an empty list and removing the last real node use the same pointer wiring as every other case.
Client
Calls get and put without knowing the internal map plus list mechanics. This keeps the data structure usable as a small cache component.
Design Patterns Used
The eviction rule is the policy that varies across cache families. This implementation hardens the LRU policy, but the same boundary can become an EvictionPolicy strategy when comparing LRU with LFU, FIFO, or TTL eviction.
Clients see only get and put. The cache hides the coordinated HashMap and doubly linked list updates behind a compact API, preventing callers from corrupting recency state.
Step-by-Step Design
1Start from the invariant
At all times, every cached key appears in the map and exactly once in the list. The list front means most recently used; the node before tail means least recently used.
2Store key and value inside the list node
The key is needed during eviction because the tail-side node tells us which map entry to delete. Without the key in the node, eviction would require a scan.
final class Node<K, V> { final K key; V value; Node<K, V> prev; Node<K, V> next; }3Use dummy sentinels for simpler pointer wiring
Dummy head and tail nodes mean every real node has both a previous and next neighbor. Insert and delete do not need special cases for empty, first, or last.
head.next = tail; tail.prev = head; private void addFront(Node<K, V> node) { Node<K, V> first = head.next; node.prev = head; node.next = first; head.next = node; first.prev = node; }4Make get a lookup plus recency update
A hit returns the value and moves that node to the front. A miss returns null and does not touch the list.
public synchronized V get(K key) { Node<K, V> node = cache.get(key); if (node == null) { return null; } moveToFront(node); return node.value; }5Make put handle update, insert, and eviction separately
If the key already exists, update in place and move it to the front. Otherwise evict the tail-side real node only when the cache is already full, then add the new node at the front.
6Name the concurrency boundary
The map and list must be updated together. The sample uses synchronized public methods; a higher-throughput production design can replace that with a ReentrantLock, striped locks, or a concurrent cache library.
Complete Java Implementation
Explanation of Every Class
Node
Package-private generic list node. It stores key and value plus previous and next links. The key is essential because eviction starts from the least-recent node and then removes the corresponding map entry.
LRUCache
Generic fixed-capacity cache. It owns the HashMap and sentinel-based doubly linked list, exposes synchronized get, put, and size, and keeps helper methods private so list wiring cannot be called out of order.
Main
Small executable demo. It creates a capacity-2 cache, shows that get updates recency, and then inserts new keys to evict the correct least-recently-used entries.
Dry Run
Sample input
Capacity 2. Actions: put(1,A), put(2,B), get(1), put(3,C), get(2), put(4,D), get(1), get(3), get(4). The list is shown from most recent to least recent.
| Step | Operation | Return | Map keys | Recency list | Explanation |
|---|---|---|---|---|---|
| 1 | put(1,A) | - | {1} | 1 | Insert key 1 at the front. |
| 2 | put(2,B) | - | {1,2} | 2 → 1 | Key 2 is newest; key 1 becomes least recent. |
| 3 | get(1) | A | {1,2} | 1 → 2 | Read hit moves key 1 to the front. |
| 4 | put(3,C) | - | {1,3} | 3 → 1 | Cache was full, so key 2 is evicted from the tail side. |
| 5 | get(2) | null | {1,3} | 3 → 1 | Miss does not change recency. |
| 6 | put(4,D) | - | {3,4} | 4 → 3 | Key 1 is now least recent, so it is evicted. |
| 7 | get(1) | null | {3,4} | 4 → 3 | Key 1 was evicted in the previous step. |
| 8 | get(3) | C | {3,4} | 3 → 4 | Read hit makes key 3 most recent. |
| 9 | get(4) | D | {3,4} | 4 → 3 | Read hit makes key 4 most recent. |
The important moment is step 3: reading key 1 protects it from eviction. Therefore step 4 evicts key 2, not key 1.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| get hit | O(1) | O(1) | Map lookup, unlink node, and add node to the front. |
| get miss | O(1) | O(1) | Map lookup only. |
| put existing key | O(1) | O(1) | Update node value and move it to the front. |
| put new key | O(1) | O(1) | Optional tail eviction, map insert, and front insertion. |
| cache storage | - | O(capacity) | One map entry and one list node per cached key. |
The O(1) claim assumes average O(1) hash map operations and that doubly linked list nodes are removed by direct reference, not by searching the list.
Extensibility
Pluggable eviction policies
Extract touch, insert, and evict behavior behind an eviction policy interface. LRU uses one list; LFU would use frequency buckets plus recency order within each frequency.
Metrics and observability
Track hits, misses, evictions, and current size. These counters can be updated inside the synchronized public operations without exposing internals.
TTL expiration
Add timestamps to nodes and check expiry during get and put. A background cleaner is optional; correctness can still be enforced lazily on access.
Weighted capacity
Replace entry count with total weight, such as bytes or cost. Eviction may remove multiple tail-side nodes until the cache is under budget.
Higher concurrency
Segment the cache by key hash or use a dedicated lock. This reduces contention compared with synchronizing the entire cache for every operation.
Alternative Designs
Java LinkedHashMap with access order
Java already provides a linked hash map that can maintain access order and override removeEldestEntry for capacity eviction.
Tradeoffs
Excellent for production Java, but in interviews it hides the core data-structure reasoning the interviewer wants to see.
Array or list scan on every access
Store entries in a list ordered by recency and scan for keys on get and put.
Tradeoffs
Simple to explain but violates O(1) lookup. It is acceptable only for tiny caches where capacity is known to be very small.
Timestamp heap plus map
Keep last-access timestamps and evict from a min-heap.
Tradeoffs
Eviction becomes O(log n), stale heap entries need cleanup, and updates are more complex than direct list movement.
LFU cache
Evict the least frequently used key instead of the least recently used key, breaking ties by recency.
Tradeoffs
Better for stable hot keys but more stateful: frequency maps, buckets, and min-frequency tracking replace the single LRU list.
Common Mistakes
- ×
Updating the map but forgetting to move the node to the front on get.
- ×
Creating a new node for an existing key, leaving a stale duplicate in the list.
- ×
Evicting from the head side instead of the tail side.
- ×
Not storing the key in the node, which makes map removal during eviction impossible without a scan.
- ×
Handling empty, first, and last nodes manually instead of using sentinels, leading to null pointer bugs.
- ×
Forgetting that put for an existing key also counts as usage.
- ×
Claiming thread-safe behavior while updating the map and list without a common lock.
Follow-up Interview Questions
QHow would you make the cache thread-safe?
Guard every operation that touches the map or list with the same lock. The sample uses synchronized methods. For higher throughput, use a ReentrantLock, lock striping, or a mature library cache.
QHow is LRU different from LFU?
LRU evicts the item with the oldest recent access. LFU evicts the item with the lowest access count, usually using recency only to break ties within the same count.
QWhy do we need a doubly linked list instead of a singly linked list?
Moving an arbitrary node requires unlinking it from its previous neighbor. The map gives the node, not its previous node, so a singly linked list would need a scan or extra predecessor tracking.
QWhy not store values directly in the HashMap and keep only keys in the list?
That can work, but the list node still needs the key for eviction and the map still needs to locate the node for movement. Storing key and value together keeps the entry cohesive.
QWhat if null values must be supported?
Return Optional<V>, a custom result object, or a containsKey method so miss can be distinguished from a cached null. The sample disallows null values to keep get simple.
QHow would you support TTL along with LRU?
Add expiry time to each node. On get, treat expired entries as misses and remove them. On put, evict expired entries opportunistically before applying normal LRU eviction.
Production Considerations
Lock contention
A single synchronized cache is correct but serializes all reads and writes. Production caches often segment by key hash or use carefully designed concurrent data structures.
Hash collision behavior
Average O(1) depends on a healthy hash function. Poor key hash implementations can degrade performance, so cache keys should be immutable and have stable equality.
Memory accounting
Entry count is not always enough. Large values may require weighted capacity, admission control, or off-heap storage to prevent memory pressure.
Eviction visibility
Real systems often need eviction listeners for cleanup, metrics, or write-back. The listener must not run while holding a hot lock if it can block.
Cache stampede
A local LRU cache does not prevent many threads from recomputing the same missing value. Add request coalescing or single-flight loading when misses trigger expensive work.
Testing pointer invariants
Unit tests should verify map size, list order, eviction order, update behavior, and repeated get calls. Pointer bugs often pass simple size-only tests.
What Interviewers Look For
Lead with the two-structure invariant: map for lookup, doubly linked list for recency.
State exactly when recency changes: get hit, put existing key, and put new key.
Use sentinels to simplify pointer operations and reduce bug surface.
During eviction, remove the tail-side real node from the list and remove its key from the map.
Call out that generic get returning null requires null values to be disallowed or a different return type.
Mention thread-safety separately from algorithmic complexity; correctness under concurrency needs a shared lock.
Quiz
0/5 answered
1.Why does the cache need both a HashMap and a doubly linked list?
2.After a successful get, what must happen to the accessed node?
3.Why is the key stored inside each Node?
4.What is the main benefit of dummy head and tail sentinels?
5.How does LFU differ from LRU?
Practice Variants
Implement integer LeetCode 146 API
BeginnerConvert the generic cache to an int-to-int class where get returns -1 on miss. Keep the same map plus doubly linked list design.
Add TTL expiration
IntermediateStore expiry time in every node, remove expired nodes on access, and decide whether expired removals should notify eviction listeners.
Build LFU cache
AdvancedReplace the single recency list with frequency buckets, track the minimum frequency, and use recency to break ties within a bucket.
Flashcards
Cheat Sheet
Goal: fixed capacity cache with O(1) get and put.
Core invariant: every cached key maps to exactly one node, and every real node in the list appears in the map.
Data structures: HashMap for key to node lookup; doubly linked list for recency order; dummy head and tail sentinels to avoid edge cases.
Ordering: head side is most recent; tail side is least recent.
Get: map lookup; on hit move node to front and return value; on miss return null.
Put existing: update value, move node to front, do not change size.
Put new: if full, evict node before tail and remove its key from the map; then add the new node at the front and map the key to it.
Complexity: O(1) average time for get and put; O(capacity) space.
Thread-safety: map and list mutations must share one lock or an equivalent concurrency strategy.
References
- DocsLeetCode 146 — LRU Cache
- DocsJava Platform Documentation — LinkedHashMap — Oracle
- BookEffective Java — Item 50 and Item 78 — Joshua Bloch
- BookDesigning Data-Intensive Applications — Martin Kleppmann