A doubly linked list stores a sequence of nodes, with each node referencing both its predecessor and successor. In an LRU cache, it tracks access order: the head identifies the most recently used item, while the tail identifies the least recently used item. section 6.4
Interview scenario
When designing a high-throughput API cache, explain how the list supports eviction and what happens under concurrent access. Multiple threads may reposition or remove nodes simultaneously, causing stale reads or corrupted ordering. Discuss locking, lock-free structures, or sharding as synchronization trade-offs. section 6.4
Listing 6.6 LRU cache implementation in TypeScript
class LRUCache<K, V> {
private cache: Map<K, V>;
private capacity: number;
constructor(capacity: number) {
if (capacity <= 0) {
throw new Error('Capacity must be greater than 0');
}
this.capacity = capacity; #A
this.cache = new Map(); #B
}
get(key: K): V | -1 { #C
if (!this.cache.has(key)) { #D
return -1;
}
const value = this.cache.get(key)!; #E
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key: K, value: V): void { #F
if (this.cache.has(key)) {
this.cache.delete(key); #G
}
this.cache.set(key, value); #H
if (this.cache.size > this.capacity) {
const lruKey = this.cache.keys().next().value!; #I
this.cache.delete(lruKey); #J
}
}
entries(): [K, V][] { #K
return Array.from(this.cache.entries());
}
}
Use the TypeScript LRU implementation to connect access-order updates, capacity checks, and least-recently-used removal to the data structure’s cache role. section 6.4



