LRU Cache

The famous DSA problem and the LLD version of it ask different questions. The DSA version wants an algorithm that hits O(1) per operation. The LLD version wants that algorithm wrapped in a class whose public surface never leaks the doubly linked list it's built on - callers only ever see keys and values.

Requirements

Functional

• get(key) returns the value for key, or a not-found signal if it isn't cached, and counts as a "use" of that key.
• put(key, value) inserts or updates an entry and counts as a "use" of that key. If the cache is at capacity and a new key needs to be inserted, the least-recently-used entry is evicted first.

Non-functional

• Both operations run in O(1) time regardless of how many entries the cache holds.
• The eviction bookkeeping is an internal detail - nothing about LRUCache's public methods should hint that a linked list is involved.

Design

LRUCache holds two collaborators that solve the two halves of the problem separately: a hash map for O(1) lookup by key, and a doubly linked list ordered by recency for O(1) reordering and eviction. Neither one alone gets you both properties - a map alone can't tell you what's least recently used without a scan, and a list alone can't find a key without one.

1. 1The client only ever sees keys and values - never a node or a pointer.
2. 2The map answers in O(1) whether the key exists and, if so, which node holds it.
3. 3A hit promotes that node to most-recently-used by splicing it to the front.
4. 4Same entry point handles both a fresh key and an update to an existing one.
5. 5Only triggered if the cache is full and the key is new - the tail node is removed first.
6. 6The evicted node is dropped from the map too, or a stale entry would sit there forever.

The map stores key -> Node, never key -> value directly, because the node is also what lets the cache splice an entry out of the middle of the list in O(1) the moment it's touched again.

Class diagram

LRUCache is the only public surface. Node and the linked-list pointers never leave it.

Code

import java.util.HashMap;

import java.util.Map;

 

class Node<K, V> {

K key;

V value;

Node<K, V> prev, next;

 

Node(K key, V value) {

this.key = key;

this.value = value;

}

}

 

class LRUCache<K, V> {

private final int capacity;

private final Map<K, Node<K, V>> lookup = new HashMap<>();

private final Node<K, V> head = new Node<>(null, null); // sentinel, most-recent side

private final Node<K, V> tail = new Node<>(null, null); // sentinel, least-recent side

 

LRUCache(int capacity) {

this.capacity = capacity;

head.next = tail;

tail.prev = head;

}

 

V get(K key) {

Node<K, V> node = lookup.get(key);

if (node == null) return null;

moveToFront(node);

return node.value;

}

 

void put(K key, V value) {

Node<K, V> existing = lookup.get(key);

if (existing != null) {

existing.value = value;

moveToFront(existing);

return;

}

if (lookup.size() == capacity) {

Node<K, V> lru = tail.prev;

removeNode(lru);

lookup.remove(lru.key);

}

Node<K, V> node = new Node<>(key, value);

addToFront(node);

lookup.put(key, node);

}

 

private void moveToFront(Node<K, V> node) {

removeNode(node);

addToFront(node);

}

 

private void removeNode(Node<K, V> node) {

node.prev.next = node.next;

node.next.prev = node.prev;

}

 

private void addToFront(Node<K, V> node) {

node.next = head.next;

node.prev = head;

head.next.prev = node;

head.next = node;

}

}

Design decisions

• A map plus a doubly linked list, not a map with timestamps. Timestamps would need a scan over every entry to find the oldest one - O(n) eviction. A list ordered by recency turns "find the least-recently-used entry" into "look at the tail," which is O(1) no matter how large the cache gets.
• Doubly linked, not singly linked. Moving a middle node to the front on every get requires detaching it from its current neighbors in one step. A singly linked list would need to walk from the head to find a node's predecessor first, which reintroduces the O(n) cost this design exists to avoid.
• Sentinel head and tail nodes instead of nullable pointers. Every insert and remove path becomes a two-line splice with no if (head == null) special case for an empty list or a single-element list - the sentinels guarantee there is always a real node on both sides of any real node.
• Node is never returned from a public method. get and put only ever hand back or accept plain values - the fact that eviction order is implemented as a linked list is free to change later (a skip list, a heap keyed by last-used time) without touching a single caller.
• What's missing for a real system: this design isn't thread-safe - concurrent get/put calls need a lock around the map-and-list pair, or a striped-lock scheme to avoid one global bottleneck. A production cache would likely also want a per-entry TTL and size-based (not just count-based) eviction, neither of which this page's scope calls for.