Understanding LRU Cache: Principles, Applications, and Coding Implementation

What is LRU Algorithm?

The LRU (Least Recently Used) algorithm is a widely used cache replacement policy that removes the least recently accessed item when the cache reaches its limit. It is commonly applied in cache management, operating system memory management, and database query optimization.

Implementation Approaches

Here's the complete LRU Cache implementation using three different methods:

Array-based LRU
Hash Table + Doubly Linked List LRU
JavaScript Map-based LRU

1 // 1. Array-based LRU Cache Implementation
2 class LRUCacheArray {
3     private cache: Map<number, number>;
4     private capacity: number;
5 
6     constructor(capacity: number) {
7         this.capacity = capacity;
8         this.cache = new Map();
9     }
10 
11     get(key: number): number {
12         if (!this.cache.has(key)) return -1;
13         const value = this.cache.get(key);
14         this.cache.delete(key);
15         this.cache.set(key, value!);
16         return value!;
17     }
18 
19     put(key: number, value: number): void {
20         if (this.cache.has(key)) this.cache.delete(key);
21         else if (this.cache.size >= this.capacity) this.cache.delete(this.cache.keys().next().value);
22         this.cache.set(key, value);
23     }
24 }
25 
26 // 2. Hash Table + Doubly Linked List LRU Cache Implementation
27 class Node {
28     key: number;
29     value: number;
30     prev: Node | null;
31     next: Node | null;
32     constructor(key: number, value: number) {
33         this.key = key;
34         this.value = value;
35         this.prev = this.next = null;
36     }
37 }
38 
39 class LRUCacheDLL {
40     private capacity: number;
41     private cache: Map<number, Node>;
42     private head: Node;
43     private tail: Node;
44 
45     constructor(capacity: number) {
46         this.capacity = capacity;
47         this.cache = new Map();
48         this.head = new Node(0, 0);
49         this.tail = new Node(0, 0);
50         this.head.next = this.tail;
51         this.tail.prev = this.head;
52     }
53 
54     private remove(node: Node): void {
55         node.prev!.next = node.next;
56         node.next!.prev = node.prev;
57     }
58 
59     private insert(node: Node): void {
60         node.next = this.head.next;
61         node.prev = this.head;
62         this.head.next!.prev = node;
63         this.head.next = node;
64     }
65 
66     get(key: number): number {
67         if (!this.cache.has(key)) return -1;
68         const node = this.cache.get(key)!;
69         this.remove(node);
70         this.insert(node);
71         return node.value;
72     }
73 
74     put(key: number, value: number): void {
75         if (this.cache.has(key)) this.remove(this.cache.get(key)!);
76         if (this.cache.size >= this.capacity) {
77             this.cache.delete(this.tail.prev!.key);
78             this.remove(this.tail.prev!);
79         }
80         const node = new Node(key, value);
81         this.cache.set(key, node);
82         this.insert(node);
83     }
84 }
85 
86 // 3. JavaScript Map-based LRU Cache Implementation
87 class LRUCacheMap {
88     private cache: Map<number, number>;
89     private capacity: number;
90 
91     constructor(capacity: number) {
92         this.capacity = capacity;
93         this.cache = new Map();
94     }
95 
96     get(key: number): number {
97         if (!this.cache.has(key)) return -1;
98         const value = this.cache.get(key)!;
99         this.cache.delete(key);
100         this.cache.set(key, value);
101         return value;
102     }
103 
104     put(key: number, value: number): void {
105         if (this.cache.has(key)) this.cache.delete(key);
106         else if (this.cache.size >= this.capacity) this.cache.delete(this.cache.keys().next().value);
107         this.cache.set(key, value);
108     }
109 }

Explanation:

1. Array-based LRUCache (LRUCacheArray)

Uses a Map to store key-value pairs.
When a key is accessed, it is removed and reinserted to maintain order.
If capacity is exceeded, the least recently used item (first inserted) is deleted.

2. Hash Table + Doubly Linked List (LRUCacheDLL)

Uses a Map for O(1) lookups and a doubly linked list for O(1) insertions/removals.
The most recently used elements are near the head; least used near the tail.
When capacity is exceeded, the least recently used node (tail’s previous) is removed.

3. JavaScript Map-based LRUCache (LRUCacheMap)

Similar to LRUCacheArray, but fully relies on Map to keep order.
Offers slightly better performance than the array-based approach.