Table of Contents
LRU caching
class MyNode {
key: number;
value: number;
prev: MyNode | null;
next: MyNode | null;
constructor(key: number, value: number) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
private capacity: number;
private cache: Map<number, MyNode>;
private head: MyNode; // Dummy head (most recently used)
private tail: MyNode; // Dummy tail (least recently used)
constructor(capacity: number) {
this.capacity = capacity;
this.cache = new Map();
this.head = new MyNode(0, 0); // Dummy head
this.tail = new MyNode(0, 0); // Dummy tail
this.head.next = this.tail;
this.tail.prev = this.head;
}
// Helper function to remove a node from the linked list
private remove(node: MyNode): void {
const prev = node.prev!;
const next = node.next!;
prev.next = next;
next.prev = prev;
}
// Helper function to insert a node at the head (most recently used)
private insert(node: MyNode): void {
const next = this.head.next!; // old MRU
this.head.next = node; // new MRU
node.prev = this.head;
node.next = next;
next.prev = node;
}
// Get the value for a key
get(key: number): number {
if (this.cache.has(key)) {
const node = this.cache.get(key)!;
this.remove(node); // Remove from current position
this.insert(node); // Move to head (most recently used)
return node.value;
}
return -1; // Key not found
}
// Add or update a key-value pair
put(key: number, value: number): void {
if (this.cache.has(key)) {
// If key exists, update its value and move it to the head
const node = this.cache.get(key)!;
node.value = value;
this.remove(node);
this.insert(node);
} else {
// If key doesn't exist, create a new node
const newNode = new MyNode(key, value);
this.cache.set(key, newNode);
this.insert(newNode);
// If cache exceeds capacity, remove the least recently used node
if (this.cache.size > this.capacity) {
const lruNode = this.tail.prev!; // MyNode before the dummy tail
this.remove(lruNode); // Remove from the list
this.cache.delete(lruNode.key); // Remove from the cache
}
}
}
}
// Example usage:
const lruCache = new LRUCache(2);
lruCache.put(1, 1); // Cache is {1=1}
lruCache.put(2, 2); // Cache is {1=1, 2=2}
console.log(lruCache.get(1)); // Returns 1 (Cache is {2=2, 1=1})
lruCache.put(3, 3); // Evicts key 2, Cache is {1=1, 3=3}
console.log(lruCache.get(2)); // Returns -1 (not found)
lruCache.put(4, 4); // Evicts key 1, Cache is {3=3, 4=4}
console.log(lruCache.get(1)); // Returns -1 (not found)
console.log(lruCache.get(3)); // Returns 3 (Cache is {4=4, 3=3})
console.log(lruCache.get(4)); // Returns 4 (Cache is {3=3, 4=4})
Why use dummy nodes head and tail?
- Use dummy node
this.head
andthis.tail
to reducee edge case when head or tail is null. - Can easily retrieve MRU by
this.head.next
and LRU bythis.tail.prev
Mental model when moving around nodes in doubly linked list
private remove(node: MyNode): void {
const prev = node.prev!;
const next = node.next!;
prev.next = next;
next.prev = prev;
}
- Connect the prev and next of the target node
- while the target node still linking its prev and next
- Detach the target node from its prev and next
haochen xu