Data Structures & Cache

JavaScript LRU Cache (Least Recently Used)

Implement a high-performance Least Recently Used (LRU) Cache in JavaScript using the Map structure with O(1) get and put operations.

JavaScript Source Code

Editable code sample with line numbers

JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

get(key) {
    if (!this.cache.has(key)) return -1;
    // Refresh access: remove and re-insert to end of Map insertion order
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }

put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // Evict least recently used (first key in Map iterator)
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

// Test LRU Cache
const lru = new LRUCache(2);
lru.put(1, "Data A");
lru.put(2, "Data B");
console.log("Get Key 1:", lru.get(1)); // Access 1, making 2 the LRU
lru.put(3, "Data C");                  // Evicts Key 2

console.log("Get Key 2 (Evicted):", lru.get(2)); // Returns -1
console.log("Get Key 3:", lru.get(3));          // Returns "Data C"
console.log("Current Keys:", Array.from(lru.cache.keys()));

Expected Output

When this program is compiled and executed, the terminal outputs:

Get Key 1: Data A
Get Key 2 (Evicted): -1
Get Key 3: Data C
Current Keys: [ 1, 3 ]

How the Code Works

JavaScript's Map preserves element insertion order. By deleting and re-inserting accessed keys, the front of the Map iterator (keys().next().value) consistently points to the least recently accessed key.

Time Complexity

O(1) get and put

Space Complexity

O(Capacity)

Key Takeaways & Best Practices

Map iteration order in JavaScript follows key insertion order.
keys().next().value provides O(1) access to the earliest inserted key.

Master JavaScript with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.