ASAPUtils
The design equation
One structure cannot efficiently answer both requirements:
unordered_map/Map: key → node in O(1), but no recency order;- doubly linked list: most-to-least recent order and O(1) removal, but no key lookup.
Combine them. The map stores node references; the list stores the same nodes between most-recent and least-recent sentinels.
Invariant
Every cached key appears exactly once in both the map and the list. The node nearest the head is most recent; the node nearest the tail is least recent.
Every successful get and every put makes that key most recent. Eviction removes tail.prev.
C++ solution
class LRUCache {
int capacity;
list<pair<int,int>> order; // front = most recent
unordered_map<int, list<pair<int,int>>::iterator> at;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (!at.count(key)) return -1;
auto it = at[key];
int value = it->second;
order.splice(order.begin(), order, it);
return value;
}
void put(int key, int value) {
if (at.count(key)) order.erase(at[key]);
order.push_front({key, value});
at[key] = order.begin();
if ((int)order.size() > capacity) {
int lruKey = order.back().first;
order.pop_back();
at.erase(lruKey);
}
}
};
JavaScript solution with explicit nodes
class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.nodes = new Map();
this.head = new Node();
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
}
remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
addMostRecent(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.nodes.has(key)) return -1;
const node = this.nodes.get(key);
this.remove(node);
this.addMostRecent(node);
return node.value;
}
put(key, value) {
if (this.nodes.has(key)) {
const old = this.nodes.get(key);
this.remove(old);
this.nodes.delete(key);
}
const node = new Node(key, value);
this.addMostRecent(node);
this.nodes.set(key, node);
if (this.nodes.size > this.capacity) {
const lru = this.tail.prev;
this.remove(lru);
this.nodes.delete(lru.key);
}
}
}
Why it works
The map and list invariant is restored after every operation. Moving a hit to the front records its new recency. If insertion creates capacity+1 items, the back real node is provably the least recently used and is removed from both representations.
Complexity
Hash operations are O(1) average. Each list action changes a constant number of pointers, so get and
put are O(1) average. At most capacity real nodes and map entries use O(capacity) space.
Traps
- Removing a node from the list but not the map, or vice versa.
- Updating an existing key’s value without making it most recent.
- Evicting the tail sentinel instead of
tail.prev. - Using an array for recency, which makes middle removal O(n).
Blank re-solve prompt
Write two helper operations first: remove(node) and addMostRecent(node). Draw their four pointer changes, then implement get and put using only those helpers.