Definition
- LRU Cache – a fixed-capacity key-value store that evicts the least recently used entry when full.
- HashMap – maps each key to its doubly linked list node for O(1) lookup.
- Doubly linked list – maintains usage order; most recently used at one end, least recently used at the other.
- Sentinel nodes – dummy head and tail eliminate edge-case null checks for insertions and removals.
- Eviction – when capacity is exceeded, remove the node just before the tail (least recently used) and delete its key from the map.
Imagine the National Bank of India teller keeps only the twenty most recently touched customer files on the desk. Every time a file is read or updated, it moves to the front of the pile. When a brand new file arrives and the desk is full, the file at the very back, the one nobody has touched in the longest time, is put back in the archive. The desk is the cache, the pile order is the linked list, and the quick index of where each file sits is the hash map.
Understanding the Concepts
What is an LRU Cache?
An LRU (Least Recently Used) cache is a fixed-capacity key-value store. When the cache is full and a new entry arrives, it evicts the entry that was accessed least recently. The design that interviewers want makes both get and put run in O(1) time by combining a hash map with a doubly linked list.
package com.bank.model;
public class CacheNode {
public String key;
public String value;
public CacheNode prev;
public CacheNode next;
public CacheNode(String key, String value) {
this.key = key;
this.value = value;
}
}
How do you implement an LRU Cache?
Use a HashMap for O(1) lookups and a doubly linked list with sentinel head and tail for O(1) reordering. The list keeps the most recently used node right after the head sentinel and the least recently used node right before the tail sentinel.
package com.bank.service;
import com.bank.model.CacheNode;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private final int capacity;
private final Map<String, CacheNode> map;
private final CacheNode head; // sentinel
private final CacheNode tail; // sentinel
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new CacheNode("", "");
this.tail = new CacheNode("", "");
head.next = tail;
tail.prev = head;
}
public String get(String key) {
CacheNode node = map.get(key);
if (node == null) return null;
moveToHead(node);
return node.value;
}
public void put(String key, String value) {
CacheNode existing = map.get(key);
if (existing != null) {
existing.value = value;
moveToHead(existing);
} else {
CacheNode newNode = new CacheNode(key, value);
map.put(key, newNode);
addAfterHead(newNode);
if (map.size() > capacity) {
CacheNode lru = tail.prev;
removeNode(lru);
map.remove(lru.key); // must remove from map too!
}
}
}
private void addAfterHead(CacheNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(CacheNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(CacheNode node) {
removeNode(node);
addAfterHead(node);
}
}
How do get and put work step by step?
On get(key): look up the node in the map. If absent, return null (cache miss). If present, move the node to the head (mark as most recently used) and return its value.
On put(key, value): if the key exists, update its value and move it to the head. If the key is new, create a node, add it after the head, and put it in the map. If adding it exceeds capacity, remove the node just before the tail (least recently used) and remove its key from the map.
package com.bank.service;
public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put("ACC-001", "Rajesh Savings");
cache.put("ACC-002", "Priya Current");
cache.put("ACC-003", "Joint Account");
System.out.println(cache.get("ACC-001")); // moves ACC-001 to front
cache.put("ACC-004", "Fixed Deposit"); // evicts ACC-002 (least recently used)
System.out.println(cache.get("ACC-002")); // null (evicted)
System.out.println(cache.get("ACC-003")); // still present
}
}
Rajesh Savings
null
Joint Account
Why are sentinel head and tail nodes important?
Sentinels eliminate null checks when inserting after the head or removing before the tail. Without sentinels, adding to an empty list or removing the last node requires special-case code. With sentinels, every node always has valid prev and next neighbors.
// Without sentinels: special case for empty list
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
// With sentinels: uniform code, no null checks
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
Why must you remove the evicted key from the map?
If you only remove the node from the list but forget to remove its key from the map, the map leaks memory and later lookups may find stale nodes. This is the most common bug in LRU cache implementations.
// WRONG: only removes from list, map leaks
CacheNode lru = tail.prev;
removeNode(lru); // removed from list
// map still has the key! Memory leak and stale data!
// CORRECT: remove from both
CacheNode lru = tail.prev;
removeNode(lru);
map.remove(lru.key); // clean up the map entry
What about Java's LinkedHashMap shortcut?
Java's LinkedHashMap with access order and an overridden removeEldestEntry provides a built-in LRU cache. However, building the map plus doubly linked list by hand demonstrates the mechanics interviewers want to see.
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCacheShortcut extends LinkedHashMap<String, String> {
private final int capacity;
public LRUCacheShortcut(int capacity) {
super(capacity, 0.75f, true); // true = access order
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > capacity;
}
}
What are the edge cases?
Capacity of 1 (every put evicts the previous entry), updating an existing key (should not trigger eviction), and getting a key that was already evicted.
public static void edgeCases() {
LRUCache cache = new LRUCache(1);
cache.put("A", "1");
cache.put("B", "2"); // evicts A
System.out.println(cache.get("A")); // null
System.out.println(cache.get("B")); // "2"
// Update existing key should not evict
cache.put("B", "3");
System.out.println(cache.get("B")); // "3"
}
What should a senior engineer know?
A senior engineer should understand that the LRU cache is a building block for application-level caching, connection pooling, and page replacement in operating systems. Thread safety requires synchronization: either a synchronized wrapper or a ReentrantReadWriteLock for concurrent reads.
In production at National Bank of India, the account service caches hot account balances in an LRU cache. Promoting an account on every access means a frequently checked account is never evicted by a burst of unrelated lookups, keeping the cache hit rate high and database load low.
// Thread-safe wrapper for production use
public class ConcurrentLRUCache {
private final LRUCache cache;
public ConcurrentLRUCache(int capacity) {
this.cache = new LRUCache(capacity);
}
public synchronized String get(String key) {
return cache.get(key);
}
public synchronized void put(String key, String value) {
cache.put(key, value);
}
}
Visual Overview
LRU Cache Structure
HashMap: { ACC-001 → node1, ACC-003 → node3, ACC-004 → node4 }
Doubly Linked List (most recent → least recent):
[HEAD] <──> [ACC-004] <──> [ACC-001] <──> [ACC-003] <──> [TAIL]
sentinel sentinel
get(ACC-001): move ACC-001 to head
[HEAD] <──> [ACC-001] <──> [ACC-004] <──> [ACC-003] <──> [TAIL]
put(ACC-005): insert at head, evict ACC-003 (before tail)
[HEAD] <──> [ACC-005] <──> [ACC-001] <──> [ACC-004] <──> [TAIL]
map.remove("ACC-003")
Node Operations
Remove node X:
X.prev.next = X.next
X.next.prev = X.prev
Add after head:
X.prev = HEAD
X.next = HEAD.next
HEAD.next.prev = X
HEAD.next = X
Key Takeaway
An LRU cache is a fixed-capacity key-value store that evicts the least recently used entry when full. The O(1) design combines a hash map for instant key lookup with a doubly linked list for instant reordering. The list keeps entries ordered by recency: the most recently used node sits right after a sentinel head, and the least recently used sits right before a sentinel tail.
On get, the map finds the node and the list moves it to the head. On put, a new node is inserted at the head and added to the map; if that pushes the size over capacity, the node just before the tail is evicted from both the list and the map. Removing the evicted key from the map is critical: forgetting it causes memory leaks and stale lookups.
Sentinel head and tail nodes are what make the doubly linked list operations clean. They ensure every real node always has valid prev and next neighbors, eliminating null checks for empty-list and single-element edge cases.
In our banking system at National Bank of India, the account service caches hot account balances in an LRU cache. A frequently checked account is promoted on every access and never evicted by a burst of unrelated lookups, keeping the cache hit rate high and the database load low. For production use, we wrap the cache with synchronization for thread safety.
Remember one sentence: a hash map gives O(1) lookup and a doubly linked list gives O(1) reordering, together they make get and put constant time in an LRU cache.
---