How To Implement LRU Cache In JavaScript In 28 Lines Or Less

LRU stands for Least Recently Used. It is a cache algorithm that is used to determine which elements should be discarded from memory when the cache is full.

The most basic LRU algorithm would simply check the last time a given value was accessed and keep the least recently used element. However, this can lead to poor performance as it does not take into account other factors such as the frequency of access or how recently an item was used.

LRU Cache implementation is very easy and simple. In this post we will implement a LRU Cache using a single Map to store. The steps required to implement the LRU Cache are as follows:

• Initialize capacity
• Use Map to store key and value
• After get, move node to head
• After put, if key exist, update node value and move it to head
• If key does not exist, check size. if size is equal or greater than capacity, remove the tail. add the new node to head. increase the size by one.

class LRUCache {
  private capacity: number;
  private map: Map<number, number>;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key: number): number {
    if (this.map.has(key)) {
      const value = this.map.get(key);
      this.map.delete(key);
      this.map.set(key, value);
      return value;
    }
    return -1;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
  }
}

Output

//Example
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // returns 1
cache.put(3, 3); // evicts key 2
console.log(cache.get(2)); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
console.log(cache.get(1)); // returns -1 (not found)
console.log(cache.get(3)); // returns 3
console.log(cache.get(4)); // returns 4

Step-by-Step Execution:

1. Initial Setup:

   • Create an LRUCache instance with a capacity of 3.

2. Put Operations:

   • put(1, 1): Cache contains {1=1}.
   • put(2, 2): Cache contains {1=1, 2=2}.
   • put(3, 3): Cache contains {1=1, 2=2, 3=3}.

3. Get Operation:

   • get(1): Retrieves 1 and marks 1 as the most recently used. Cache becomes {2=2, 3=3, 1=1}.

4. Put Operation:

   • put(4, 4): Cache exceeds capacity, evicts the least recently used item (2). Cache becomes {3=3, 1=1, 4=4}.

5. Get Operation:

   • get(2): 2 is not found, returns -1.

6. Get Operation:

   • get(3): Retrieves 3 and marks 3 as the most recently used. Cache becomes {1=1, 4=4, 3=3}.

7. Put Operation:

   • put(5, 5): Cache exceeds capacity, evicts the least recently used item (1). Cache becomes {4=4, 3=3, 5=5}.

8. Get Operations:

   • get(1): 1 is not found, returns -1.
   • get(4): Retrieves 4 and marks 4 as the most recently used. Cache becomes {3=3, 5=5, 4=4}.

This example illustrates how the LRUCache maintains the order of usage and ensures that the most recently used items are retained while evicting the least recently used ones when the capacity is exceeded.