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

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.