A fixed-size cache with O(1) get and put, built from a hash map and a doubly-linked list — then made thread-safe. The concurrency twist is subtler than it looks, and it's the detail worth carrying into an interview.
The problem
Build a cache with a fixed capacity. get(key) returns a value; put(key, value) stores one. When the cache is full, adding a new entry evicts the least recently used one. Both operations must be O(1).
The defining rule is least recently used. Every time you access an entry — by get or put — it becomes the most recently used. The entry that hasn't been touched for the longest is the one evicted when space runs out. Accessing something protects it; neglect gets it evicted.
Both get and put count as "using"
An access is any interaction with a key, not just a read. A get refreshes recency even though it changes no value. A put on an existing key refreshes recency even if the value is identical. The rule is about touching the key, not changing it — so both operations move an entry to most-recently-used.
The O(1) requirement is what makes this more than a dictionary. Getting both constant-time lookup and constant-time eviction forces a specific pairing of two data structures.
Why two data structures
Neither a hash map nor a linked list alone can do the job in O(1). The design comes from combining their strengths.
| Need | HashMap alone | Linked list alone |
|---|---|---|
| Look up a value by key | O(1) ✓ | O(n) — must scan |
| Track recency order | no order at all | O(1) to reorder ✓ |
| Find & evict the LRU entry | O(n) — no notion of oldest | O(1) if it's at a known end ✓ |
The combination
Use a HashMap for O(1) lookup and a doubly-linked list for O(1) recency ordering. The map stores key → node; the node lives in the list. The list keeps entries in recency order — most-recent at the head, least-recent at the tail. On access, move the node to the head (O(1)). On eviction, remove the node at the tail (O(1)). The map gives you the node instantly by key; the list gives you order and eviction. Together, every operation is O(1).
Why not Java's LinkedList
Java's built-in LinkedList is doubly-linked internally, but it won't work here: removing a specific element is O(n), because it has to search for it. For O(1) eviction you need to hold a direct reference to a node and splice it out via its pointers — which means building the list yourself, with the map storing node references directly. That direct-reference-to-node is the whole trick.
The Node and the list
Each node holds its key, its value, and pointers to both neighbours. Storing the key in the node matters — you'll need it during eviction.
class Node {
int key; // stored so eviction can remove it from the map
int value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
The list uses two dummy sentinel nodes — a permanent head and tail that hold no real data. Real nodes live between them. Sentinels eliminate every edge case: with a fixed node always before and after any real node, insertion and removal never hit a null and never need special handling for the empty or single-element cases.
class DoublyLinkedList {
Node head, tail;
DoublyLinkedList() {
head = new Node(0, 0); // dummy — most-recent side
tail = new Node(0, 0); // dummy — least-recent side
head.next = tail;
tail.prev = head;
}
void addNode(Node node) { // insert right after head (most-recent)
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
void removeNode(Node node) { // splice out — O(1)
node.prev.next = node.next;
node.next.prev = node.prev;
}
void moveNodeToFront(Node node) { // mark as recently used
removeNode(node);
addNode(node);
}
Node getLast() { // the LRU node (for eviction)
return tail.prev;
}
}
Layout: head <-> [most recent] <-> ... <-> [least recent] <-> tail. Add at the head end; evict at the tail end (tail.prev).
The four-pointer splice
Inserting into a doubly-linked list is always four pointer updates, and getting them right (and in the right order) is the one fiddly part. To insert node between head and whatever is currently first:
node.prev = head; // 1. node's back → head
node.next = head.next; // 2. node's front → old first
head.next.prev = node; // 3. old first's back → node (BEFORE step 4)
head.next = node; // 4. head's front → node (LAST)
The mental model
To insert a node between A and B: point the node at both (node.prev = A, node.next = B), then point both back at the node (A.next = node, B.prev = node). Four pointers — the new node has two, and each of its two neighbours needs one updated to point back. Here A is head and B is head.next.
Two rules that catch everyone
First, sentinels never move — head and tail are fixed anchors for the life of the list. You change the pointers of nodes, never reassign head or tail themselves. Second, order matters — set head.next.prev = node before head.next = node, because once you overwrite head.next you've lost the reference to the old first node. Capture the old neighbour's link first, then repoint head.
Removal is the same idea in reverse — fix the two neighbours to point past the departing node — and because sentinels guarantee every real node has both a prev and a next, it never touches a null.
get and put
With the list in hand, both operations are short — each is a combination of a map lookup and a list move. The cache holds the map and the list as fields.
public class LRUCache {
private final int capacity;
private final HashMap<Integer, Node> map = new HashMap<>();
private final DoublyLinkedList dll = new DoublyLinkedList();
LRUCache(int capacity) {
this.capacity = capacity;
}
int get(int key) {
if (!map.containsKey(key)) return -1; // miss
Node node = map.get(key);
dll.moveNodeToFront(node); // mark recently used
return node.value;
}
void put(int key, int value) {
if (map.containsKey(key)) { // update existing
Node node = map.get(key);
node.value = value;
dll.moveNodeToFront(node); // refresh recency (always)
return;
}
if (map.size() == capacity) { // full → evict LRU first
Node lru = dll.getLast(); // tail.prev
dll.removeNode(lru);
map.remove(lru.key); // key stored in node → clean the map
}
Node node = new Node(key, value); // insert new
dll.addNode(node);
map.put(key, node);
}
}
get misses cleanly (returns −1) and, on a hit, moves the node to the front before returning. put has three paths: update an existing key (refresh, no size change), insert when there's room, and insert-after-eviction when full.
The eviction detail
Two things about eviction are easy to get wrong, and both are worth stating plainly.
Remove from BOTH structures
When you evict, the node must leave the linked list and the map — and it's easy to do one and forget the other, leaving them out of sync. Removing from the list is removeNode(lru); removing from the map is map.remove(lru.key). This is exactly why the node stores its own key: the map is keyed by key, so you need the evicted node's key to clean the map. Without the key in the node, you couldn't remove it from the map.
Updating an existing key doesn't change size
A put on a key already present updates the value and refreshes recency — but it does not add an entry, so no eviction happens. A common bug is treating every put as an insert and evicting unnecessarily. Check for the existing key first, update in place, and return before touching capacity.
The LRU node is always tail.prev — the last real node before the dummy tail. The sentinel makes this uniform: no matter the list state, the least-recently-used entry sits right before the tail, so eviction is a constant-time reach for tail.prev.
Making it thread-safe
Single-threaded, the cache is correct. Under concurrent access it corrupts — and the reason is the same one that governs most concurrency problems.
A concurrent map is not the fix
The instinct is to swap in a ConcurrentHashMap. It doesn't work, for two reasons. First, each operation is a compound sequence — lookup, then list manipulation, then map update — that must be atomic as a whole; a concurrent map only makes each single call atomic, not the sequence. Second, and more fundamentally, the doubly-linked list is not protected by the map at all. Two threads running the four-pointer splice at once will cross the pointers and mangle the list, no matter what kind of map you use. The corruption is in the list, which the map knows nothing about.
The fix is a single lock around each whole operation, so only one thread runs the full sequence at a time:
synchronized void put(int key, int value) { /* ... whole body ... */ }
synchronized int get(int key) { /* ... whole body ... */ }
One lock, plain HashMap
Both methods are synchronized, so both lock on this — the same lock. That means only one thread is ever inside get or put at a time, making each compound operation atomic across both the map and the list. And once a single lock guards everything, the map never sees concurrent access — so a plain HashMap is correct, and ConcurrentHashMap would be redundant. One mechanism, not two: the lock protects the whole operation; the container needn't be concurrent.
This is the same "one lock guards a compound operation" idea from the thread-safe job scheduler — here there's no waiting or signalling, just mutual exclusion.
Why ReadWriteLock doesn't work here
The single lock has a real cost: it serialises everything, including reads. Since a cache is usually read-heavy, the natural optimisation is a ReadWriteLock — let many readers run concurrently, and only make writers exclusive. For most read-heavy structures that's the right move. For LRU, it breaks — and the reason is subtle and worth understanding.
get is secretly a write
A ReadWriteLock lets multiple readers share the lock because it assumes readers don't modify shared state. But in an LRU cache, get calls moveNodeToFront — which mutates the linked list to update recency. So get looks like a read but behaves like a write. If you let two gets run concurrently under a read lock, they'd both reorder the list at once and corrupt it — exactly like two writers. Since get isn't a true read, the read lock gives no safe concurrency, and you'd have to make get take the write lock anyway — collapsing back to an exclusive lock.
This is the insight that makes LRU concurrency genuinely hard: its reads write. The real ways to improve concurrency don't use a naive read/write split — they use segmented locking (partition the cache, a lock per segment, as ConcurrentHashMap does internally), or they accept an approximate LRU that doesn't reorder on every read (batching or sampling recency updates, as high-performance caches like Caffeine do). Both trade exact recency for throughput.
In production, you'd rarely hand-roll this
Java's LinkedHashMap with accessOrder = true and an overridden removeEldestEntry is an LRU cache in a few lines. For concurrent, high-performance caching, Caffeine is the standard choice. Building it from scratch is for understanding the mechanics — and for the interview, where the reasoning above is the point.
The complete program
Here is the whole thing in one file — Node, DoublyLinkedList, the synchronized LRUCache, and a main that first shows deterministic eviction, then hammers a shared cache with eight threads to show the lock holds the map and list in sync. Save it as LRUCacheDemo.java and run it with a single command (JDK 11+).
import java.util.HashMap;
class Node {
int key, value; // key stored so eviction can clean the map
Node prev, next;
Node(int key, int value) { this.key = key; this.value = value; }
}
class DoublyLinkedList {
final Node head, tail; // dummy sentinels — never move
DoublyLinkedList() {
head = new Node(0, 0); // most-recent side
tail = new Node(0, 0); // least-recent side
head.next = tail;
tail.prev = head;
}
void addNode(Node node) { // insert right after head (most-recent)
node.prev = head;
node.next = head.next;
head.next.prev = node; // BEFORE overwriting head.next
head.next = node;
}
void removeNode(Node node) { // splice out — O(1)
node.prev.next = node.next;
node.next.prev = node.prev;
}
void moveNodeToFront(Node node) { removeNode(node); addNode(node); }
Node getLast() { return tail.prev; } // the LRU node
}
class LRUCache {
private final int capacity;
private final HashMap<Integer, Node> map = new HashMap<>();
private final DoublyLinkedList dll = new DoublyLinkedList();
LRUCache(int capacity) { this.capacity = capacity; }
synchronized int get(int key) {
if (!map.containsKey(key)) return -1; // miss
Node node = map.get(key);
dll.moveNodeToFront(node); // mark recently used
return node.value;
}
synchronized void put(int key, int value) {
if (map.containsKey(key)) { // update existing
Node node = map.get(key);
node.value = value;
dll.moveNodeToFront(node); // refresh recency
return;
}
if (map.size() == capacity) { // full → evict LRU
Node lru = dll.getLast();
dll.removeNode(lru);
map.remove(lru.key); // key in node → clean map
}
Node node = new Node(key, value);
dll.addNode(node);
map.put(key, node);
}
synchronized int size() { return map.size(); }
}
public class LRUCacheDemo {
public static void main(String[] args) throws InterruptedException {
// ---- Part 1: deterministic LRU behaviour ----
System.out.println("== Part 1: eviction & recency ==");
LRUCache cache = new LRUCache(2);
cache.put(1, 10);
cache.put(2, 20);
System.out.println("get(1) = " + cache.get(1)); // 10, now 1 is MRU
cache.put(3, 30); // capacity 2 → evicts key 2 (LRU)
System.out.println("get(2) = " + cache.get(2)); // -1 (evicted)
System.out.println("get(3) = " + cache.get(3)); // 30
cache.put(1, 11); // update existing, no eviction
System.out.println("get(1) = " + cache.get(1)); // 11
System.out.println("size = " + cache.size()); // 2
// ---- Part 2: thread-safety stress ----
System.out.println("\n== Part 2: 8 threads hammering, no corruption ==");
final LRUCache shared = new LRUCache(50);
final int THREADS = 8, OPS = 50_000;
Thread[] ts = new Thread[THREADS];
for (int t = 0; t < THREADS; t++) {
ts[t] = new Thread(() -> {
java.util.Random r = new java.util.Random();
for (int i = 0; i < OPS; i++) {
int k = r.nextInt(100);
if (r.nextBoolean()) shared.put(k, k * 2);
else shared.get(k);
}
});
ts[t].start();
}
for (Thread th : ts) th.join();
System.out.println("final size = " + shared.size() + " (must be <= 50)");
System.out.println("done: no exception, list stayed consistent");
}
}
Run it:
java LRUCacheDemo.java
Output (Part 1 is deterministic; Part 2's final size is always ≤ 50):
== Part 1: eviction & recency ==
get(1) = 10
get(2) = -1
get(3) = 30
get(1) = 11
size = 2
== Part 2: 8 threads hammering, no corruption ==
final size = 50 (must be <= 50)
done: no exception, list stayed consistent
Part 1 proves the recency logic: get(1) makes key 1 most-recent, so the next put(3) evicts key 2 (the LRU), not key 1. Part 2 runs 400,000 mixed operations across eight threads; because one lock guards each whole operation, the map and list never drift apart.
Revision cheat sheet
The whole design, distilled — read this to reconstruct it.
The core design
- HashMap + doubly-linked list. Map:
key → node, O(1) lookup. List: recency order, O(1) reorder and eviction. Together every op is O(1). - Map stores node references, so you reach a node by key and splice it out directly. This is why not to use Java's
LinkedList(its remove is O(n)). - Dummy head/tail sentinels — eliminate all edge cases. Head end = most recent; tail end = least recent (
tail.prev= LRU).
The list operations
- Insert = four pointers: point the node at both neighbours, point both neighbours back. Set the old neighbour's link before repointing head. Sentinels never move.
- moveToFront = remove + addFirst — the "mark recently used" operation, used by both
getandput.
get and put
- get: miss → −1; hit → moveToFront, return value.
- put: existing key → update value + moveToFront (no size change); new key + full → evict
tail.prevfrom list AND map, then insert; new key + room → insert. - Eviction removes from BOTH list and map — the node stores its key so
map.remove(lru.key)works. Any access (get or put) counts as "using."
Thread safety
- A
ConcurrentHashMapis not enough — the operation is compound (needs whole-sequence atomicity), and the linked list isn't protected by the map at all. - Use a single lock (
synchronizedon both methods → both lock onthis) around each whole operation. Then a plainHashMapsuffices — one mechanism, not two.
The senior insight
- The single lock serialises reads too. The obvious fix —
ReadWriteLock— doesn't work, becausegetmutates the list (moveToFront), so it's not a true read; two concurrent reads would corrupt the list. - Real optimisations: segmented locking, or approximate LRU that doesn't reorder on every read (Caffeine's approach). In production:
LinkedHashMapor Caffeine, not a hand-roll.
The cache is a hash map for lookup and a doubly-linked list for order, joined so both get and put stay O(1). The concurrency twist is that its reads write — which is the detail worth carrying into an interview.