A login service keeps the last N session payloads in memory so the next request does not hit Redis. Capacity is 10_000. Request 10_001 arrives. Which session do you drop?
If you drop the oldest insert, a user who logged in first and is still clicking gets evicted while a bot that signed up a second ago stays. LRU’s answer: drop the session nobody has touched. That policy is cheap only when two layouts share the work. From the series hub: a data structure is a layout that makes some operations cheap and others expensive. LRU is the job where one layout is never enough.
This post is the machine: why a list alone or a map alone fails, dummy head and tail, get / put / evict, and LinkedHashMap with accessOrder. Terms such as expected O(1), amortized, and “splice is cheap when you already hold the node” live on the Data Structures Roadmap. This page does not re-teach them.
Why one layout is not enough
A cache has three hot operations, not one:
| Operation | What must be cheap |
|---|---|
get(key) | Find the value, and mark that key as most recently used |
put(key, value) | Insert or refresh, then mark most recently used |
| Evict | Drop the least recently used entry when you are over capacity |
A doubly linked list can evict from one end in O(1) if you keep a tail pointer. Finding a key still walks the list. Every get becomes a scan, then a splice. At 10_000 sessions that is a tax on the hot path.
// list alone: eviction is cheap; finding the key is not
V get(LinkedList<Entry<K, V>> order, K key) {
for (Entry<K, V> e : order) { // O(n)
if (e.key().equals(key)) {
order.remove(e); // another walk unless you hold the node
order.addFirst(e);
return e.value();
}
}
return null;
}A HashMap makes get and put expected O(1). It has no recency order. Eviction means scanning every entry for the oldest timestamp — or keeping a second structure you then have to keep in sync.
// map alone: lookup is cheap; "who is least recent?" is a scan
K pickVictim(Map<K, Timed<V>> store) {
K victim = null;
long oldest = Long.MAX_VALUE;
for (var e : store.entrySet()) { // O(n) on every eviction
if (e.getValue().lastAccess() < oldest) {
oldest = e.getValue().lastAccess();
victim = e.getKey();
}
}
return victim;
}List alone cannot find. Map alone cannot rank. The interview trick — and the production layout — is to let each structure do only the job it is cheap at.
The two-layout machine
Give every entry a node. The hash map stores key → node. The doubly linked list stores those same nodes in recency order. Lookup is a map hit. Reordering is a splice, and you already hold the node.
map: A -> nodeA B -> nodeB C -> nodeC
list: head <-> [C] <-> [A] <-> [B] <-> tail
most recent least recentC was touched last. B is the eviction candidate. After get(A), the list becomes head <-> [A] <-> [C] <-> [B] <-> tail. The map does not change shape — only the node’s prev / next pointers do.
Dummy head and tail sentinels sit at both ends so every real node always has neighbors. Insert after head and evict tail.prev never special-case an empty list or a single remaining entry.
final 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;
}
}
void wireSentinels(Node<K, V> head, Node<K, V> tail) {
head.next = tail;
tail.prev = head;
}Note: A singly linked list is the wrong half. Moving a node to the front needs the predecessor. A doubly linked list holds it. That is the glossary line from the hub: linked layouts win at splicing when you already hold the node. The map is how you hold it without walking.
Attach, detach, move to front
Three pointer edits. Every get and put is some combination of these. The sentinels keep the nulls out of the hot path.
void attachAfterHead(Node<K, V> head, Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
void detach(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
}
void moveToFront(Node<K, V> head, Node<K, V> node) {
detach(node);
attachAfterHead(head, node);
}After attachAfterHead, the node is most recently used. After detach of tail.prev, that node is gone from the list and ready to leave the map.
get, put, evict
get is a map lookup, then a move. A miss does not invent an entry — this is a cache, not a loader.
V get(Map<K, Node<K, V>> index, Node<K, V> head, K key) {
Node<K, V> node = index.get(key);
if (node == null) {
return null;
}
moveToFront(head, node);
return node.value;
}put refreshes an existing key in place, or inserts a new node after head. If the map is now over capacity, evict the node before tail.
void put(Map<K, Node<K, V>> index, Node<K, V> head, Node<K, V> tail,
int capacity, K key, V value) {
Node<K, V> node = index.get(key);
if (node != null) {
node.value = value;
moveToFront(head, node);
return;
}
Node<K, V> fresh = new Node<>(key, value);
index.put(key, fresh);
attachAfterHead(head, fresh);
if (index.size() > capacity) {
evictLru(index, tail);
}
}
void evictLru(Map<K, Node<K, V>> index, Node<K, V> tail) {
Node<K, V> lru = tail.prev;
detach(lru);
index.remove(lru.key);
}Both sides stay in lockstep: a node lives in the map if and only if it lives between the sentinels. Evict from the list, then from the map, using the node’s own key. Never search.
A capacity-2 trace makes the pointer story concrete:
put(A, 1) list: head <-> A <-> tail
put(B, 2) list: head <-> B <-> A <-> tail
get(A) list: head <-> A <-> B <-> tail // A is MRU
put(C, 3) evict B // B was LRU
list: head <-> C <-> A <-> tail
get(B) missB was inserted more recently than A, then A was read. Recency is last touch, not last insert. That is the whole policy.
Complexity — what you actually pay
Read this as a shopping list, the way the hub teaches. Hash-map cost is expected O(1) with a decent hash and a load factor you respect — not a law of physics.
Structure: LRU (hash map + doubly linked list)
get(key) expected O(1) — map hit, then splice
put(key) expected O(1) — map hit or insert, splice, maybe evict
evict O(1) — tail.prev is the victim
space O(capacity) — one node and one map entry per keyA heap of timestamps would make eviction O(log n) and still need a map to find the heap node. LRU does not need “next best” — it needs “the end of this list.” A heap is the wrong specialized layout for this job.
The JDK shortcut: LinkedHashMap with accessOrder
LinkedHashMap is this machine: a hash table whose entries are also a doubly linked list. The third constructor argument flips the list from insertion order to access order. get and put then move the touched entry to the most-recent end. Override removeEldestEntry to drop the other end when you are over capacity.
public final class SessionCache<K, V> extends LinkedHashMap<K, V> {
private final int maxEntries;
public SessionCache(int maxEntries) {
super(maxEntries, 0.75f, true); // accessOrder = true
this.maxEntries = maxEntries;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxEntries;
}
}true is the whole trick. false (the default) is insertion order — a queue of first-seen keys, not LRU. removeEldestEntry runs after an insert; returning true removes the eldest entry, which in access order is the least recently used.
Note: The first constructor argument is the hash table’s initial capacity, not a hard LRU cap. The cap lives in removeEldestEntry. Size the table so you do not rehash on every warm-up if maxEntries is large; the eviction hook is what actually bounds the map.
get on an access-ordered LinkedHashMap is a structural modification. Iterators and concurrent readers will notice. That is correct LRU behavior, not a bug — and it is why this type is a single-threaded cache, not a shared one.
When not to use LRU
Skip the machine — hand-rolled or LinkedHashMap — when the job is a different job:
- Tiny
n. A map of twelve feature flags plus a scan on eviction is clearer than sentinels. Constant-time pointer edits do not matter until the scan shows up in a profile. - You need LFU, not LRU. Recency is not frequency. A key hit once a second ago evicts a key hit a thousand times an hour ago. Least-frequently-used tracks counts (often with aging). Do not rename an LRU and hope.
- Concurrent cache is a different product.
LinkedHashMapis not thread-safe.Collections.synchronizedMapserializes every call, andgetstill mutates order under the lock. A production concurrent cache — Caffeine, Guava Cache, a store with segmented locks, stats, and refresh — is designed for that. Do not ship a synchronized LRU and call it Redis.
TTL-only expiry (drop after thirty minutes, regardless of hits) is also a different policy. You can combine TTL with LRU, but the clock is a second index, not a recency list.
Cheat sheet
Job: bounded store; evict least recently touched
Machine: HashMap key -> node + DLL in recency order
Sentinels: dummy head (MRU side), dummy tail (LRU side)
get: map hit, move node after head
put: refresh or insert after head; if over cap, evict tail.prev
Evict: detach LRU node, map.remove(node.key)
JDK: new LinkedHashMap<>(n, 0.75f, true) + removeEldestEntry
accessOrder: true = LRU; false = insertion order
Hash cost: expected O(1), not a lawDo:
- Let the map find the node and the list rank it. One structure each.
- Keep sentinels so insert and evict never branch on “empty” or “one node.”
- Reach for
LinkedHashMapwithaccessOrderunless you are teaching the pointers or need a hook the JDK type does not have.
Don’t:
- Walk a list to implement
get, or scan a map to pick a victim. - Treat insertion-ordered
LinkedHashMapas LRU. - Use a synchronized
LinkedHashMapas a multi-threaded cache and stop there.
Wrap-up
LRU is not a clever eviction formula. It is two layouts sharing one set of nodes: the hash map answers “where is this key,” the doubly linked list answers “what have we touched least.” Dummy sentinels keep the splices boring. get and put move a node to the head; overflow detaches tail.prev and drops that key from the map.
In Java, LinkedHashMap(n, 0.75f, true) plus removeEldestEntry is that machine. Use it when a single-threaded bounded cache is the whole product. Reach for a real concurrent cache when threads share the map. Reach for LFU — or a scan — when recency is the wrong ranking.
The glossary, the JDK map, and the rest of the series index live on the Data Structures Roadmap. This page is one specialized row on that path: the job a hash table and a list cannot do alone, and the two-layout answer that makes all three operations expected O(1).