1. Architectural Requirements & Data Structure Selection
An LRU (Least Recently Used) cache must support two operations in strict $O(1)$ time complexity: `get(key)` and `put(key, value)`. When capacity is reached, the least recently accessed item is evicted.
A standard Array or LinkedList requires $O(N)$ lookup. A HashMap provides $O(1)$ lookup but lacks ordering. By combining a HashMap with a Doubly Linked List (DLL), we achieve $O(1)$ access, instant node removal, and fast head insertion.
2. Anatomy of the Doubly Linked List + HashMap
The DLL maintains dummy `head` and `tail` sentinel nodes to eliminate edge-case null checks. The HashMap stores keys mapped directly to DLL `Node` references.
When `get(key)` is called, the node is decoupled from its current DLL position and spliced directly behind `head`. When `put()` exceeds capacity, the node right before `tail` is removed from both DLL and Map in $O(1)$ steps.
3. Production Code Implementation
Here is the complete, high-performance implementation in TypeScript:
class DNode<K, V> {
key: K; val: V;
prev: DNode<K, V> | null = null;
next: DNode<K, V> | null = null;
constructor(key: K, val: V) { this.key = key; this.val = val; }
}
export class LRUCache<K, V> {
private capacity: number;
private map = new Map<K, DNode<K, V>>();
private head: DNode<K, V>;
private tail: DNode<K, V>;
constructor(capacity: number) {
this.capacity = capacity;
this.head = new DNode<K, V>(null as any, null as any);
this.tail = new DNode<K, V>(null as any, null as any);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public get(key: K): V | undefined {
const node = this.map.get(key);
if (!node) return undefined;
this.moveToHead(node);
return node.val;
}
public put(key: K, value: V): void {
if (this.map.has(key)) {
const node = this.map.get(key)!;
node.val = value;
this.moveToHead(node);
return;
}
if (this.map.size >= this.capacity) {
const lru = this.tail.prev!;
this.removeNode(lru);
this.map.delete(lru.key);
}
const newNode = new DNode(key, value);
this.addNode(newNode);
this.map.set(key, newNode);
}
private addNode(node: DNode<K, V>) {
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
private removeNode(node: DNode<K, V>) {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private moveToHead(node: DNode<K, V>) {
this.removeNode(node);
this.addNode(node);
}
}Model this architecture on the HLDForge Canvas
Turn static box diagrams into living, collaborative systems. Drag and drop microservices, Kafka clusters, and cache tiers. Run automated SPOF detection and STRIDE threat modeling in real time.
Written by HLDForge Architecture Team
Lead Systems Software Engineer
The HLDForge Architecture Team publishes practical engineering guides, real-world case studies, and high-concurrency blueprints to help engineers build scalable and fault-tolerant software.