Definition
- LRU cache – a fixed-capacity key-value store that evicts the entry accessed longest ago when a new entry arrives and the cache is full.
- HashMap – maps every key to its doubly linked list node, giving O(1) lookup.
- Doubly linked list – orders nodes by recency; the most recently used node sits at the front and the least recently used sits at the tail.
- Sentinel nodes – dummy head and tail nodes that simplify link and unlink operations by removing null checks.
- Eviction – when the cache exceeds capacity, the tail node (least recently used) is removed from both the list and the map.
The National Bank of India keeps only the ten most recently viewed customer profiles on a fast desk because fetching the full archive is slow. Every time a clerk views a profile, she moves that folder to the front of the desk. When a new profile is needed and the desk is full, she removes the folder at the very back, the one nobody has touched for the longest time. A card index on the side tells her instantly where each folder sits so she never searches the desk.
Understanding the Concepts
What is an LRU cache?
An LRU (Least Recently Used) cache is a fixed-capacity data structure that stores key-value pairs. When a new key needs to be inserted and the cache is already full, it evicts the entry that was accessed the longest time ago. Both get and put operations must run in O(1) time.
In the National Bank of India mobile app, recent account balance lookups are cached so the database is not hit on every request. When the cache is full and a new account is queried, the balance that nobody has requested for the longest time is evicted to make room.
// Usage contract
LRUCache cache = new LRUCache(3);
cache.put("ACC1001", balance1001); // cache: [ACC1001]
cache.put("ACC1002", balance1002); // cache: [ACC1002, ACC1001]
cache.put("ACC1003", balance1003); // cache: [ACC1003, ACC1002, ACC1001]
cache.get("ACC1001"); // cache: [ACC1001, ACC1003, ACC1002]
cache.put("ACC1004", balance1004); // evicts ACC1002 -> cache: [ACC1004, ACC1001, ACC1003]
Why do we need both a HashMap and a doubly linked list?
A HashMap alone gives O(1) lookup but has no notion of ordering by recency. A linked list alone maintains order but requires O(n) to find a specific node. Combining them solves both problems: the HashMap points directly to the list node so lookup is O(1), and the doubly linked list keeps nodes ordered by recency so reordering and eviction are O(1).
| Structure | Lookup | Insert/Remove | Ordering |
|-----------|--------|---------------|----------|
| HashMap only | O(1) | O(1) | No order |
| LinkedList only | O(n) | O(1) at ends | Maintains order |
| HashMap + Doubly Linked List | O(1) | O(1) anywhere | Maintains order |
package com.bank.cache;
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> map;
private final Node<K, V> head; // sentinel
private final Node<K, V> tail; // sentinel
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new Node<>(null, null);
this.tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
}
How does the doubly linked list node look?
Each node holds a key, a value, and pointers to the previous and next nodes. The key is stored in the node so that during eviction we can remove the tail node and also delete its entry from the HashMap without a reverse lookup.
package com.bank.cache;
class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
How does get work?
On get(key), look up the node in the HashMap. If it exists, unlink it from its current position and re-insert it right after the head sentinel to mark it as most recently used, then return its value. If the key is not in the map, return null or a sentinel value.
public V get(K key) {
Node<K, V> node = map.get(key);
if (node == null) {
return null; // cache miss
}
// Move to front (most recently used)
unlink(node);
insertAfterHead(node);
return node.value;
}
How does put work?
On put(key, value), if the key already exists, update the value and move the node to the front. If it is a new key, create a node, insert it after the head, and put it in the map. If the size now exceeds capacity, remove the tail node (least recently used) and delete its key from the map.
public void put(K key, V value) {
Node<K, V> existing = map.get(key);
if (existing != null) {
existing.value = value;
unlink(existing);
insertAfterHead(existing);
return;
}
Node<K, V> newNode = new Node<>(key, value);
map.put(key, newNode);
insertAfterHead(newNode);
if (map.size() > capacity) {
Node<K, V> lru = tail.prev; // least recently used
unlink(lru);
map.remove(lru.key);
}
}
How do unlink and insertAfterHead work?
These are the two primitive operations on the doubly linked list. Unlink removes a node by connecting its neighbours to each other. InsertAfterHead places a node right after the head sentinel. Because both neighbours are always known through the doubly linked pointers, these operations are O(1) with no scanning.
private void unlink(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insertAfterHead(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
Why must the list be doubly linked?
A singly linked list cannot remove a node in O(1) because you need a pointer to the previous node to splice the list, and with a singly linked list you would have to scan from the head to find the predecessor. A doubly linked list stores the previous pointer directly in each node, so unlinking is always O(1).
// With a singly linked list, removing nodeX requires scanning:
// head -> A -> B -> nodeX -> C -> tail
// You must walk from head to find B, which is O(n)
// With a doubly linked list, nodeX.prev gives B directly:
// head <-> A <-> B <-> nodeX <-> C <-> tail
// nodeX.prev.next = nodeX.next // O(1)
// nodeX.next.prev = nodeX.prev // O(1)
What is the complete runnable implementation?
Here is the full LRU cache with a banking test case that caches account balances.
package com.bank.cache;
import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
public class AccountBalanceCache {
static class Node {
String accountId;
BigDecimal balance;
Node prev, next;
Node(String accountId, BigDecimal balance) {
this.accountId = accountId;
this.balance = balance;
}
}
private final int capacity;
private final Map<String, Node> map = new HashMap<>();
private final Node head = new Node(null, null);
private final Node tail = new Node(null, null);
public AccountBalanceCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public BigDecimal get(String accountId) {
Node node = map.get(accountId);
if (node == null) return null;
unlink(node);
insertAfterHead(node);
return node.balance;
}
public void put(String accountId, BigDecimal balance) {
Node existing = map.get(accountId);
if (existing != null) {
existing.balance = balance;
unlink(existing);
insertAfterHead(existing);
return;
}
Node newNode = new Node(accountId, balance);
map.put(accountId, newNode);
insertAfterHead(newNode);
if (map.size() > capacity) {
Node lru = tail.prev;
unlink(lru);
map.remove(lru.accountId);
}
}
private void unlink(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void insertAfterHead(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
public static void main(String[] args) {
AccountBalanceCache cache = new AccountBalanceCache(3);
cache.put("ACC1001", new BigDecimal("50000.00"));
cache.put("ACC1002", new BigDecimal("75000.00"));
cache.put("ACC1003", new BigDecimal("30000.00"));
System.out.println("Get ACC1001: " + cache.get("ACC1001"));
cache.put("ACC1004", new BigDecimal("90000.00"));
System.out.println("Get ACC1002 (evicted): " + cache.get("ACC1002"));
System.out.println("Get ACC1004: " + cache.get("ACC1004"));
}
}
Get ACC1001: 50000.00
Get ACC1002 (evicted): null
Get ACC1004: 90000.00
How is this different from LinkedHashMap?
Java's LinkedHashMap already implements LRU cache behaviour when constructed with access-order mode and removeEldestEntry overridden. In production, this or a library like Caffeine is the right choice. The hand-rolled version is for interviews to prove you understand the mechanics.
package com.bank.cache;
import java.math.BigDecimal;
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapLRU extends LinkedHashMap<String, BigDecimal> {
private final int capacity;
public LinkedHashMapLRU(int capacity) {
super(capacity, 0.75f, true); // true = access order
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<String, BigDecimal> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LinkedHashMapLRU cache = new LinkedHashMapLRU(3);
cache.put("ACC1001", new BigDecimal("50000.00"));
cache.put("ACC1002", new BigDecimal("75000.00"));
cache.put("ACC1003", new BigDecimal("30000.00"));
cache.get("ACC1001");
cache.put("ACC1004", new BigDecimal("90000.00"));
System.out.println("Contains ACC1002: " + cache.containsKey("ACC1002"));
System.out.println("Cache: " + cache);
}
}
Contains ACC1002: false
Cache: {ACC1003=30000.00, ACC1001=50000.00, ACC1004=90000.00}
What about thread safety?
The hand-rolled LRU cache is not thread-safe. Multiple threads calling get and put concurrently can corrupt the linked list pointers. In production, wrap the cache with Collections.synchronizedMap, use ReentrantReadWriteLock, or use a concurrent cache library like Caffeine.
package com.bank.cache;
import java.math.BigDecimal;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class ThreadSafeBalanceCache {
private final AccountBalanceCache cache;
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
public ThreadSafeBalanceCache(int capacity) {
this.cache = new AccountBalanceCache(capacity);
}
public BigDecimal get(String accountId) {
lock.writeLock().lock(); // write lock because get mutates list order
try {
return cache.get(accountId);
} finally {
lock.writeLock().unlock();
}
}
public void put(String accountId, BigDecimal balance) {
lock.writeLock().lock();
try {
cache.put(accountId, balance);
} finally {
lock.writeLock().unlock();
}
}
}
What are the time and space complexities?
Both get and put are O(1) because the HashMap lookup is O(1) amortized, and the doubly linked list operations (unlink, insertAfterHead, remove tail) are all O(1). Space is O(capacity) for the map entries and list nodes.
| Operation | Time | Space |
|-----------|------|-------|
| get(key) | O(1) | O(capacity) total |
| put(key, value) | O(1) amortized | O(capacity) total |
| Eviction | O(1) | included above |
// Complexity demonstration: 100,000 operations complete instantly
public static void benchmark() {
AccountBalanceCache cache = new AccountBalanceCache(1000);
long start = System.nanoTime();
for (int i = 0; i < 100_000; i++) {
cache.put("ACC" + i, BigDecimal.valueOf(i));
}
for (int i = 0; i < 100_000; i++) {
cache.get("ACC" + i);
}
long elapsed = System.nanoTime() - start;
System.out.println("200K ops in " + (elapsed / 1_000_000) + " ms");
}
What are common mistakes?
The most common mistake is forgetting to store the key inside the node. During eviction you remove the tail node from the list, but you also need to remove its key from the HashMap. Without the key in the node, you would need a reverse lookup from value to key, which is not available.
// WRONG: Node without key
class BadNode {
BigDecimal balance;
BadNode prev, next;
}
// During eviction:
BadNode lru = tail.prev;
unlink(lru);
// map.remove(???); // No way to find the key!
// CORRECT: Node stores the key
class GoodNode {
String accountId; // key stored here
BigDecimal balance;
GoodNode prev, next;
}
// During eviction:
GoodNode lru = tail.prev;
unlink(lru);
map.remove(lru.accountId); // key available from the node
What should a senior engineer know?
- Production choice. Use
LinkedHashMapin access-order mode or Caffeine, not a hand-rolled cache. Caffeine provides bounded concurrency, statistics, and eviction policies. - Eviction policies. LRU is not always the best. LFU (Least Frequently Used) keeps frequently accessed items longer. W-TinyLFU (used by Caffeine) combines recency and frequency for better hit rates.
- Cache stampede. When a popular key is evicted, many threads may simultaneously compute the value. Use a loading cache or a lock per key to prevent thundering herd.
- Memory overhead. Each node has two pointers plus the key and value. For very small values, the overhead can exceed the data. Consider whether the hit-rate improvement justifies the memory cost.
Visual Overview
┌─────────────────────────────────────────────────────────┐ │ LRU Cache │ │ │ │ HashMap<Key, Node> Doubly Linked List │ │ ┌──────────────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐│ │ │ ACC1001 -> ──────> │HEAD│<->│ N1 │<->│ N2 │<->│TAIL││ │ │ ACC1003 -> ──────> │sent│ │MRU │ │LRU │ │sent││ │ └──────────────┘ └────┘ └────┘ └────┘ └────┘│ └─────────────────────────────────────────────────────────┘ get(ACC1003): unlink N2, insert after HEAD ┌────┐ ┌────┐ ┌────┐ ┌────┐ │HEAD│<->│ N2 │<->│ N1 │<->│TAIL│ │sent│ │MRU │ │LRU │ │sent│ └────┘ └────┘ └────┘ └────┘ put(new key, capacity full): remove tail.prev, add new after HEAD ┌────┐ ┌────┐ ┌────┐ ┌────┐ │HEAD│<->│NEW │<->│ N2 │<->│TAIL│ │sent│ │MRU │ │ │ │sent│ └────┘ └────┘ └────┘ └────┘
put / get operation flow:
Client request
│
▼
┌──────────────┐ ┌──────────────────┐
│ HashMap │────>│ Doubly Linked List│
│ O(1) lookup │ │ O(1) move/evict │
└──────────────┘ └──────────────────┘
│ │
▼ ▼
Found in map? Unlink + Move to front
Yes -> update + move Over capacity? -> Remove tail
No -> create + insert Delete tail key from map
Key Takeaway
An LRU cache holds a fixed number of entries and evicts the one accessed longest ago when a new entry arrives and the cache is full. The design challenge is making both get and put run in constant time, and the classic solution pairs two data structures. A HashMap gives O(1) lookup from key to node, and a doubly linked list orders the nodes by recency with the most recently used at the front and the least recently used at the tail.
On a get, I look up the key in the map, unlink the node from its current position, and re-insert it right after the head sentinel to mark it most recently used. On a put, if the key exists I update its value and move it to the front. If it is new, I create a node, insert it after the head, and add it to the map. If the size exceeds capacity, I remove the tail node and delete its key from the map. Sentinel head and tail nodes make the splice logic clean because there are no null edge cases.
In the National Bank of India mobile app, I used this pattern to cache recently requested account balances. The database round-trip was too slow for the high-traffic balance endpoint, so we kept recently requested balances in memory. When the cache was full, the balance nobody had asked for in the longest time was evicted. Both the read and the insert were constant time, which was critical on that hot path.
The production recommendation is to use Java's LinkedHashMap in access-order mode with removeEldestEntry overridden, or a library like Caffeine for concurrent access and better eviction policies. I implement the HashMap-plus-doubly-linked-list by hand in interviews to demonstrate that I understand the mechanics, but I always name the production-ready option.
Remember one sentence: a HashMap for O(1) lookup plus a doubly linked list for O(1) reordering gives constant-time get and put with least-recently-used eviction.
---