Typorithm · medium

LRU Cache

lru-cachelinked-listsordered-maprecencyeviction

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn LRU Cache

Linked Lists

A JS Map preserves insertion order: refresh a key by deleting and re-inserting it, and evict the first key when over capacity.

An LRU cache needs O(1) get and put and must evict the least-recently-used key when full.

A JavaScript Map iterates keys in insertion order, so the first key is the oldest and re-inserting a key makes it newest.

get deletes and re-adds the key to refresh it; put evicts the first key when the cache is full.

Map preserves insertion order.

Refresh = delete then set.

Evict the first (oldest) key.

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

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

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest);
    }
    this.cache.set(key, value);
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Ordered map

A JS Map iterates keys in insertion order, so the first key is the oldest.

this.cache = new Map()

2. Refresh recency

Delete then re-insert to move the key to the most-recent position.

this.cache.delete(key);
    this.cache.set(key, value)

3. At capacity

Evict only when full and inserting a brand-new key.

this.cache.size >= this.capacity

4. Oldest key

The first key in iteration order is the least recently used.

this.cache.keys().next().value

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.