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:

1. Array-based LRU
2. Hash Table + Doubly Linked List LRU
3. JavaScript Map-based LRU

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.