1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 * Doubly Linked List Node for LRU Cache
 * 
 * Each node stores:
 * - key: Required for removing from HashMap during eviction
 * - value: The actual cached data
 * - prev/next: Pointers for doubly linked list structure
 * 
 * @template K - Key type (typically number or string)
 * @template V - Value type (the cached data)
 */
class LRUNode<K, V> {
    key: K;
    value: V;
    prev: LRUNode<K, V> | null;
    next: LRUNode<K, V> | null;
 
    constructor(key: K, value: V) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}
 
/**
 * Alternative: Using a simple object for languages without classes
 * This pattern works well in JavaScript interviews
 */
function createNode<K, V>(key: K, value: V): LRUNode<K, V> {
    return {
        key,
        value,
        prev: null,
        next: null
    };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/**
 * LRU Cache Implementation
 * 
 * Combines a HashMap with a Doubly Linked List to achieve:
 * - O(1) get operations
 * - O(1) put operations
 * - O(1) eviction of least recently used item
 * 
 * @template K - Key type
 * @template V - Value type
 */
class LRUCache<K, V> {
    // === PRIVATE MEMBERS ===
    
    /**
     * Maps keys to their corresponding nodes in the linked list.
     * Enables O(1) lookup of any cache entry by key.
     */
    private cache: Map<K, LRUNode<K, V>>;
    
    /**
     * Maximum number of items the cache can hold.
     * When exceeded, the LRU item is evicted.
     */
    private readonly capacity: number;
    
    /**
     * Sentinel node marking the head (MRU end) of the list.
     * head.next points to the most recently used real node.
     * Note: head itself is never removed or replaced.
     */
    private readonly head: LRUNode<K, V>;
    
    /**
     * Sentinel node marking the tail (LRU end) of the list.
     * tail.prev points to the least recently used real node.
     * Note: tail itself is never removed or replaced.
     */
    private readonly tail: LRUNode<K, V>;
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be positive");
        }
        
        this.capacity = capacity;
        this.cache = new Map();
        
        // Initialize sentinel nodes with dummy values
        // These are structural markers, not real cache entries
        this.head = new LRUNode<K, V>(null as unknown as K, null as unknown as V);
        this.tail = new LRUNode<K, V>(null as unknown as K, null as unknown as V);
        
        // Connect sentinels: head <-> tail
        // This represents an empty cache
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    /**
     * Returns the current number of items in the cache.
     */
    get size(): number {
        return this.cache.size;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// Inside LRUCache class:
 
/**
 * Removes a node from its current position in the linked list.
 * 
 * This does NOT remove from the hash map — only from the list.
 * After this call, the node is "floating" (not in any list).
 * 
 * Time: O(1) — just 4 pointer updates
 * 
 * @param node - The node to remove (must be a real node, not a sentinel)
 */
private removeNode(node: LRUNode<K, V>): void {
    // Get neighbors
    const prevNode = node.prev!;
    const nextNode = node.next!;
    
    // Bypass this node: prev <-> next (cutting out 'node')
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
    
    // Clear the node's pointers (optional but good practice)
    // Helps garbage collection and makes debugging easier
    node.prev = null;
    node.next = null;
}
 
/**
 * Inserts a node right after the head sentinel (making it MRU).
 * 
 * The node should be a "floating" node (not currently in any list).
 * After this call, the node is the first real node in the list.
 * 
 * Time: O(1) — just 4 pointer updates
 * 
 * @param node - The node to insert (should not currently be in the list)
 */
private addToHead(node: LRUNode<K, V>): void {
    // Current first real node (might be tail if list is empty)
    const firstNode = this.head.next!;
    
    // Insert between head and firstNode
    // head <-> node <-> firstNode
    node.prev = this.head;
    node.next = firstNode;
    
    // Update neighbors to point to the new node
    this.head.next = node;
    firstNode.prev = node;
}
 
/**
 * Moves an existing node to the head (making it MRU).
 * 
 * Combines removeNode + addToHead into a single logical operation.
 * Used when a cache hit occurs (get or put on existing key).
 * 
 * Time: O(1)
 * 
 * @param node - The node to move (must already be in the list)
 */
private moveToHead(node: LRUNode<K, V>): void {
    this.removeNode(node);
    this.addToHead(node);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 * Retrieves the value associated with the given key.
 * 
 * If the key exists:
 * - Returns the associated value
 * - Marks the key as most recently used (moves to head)
 * 
 * If the key doesn't exist:
 * - Returns null (or -1 for LeetCode-style int caches)
 * 
 * Time Complexity: O(1) average
 * - Hash map lookup: O(1) average
 * - Move to head: O(1) always
 * 
 * @param key - The key to look up
 * @returns The value if found, null otherwise
 */
get(key: K): V | null {
    // Step 1: Hash map lookup — O(1)
    const node = this.cache.get(key);
    
    // Step 2: Cache miss — key not found
    if (node === undefined) {
        return null;
    }
    
    // Step 3: Cache hit — update recency
    // Move this node to the head (most recently used position)
    this.moveToHead(node);
    
    // Step 4: Return the cached value
    return node.value;
}
 
/**
 * LeetCode-style get() that returns -1 instead of null.
 * Use this for interview problems with integer values.
 */
getLeetCode(key: K): V | -1 {
    const node = this.cache.get(key);
    if (node === undefined) {
        return -1;
    }
    this.moveToHead(node);
    return node.value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/**
 * Inserts or updates a key-value pair in the cache.
 * 
 * If the key already exists:
 * - Updates the value
 * - Marks as most recently used
 * 
 * If the key is new:
 * - If at capacity, evicts the LRU item first
 * - Inserts the new key-value pair
 * - Marks as most recently used
 * 
 * Time Complexity: O(1) average
 * - Hash map operations: O(1) average
 * - Linked list operations: O(1) always
 * 
 * @param key - The key to insert or update
 * @param value - The value to associate with the key
 */
put(key: K, value: V): void {
    // Step 1: Check if key already exists
    const existingNode = this.cache.get(key);
    
    if (existingNode !== undefined) {
        // === CASE A: UPDATE EXISTING KEY ===
        // Update the value in place
        existingNode.value = value;
        
        // Move to head (most recently used)
        this.moveToHead(existingNode);
        
        // Done — no size change, no eviction needed
        return;
    }
    
    // === CASE B: INSERT NEW KEY ===
    
    // Step 2: Check if eviction is needed
    if (this.cache.size >= this.capacity) {
        // Evict the least recently used item (node before tail sentinel)
        const lruNode = this.tail.prev!;
        
        // CRITICAL: Remove from BOTH structures
        // First, remove from linked list
        this.removeNode(lruNode);
        
        // Then, remove from hash map (using the key stored in the node)
        this.cache.delete(lruNode.key);
    }
    
    // Step 3: Create and insert new node
    const newNode = new LRUNode(key, value);
    
    // Add to hash map
    this.cache.set(key, newNode);
    
    // Add to linked list head (most recently used position)
    this.addToHead(newNode);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

/**
 * Complete LRU Cache Implementation
 * 
 * Time Complexity: O(1) for both get and put (amortized)
 * Space Complexity: O(capacity)
 * 
 * This implementation uses:
 * - HashMap for O(1) key lookup
 * - Doubly Linked List for O(1) recency updates
 * - Sentinel nodes for simplified edge case handling
 */
 
class LRUNode<K, V> {
    key: K;
    value: V;
    prev: LRUNode<K, V> | null = null;
    next: LRUNode<K, V> | null = null;
 
    constructor(key: K, value: V) {
        this.key = key;
        this.value = value;
    }
}
 
class LRUCache<K, V> {
    private cache: Map<K, LRUNode<K, V>>;
    private readonly capacity: number;
    private readonly head: LRUNode<K, V>;
    private readonly tail: LRUNode<K, V>;
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be positive");
        }
        
        this.capacity = capacity;
        this.cache = new Map();
        
        // Sentinel nodes
        this.head = new LRUNode<K, V>(null as unknown as K, null as unknown as V);
        this.tail = new LRUNode<K, V>(null as unknown as K, null as unknown as V);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
 
    get size(): number {
        return this.cache.size;
    }
 
    get(key: K): V | null {
        const node = this.cache.get(key);
        if (!node) return null;
        
        this.moveToHead(node);
        return node.value;
    }
 
    put(key: K, value: V): void {
        const existingNode = this.cache.get(key);
        
        if (existingNode) {
            existingNode.value = value;
            this.moveToHead(existingNode);
            return;
        }
        
        if (this.cache.size >= this.capacity) {
            const lruNode = this.tail.prev!;
            this.removeNode(lruNode);
            this.cache.delete(lruNode.key);
        }
        
        const newNode = new LRUNode(key, value);
        this.cache.set(key, newNode);
        this.addToHead(newNode);
    }
 
    private removeNode(node: LRUNode<K, V>): void {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }
 
    private addToHead(node: LRUNode<K, V>): void {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next!.prev = node;
        this.head.next = node;
    }
 
    private moveToHead(node: LRUNode<K, V>): void {
        this.removeNode(node);
        this.addToHead(node);
    }
}
 
// Usage example
const cache = new LRUCache<number, number>(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));  // 1
cache.put(3, 3);            // Evicts key 2
console.log(cache.get(2));  // null (was evicted)
console.log(cache.get(3));  // 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/**
 * Comprehensive LRU Cache Test Suite
 */
 
function testLRUCache(): void {
    console.log("Running LRU Cache tests...
");
 
    // Test 1: Basic get/put
    (() => {
        const cache = new LRUCache<number, number>(2);
        cache.put(1, 100);
        cache.put(2, 200);
        console.assert(cache.get(1) === 100, "Test 1.1 failed");
        console.assert(cache.get(2) === 200, "Test 1.2 failed");
        console.log("✓ Test 1: Basic get/put");
    })();
 
    // Test 2: Get nonexistent key
    (() => {
        const cache = new LRUCache<number, number>(2);
        console.assert(cache.get(999) === null, "Test 2.1 failed");
        cache.put(1, 100);
        console.assert(cache.get(999) === null, "Test 2.2 failed");
        console.log("✓ Test 2: Get nonexistent key");
    })();
 
    // Test 3: Update existing key (no eviction)
    (() => {
        const cache = new LRUCache<number, number>(2);
        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(1, 111);  // Update, not new insert
        console.assert(cache.get(1) === 111, "Test 3.1: Value not updated");
        console.assert(cache.get(2) === 200, "Test 3.2: Key 2 incorrectly evicted");
        console.log("✓ Test 3: Update existing key");
    })();
 
    // Test 4: Eviction when at capacity
    (() => {
        const cache = new LRUCache<number, number>(2);
        cache.put(1, 100);
        cache.put(2, 200);
        cache.put(3, 300);  // Should evict key 1 (LRU)
        console.assert(cache.get(1) === null, "Test 4.1: Key 1 not evicted");
        console.assert(cache.get(2) === 200, "Test 4.2: Key 2 incorrectly evicted");
        console.assert(cache.get(3) === 300, "Test 4.3: Key 3 not present");
        console.log("✓ Test 4: Eviction at capacity");
    })();
 
    // Test 5: Get() updates recency (prevents eviction)
    (() => {
        const cache = new LRUCache<number, number>(2);
        cache.put(1, 100);
        cache.put(2, 200);
        cache.get(1);       // Touch key 1 → now key 2 is LRU
        cache.put(3, 300);  // Should evict key 2, not key 1
        console.assert(cache.get(1) === 100, "Test 5.1: Key 1 incorrectly evicted");
        console.assert(cache.get(2) === null, "Test 5.2: Key 2 not evicted");
        console.assert(cache.get(3) === 300, "Test 5.3: Key 3 not present");
        console.log("✓ Test 5: Get() updates recency");
    })();
 
    // Test 6: Capacity 1
    (() => {
        const cache = new LRUCache<number, number>(1);
        cache.put(1, 100);
        console.assert(cache.get(1) === 100, "Test 6.1 failed");
        cache.put(2, 200);  // Immediate eviction of key 1
        console.assert(cache.get(1) === null, "Test 6.2: Key 1 not evicted");
        console.assert(cache.get(2) === 200, "Test 6.3: Key 2 not present");
        console.log("✓ Test 6: Capacity 1");
    })();
 
    // Test 7: LeetCode example
    (() => {
        const cache = new LRUCache<number, number>(2);
        cache.put(1, 1);
        cache.put(2, 2);
        console.assert(cache.get(1) === 1, "Test 7.1 failed");
        cache.put(3, 3);    // evicts key 2
        console.assert(cache.get(2) === null, "Test 7.2 failed");
        cache.put(4, 4);    // evicts key 1
        console.assert(cache.get(1) === null, "Test 7.3 failed");
        console.assert(cache.get(3) === 3, "Test 7.4 failed");
        console.assert(cache.get(4) === 4, "Test 7.5 failed");
        console.log("✓ Test 7: LeetCode example");
    })();
 
    console.log("
✓ All tests passed!");
}
 
testLRUCache();