Implement an O(1) get/put LRU Cache using a doubly linked list and HashMap, with an optional thread-safe variant using ReadWriteLock.
Overview
An LRU (Least Recently Used) Cache evicts the least recently accessed entry when capacity is reached. The classic O(1) implementation combines a HashMap (for O(1) key lookup) with a Doubly Linked List (for O(1) move-to-front and evict-from-tail). get() retrieves the node and moves it to the front. put() inserts a new head node; if over capacity, it evicts the tail. Java's LinkedHashMap with accessOrder=true provides this out of the box, but interviews test the manual implementation. A thread-safe version wraps access with ReadWriteLock to allow concurrent reads. CacheStats tracks hits and misses for observability.
Requirements Analysis
Functional: get(key) in O(1) — return value or -1 if absent, put(key, value) in O(1) — insert or update, evict LRU entry when capacity is exceeded. Non-functional: O(1) time complexity for both operations, optional thread-safety via ReadWriteLock, capacity configurable at construction.
// Data structures : HashMap<K, DLLNode> + DoublyLinkedList
// Patterns : Composite (node + map together), Decorator (stats tracking layer)Core Classes & Relationships
DLLNode holds key, value, prev and next pointers. DoublyLinkedList exposes addToFront(node), removeNode(node), removeTail() → node. LRUCache<K,V> wraps a HashMap and the list. CacheStats decorator tracks hits, misses, and evictions. Thread-safe variant extends LRUCache and wraps operations with ReentrantReadWriteLock.
// DoublyLinkedList node
public class DLLNode<K, V> {
K key;
V value;
DLLNode<K, V> prev;
DLLNode<K, V> next;
public DLLNode(K key, V value) { this.key = key; this.value = value; }
}
// Doubly Linked List with sentinel head and tail
public class DoublyLinkedList<K, V> {
private final DLLNode<K, V> head = new DLLNode<>(null, null); // sentinel
private final DLLNode<K, V> tail = new DLLNode<>(null, null); // sentinel
private int size = 0;
public DoublyLinkedList() { head.next = tail; tail.prev = head; }
public void addToFront(DLLNode<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
size++;
}
public void removeNode(DLLNode<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
public DLLNode<K, V> removeTail() {
if (size == 0) return null;
DLLNode<K, V> lru = tail.prev;
removeNode(lru);
return lru;
}
public int size() { return size; }
}Java Implementation
LRUCache.get() looks up the map, moves the node to the front, returns the value. put() updates an existing node or creates a new one; if over capacity it evicts the tail. Thread-safe variant uses ReentrantReadWriteLock so concurrent gets do not block each other.
import java.util.HashMap;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LRUCache<K, V> {
private final int capacity;
private final HashMap<K, DLLNode<K, V>> map;
private final DoublyLinkedList<K, V> list;
public LRUCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("Capacity must be positive");
this.capacity = capacity;
this.map = new HashMap<>(capacity);
this.list = new DoublyLinkedList<>();
}
public V get(K key) {
DLLNode<K, V> node = map.get(key);
if (node == null) return null; // cache miss
moveToFront(node); // mark as recently used
return node.value;
}
public void put(K key, V value) {
DLLNode<K, V> existing = map.get(key);
if (existing != null) {
existing.value = value;
moveToFront(existing);
return;
}
if (map.size() >= capacity) {
DLLNode<K, V> evicted = list.removeTail();
if (evicted != null) map.remove(evicted.key);
}
DLLNode<K, V> node = new DLLNode<>(key, value);
list.addToFront(node);
map.put(key, node);
}
private void moveToFront(DLLNode<K, V> node) {
list.removeNode(node);
list.addToFront(node);
}
public int size() { return map.size(); }
public boolean contains(K key) { return map.containsKey(key); }
}
// Thread-safe LRU Cache
public class ThreadSafeLRUCache<K, V> {
private final LRUCache<K, V> cache;
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
public ThreadSafeLRUCache(int capacity) { this.cache = new LRUCache<>(capacity); }
public V get(K key) {
lock.readLock().lock();
try { return cache.get(key); }
finally { lock.readLock().unlock(); }
}
public void put(K key, V value) {
lock.writeLock().lock();
try { cache.put(key, value); }
finally { lock.writeLock().unlock(); }
}
}
// Quick test
LRUCache<Integer, String> lru = new LRUCache<>(3);
lru.put(1, "one");
lru.put(2, "two");
lru.put(3, "three");
System.out.println(lru.get(1)); // "one" — moves 1 to front; LRU is now 2
lru.put(4, "four"); // evicts 2 (LRU)
System.out.println(lru.contains(2)); // false — evicted
System.out.println(lru.contains(4)); // trueKey Points to Remember
- 1O(1) get and put requires both a HashMap (lookup) and a DoublyLinkedList (order); neither alone achieves both operations in O(1).
- 2Sentinel head and tail nodes eliminate null checks at list boundaries, simplifying add/remove logic.
- 3ReadWriteLock allows concurrent reads but exclusive writes — ideal when cache reads vastly outnumber writes.
- 4Java LinkedHashMap(capacity, 0.75f, true) with removeEldestEntry() is the production shortcut but interviewers test the manual DLL implementation.
Interview Questions
Sign in to ask AriaWhy do you need both a HashMap and a DoublyLinkedList for an O(1) LRU Cache?
How would you implement an LFU (Least Frequently Used) cache?
How does ReadWriteLock improve concurrent LRU Cache performance over synchronized?
Ask Aria about Design an LRU Cache
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.