LRU Cache in Java — LinkedHashMap and HashMap + Doubly-Linked List
Fast recall
Quick revision
Core answer
get(key) and put(key, value) — both must be O(1). Two implementations: (1) LinkedHashMap with access order — simplest; override removeEldestEntry to evict when size exceeds capacity. Java's LinkedHashMap with accessOrder=true in the constructor moves each accessed entry to the tail, so the head is always the LRU. (2) HashMap + doubly-linked list — the 'interview' answer; demonstrates understanding of O(1) invariants. The HashMap maps keys to list nodes for O(1) access; the doubly-linked list maintains order, with head = most recent and tail = least recent (or vice versa). Operations: get locates node via HashMap, moves to head (O(1)); put either updates existing (move to head) or inserts new (remove tail if over capacity). Why doubly-linked? Singly-linked can't delete a middle node in O(1) (would need to find its predecessor by traversal). Doubly-linked allows node.prev.next = node.next in O(1). Why sentinel head/tail? Avoids null checks; simplifies the code. Complexity: both approaches are O(1) per operation, O(capacity) space. Thread safety: neither is thread-safe. For concurrent LRU: Collections.synchronizedMap (single lock, serializes everything) or Caffeine / Guava's LoadingCache (lock-striped, industry standard). Common variants: LFU (Least Frequently Used) — uses frequency buckets, more complex; LRU with TTL (Time To Live) — expiry on top of LRU; ARC (Adaptive Replacement Cache) — balances recency and frequency. For interviews, know both implementations: LinkedHashMap is concise (10 lines); HashMap + DLL shows deeper understanding.Whether the candidate understands the O(1) constraints, knows why doubly-linked list is needed (vs singly), can use sentinel nodes, and implements both LinkedHashMap and HashMap+DLL approaches correctly
Using singly-linked list (can't O(1) delete a middle node). Using ArrayList (O(n) removal). Forgetting to update HashMap when evicting. Not handling edge cases (capacity 0, empty cache)
Explain why doubly-linked is necessary for O(1), discuss sentinel node trick, mention thread-safety alternatives (Caffeine, ConcurrentLinkedHashMap), contrast with LFU, and implement both versions
Interview-ready guide
Interview answer
LRU cache requirements
- Fixed capacity
- O(1) get and put
- Evict least-recently-used when full
- Move to 'most recent' on access
Why O(1)?
- LRU is on hot paths (DB buffer, CDN, page cache)
- Any O(log n) or O(n) is unacceptable
The data structures needed
HashMap for lookup
- key → location in order structure
- O(1) access
Linked list for order
- Most recent at front
- Least recent at back
- Need O(1) insert at front, remove at back, move to front
Why doubly-linked?
- O(1) remove any node (need prev)
- Singly can't remove middle in O(1) (no prev pointer)
- Required for move-to-front in O(1)
Sentinel head/tail nodes
- Dummy nodes at both ends
- Eliminates null checks
- Internal nodes always have valid prev/next
- Cleaner code
Two implementations
1. LinkedHashMap — short version
- Extend LinkedHashMap
- Constructor: super(capacity, 0.75f, true) — accessOrder=true
- Override removeEldestEntry: return size() > capacity
- ~10 lines
- Uses JDK's built-in LinkedHashMap (HashMap + DLL under the hood)
2. HashMap + DLL — interview version
- Manual Node class with key, value, prev, next
- HashMap<Integer, Node>
- Sentinel head and tail nodes
- addToFront, removeNode, moveToFront helpers
- ~40 lines
- Shows understanding
Get operation
- Lookup key in HashMap → node
- If not found: return -1
- Move node to front (remove + addToFront)
- Return node.value
Put operation
- Lookup key in HashMap
- If exists: update value, move to front
- If not: check capacity
- If full: evict tail.prev from both list and HashMap
- Create new node, addToFront, put in HashMap
Common bugs
1. Using singly-linked list
- Can't O(1) remove middle
- Need doubly
2. Using ArrayList
- O(n) insert/delete
- Not O(1)
3. Forgetting to update HashMap on eviction
- Memory leak / stale key
- Always map.remove(evicted.key)
4. Missing sentinel nodes
- Null checks everywhere
- Bug-prone
- Always use sentinels
5. Wrong order: update value vs move to front
- Must do both on existing key
6. Capacity 0 or 1
- Capacity 0: everything misses
- Capacity 1: every put evicts
- Handle both gracefully
Thread safety
Neither approach is thread-safe
- Data races, lost updates, NPEs
Options for concurrent
Collections.synchronizedMap
- Single lock, serializes all access
- Low throughput
ReentrantReadWriteLock
- Limited help: LRU's get is effectively a write (moves entry)
Caffeine (industry standard)
- Lock-striped, like ConcurrentHashMap
- Per-bucket locks
- ~200ns per op in low contention
- TTL, expiry, stats built-in
- Use this in production
Google Guava LoadingCache
- Similar API
- Being superseded by Caffeine
Variants
LFU (Least Frequently Used)
- Frequency buckets
- More complex (O(1) each op)
- Resists eviction of hot items
- Slower to react to changes
LRU with TTL
- expireAt timestamp per entry
- On get: check if expired
- Caffeine native support
ARC (Adaptive Replacement)
- Balances LRU + LFU
- Two queues adjusted dynamically
- Used in ZFS
- Complex; use library
Clock algorithm
- Approximation of LRU
- Circular list with reference bit
- Low overhead
- OS page replacement
2Q
- FIFO for first-time + LRU for repeat
- Scan-resistant
For interviews
- Implement HashMap + DLL (shows algorithm)
- Mention LinkedHashMap as shortcut
- Discuss Caffeine for production concurrent use
- Address edge cases
Recommendation: For interviews, implement the HashMap + doubly-linked list approach — it demonstrates deep understanding of the O(1) invariants. Use sentinel head/tail nodes to eliminate null checks and keep the pointer operations clean. Always remember: doubly-linked is required for O(1) arbitrary-node removal; singly-linked forces O(n) to find predecessors. Mention LinkedHashMap as the idiomatic JDK shortcut — new LinkedHashMap<>(capacity, 0.75f, true) + removeEldestEntry gives you LRU in ~10 lines. For production, both manual and LinkedHashMap implementations are not thread-safe; use Caffeine (industry standard: lock-striped, ~200ns per op, supports TTL, stats, and async loading) or Guava's LoadingCache. Never use Collections.synchronizedMap for high-throughput scenarios — it serializes all access. Handle edge cases: capacity 0 (every get misses), capacity 1 (every put evicts), and duplicate-key puts (update value AND move to front). Always remove from the HashMap when evicting — a common bug leaves stale keys and leaks memory. Know the variants — LFU (frequency-based, harder to implement, resists hot-item eviction), ARC (adaptive, balances LRU and LFU), TTL-based caches (expiry on top of LRU), Clock (approximation used in OS page replacement). The mental model: LRU = O(1) lookup (HashMap) + O(1) order maintenance (DLL). Once you've internalized the sentinel-node trick and the three pointer operations (addToFront, removeNode, moveToFront), the code writes itself.
LRU Cache in Java — LinkedHashMap and HashMap + Doubly-Linked List
Direct Answer
An LRU (Least Recently Used) cache is a fixed-capacity cache that evicts the least-recently-used entry when full. Required operations — get(key) and put(key, value) — both must be O(1). Two implementations: (1) LinkedHashMap with access order — simplest; override removeEldestEntry to evict when size exceeds capacity. Java's LinkedHashMap with accessOrder=true in the constructor moves each accessed entry to the tail, so the head is always the LRU. (2) HashMap + doubly-linked list — the 'interview' answer; demonstrates understanding of O(1) invariants. The HashMap maps keys to list nodes for O(1) access; the doubly-linked list maintains order, with head = most recent and tail = least recent (or vice versa). Operations: get locates node via HashMap, moves to head (O(1)); put either updates existing (move to head) or inserts new (remove tail if over capacity). Why doubly-linked? Singly-linked can't delete a middle node in O(1) (would need to find its predecessor by traversal). Doubly-linked allows node.prev.next = node.next in O(1). Why sentinel head/tail? Avoids null checks; simplifies the code. Complexity: both approaches are O(1) per operation, O(capacity) space. Thread safety: neither is thread-safe. For concurrent LRU: Collections.synchronizedMap (single lock, serializes everything) or Caffeine / Guava's LoadingCache (lock-striped, industry standard). Common variants: LFU (Least Frequently Used) — uses frequency buckets, more complex; LRU with TTL (Time To Live) — expiry on top of LRU; ARC (Adaptive Replacement Cache) — balances recency and frequency. For interviews, know both implementations: LinkedHashMap is concise (10 lines); HashMap + DLL shows deeper understanding.
Common Mistakes & Pitfalls
Using singly-linked list (can't O(1) delete a middle node). Using ArrayList (O(n) removal). Forgetting to update HashMap when evicting. Not handling edge cases (capacity 0, empty cache)
Check your understanding
Answer these without looking back at the article.
- Why must the list be doubly-linked and not singly-linked?
- Why use sentinel head and tail nodes?
- How would you make the LRU cache thread-safe for production?
- What's the difference between LRU and LFU eviction policies?
- How does Caffeine achieve high-throughput concurrent LRU?
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.