Cache Mechanisms 101: Designing an LRU Cache Like a Pro

"New year, new me" was the plan, but apparently, my distractions had a lifetime subscription. The MVP for my latest product was supposed to drop sooner, but turns out, my focus had other priorities— like doom-scrolling through Product Hunt for smoother flows, overthinking, and getting sidetracked by the most irrelevant rabbit holes on the internet (its not Instagram or linkedIn I promise, I no more use it). But hey you know what, every LRU cache needs garbage collection, and I guess it's time to evict some distractions from my LRU cache and yup MVP will be ready sooner than ever.

Just like how my brain needs garbage collection to clear out distractions, systems need efficient caching to keep the most relevant data accessible. And that’s exactly where LRU Cache comes in! Let’s roll out the red carpet and dive right in!

Caching is one of the most important techniques for improving software performance. However, before jumping into how LRU Cache works, it’s crucial to ask ourselves: what data should we cache?

Before diving into the implementation, let’s break it down with a simple analogy:

You’ve probably noticed that Netflix keeps track of your most recently watched shows.

• When you watch an episode, that show moves to the front of the “Continue Watching” list.

• If you start a new show and your list is full, the oldest, least-watched show gets removed.

• This ensures that only the most relevant shows stay on the list.

This is indeed exactly how an LRU Cache functions! It keeps frequently accessed data available and removes the oldest, least-used data when space runs out.

Let's start implementing LRU cache block by block but we can start with brute force approach, considering we basically know what Map is in javascript and if you don't, I will add a link in the resource section below for what exactly map is.

But why Map right ?

Map helps us to store key value pair, lets say we can add a key and its value lets say I have recently watched movies than what i can do is I might look for the recently_watched_movies as key in the Map and return you the desired result that is stored in the value of that particular key.

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

  // GET method - Retrieve a value and mark it as recently used
  get(key) {
    if (!this.cache.has(key)) {
      return -1; // Key not found
    }
    let value = this.cache.get(key);
    // Move key to the most recently used position
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  // PUT method - Insert a key-value pair into the cache
  put(key, value) {
    // Remove old position if key already exists
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } 
    // If cache is full, remove the least recently used item
    else if (this.cache.size >= this.cacheLength) {
      let firstKey = this.cache.keys().next().value; // Get LRU item
      this.cache.delete(firstKey);
    }
    // Insert the new key-value pair as most recently used
    this.cache.set(key, value);
  }
}

// Usage Example
const lru = new LRUCache(3);
lru.put(1, 'A');
lru.put(2, 'B');
lru.put(3, 'C');
console.log(lru.get(2)); // B (moves 2 to the front)
lru.put(4, 'D'); // Removes least recently used (key: 1)
console.log(lru.get(1)); // -1 (not found)
console.log(lru.get(3)); // C
console.log(lru.get(4)); // D

so what happens in above code ?

In above code we created a class LRUCache, which exposes two methods get and put where , One method accepts only a key, while the other accepts both a key and a value, respectively While the LRU cache here is built using Map it stores in case of key value pair something sort of dictionary hence whenever we call get method the method actually run a very simple logic that says delete the current key and again add it (if the key is found in the Map) otherwise return -1 (that is they key is not found).

Since Map maintains insertion order, the first key in Map.keys() is always the oldest (i.e., the least recently used). This is why deleting Map.keys().next().value removes the LRU item, effectively implementing LRU eviction

Where as when we talk about the put part of the code, it first checks whether the key exists or not if it does it deletes the key and adds it again , but before adding the key what does it do is check for the cache length. If the cache length is full it does a thing especially this part

 else if (this.cache.size >= this.cacheLength) {
      let firstKey = this.cache.keys().next().value; // Get LRU item
      this.cache.delete(firstKey);
 }

this part is what exactly removes the least used item from the cache if the cache is full. So deletion in Map works something like this....

Since Map maintains insertion order, when we delete a key:

• The next key takes the position of the deleted key in terms of iteration order.

• Map.keys().next().value always retrieves the first remaining key.

Hence if we go with a simple example to understand without complicating it
it is something like this

const map = new Map();
map.set(1, 'A');
map.set(2, 'B');
map.set(3, 'C');

console.log([...map.keys()]); // Output: [1, 2, 3]

// Deleting the first key
map.delete(1);

console.log([...map.keys()]); // Output: [2, 3]

// Now the first key is 2
console.log(map.keys().next().value); // Output: 2

hence this is what the else-if part of the code of ours exactly replicates to the above extract.

While the brute-force approach works fine for small-scale apps, it has a major flaw—LRU eviction requires iterating over Map.keys(), which can take O(n) in the worst case. This is why we need a more optimized approach: combining a Doubly Linked List (DLL) and a HashMap, where eviction and updates happen in O(1) constant time.

Time for explain me like I am five:

Imagine a train 🚂 with multiple carriages connected together.

What makes this train special?

1. Each carriage (node) has a door at the front and back → This means you can move forward or backward easily.

2. You can remove a carriage from the middle without affecting the rest of the train.

3. You can add a new carriage at the front quickly when new passengers arrive. (most recently used)

This is called a Doubly Linked List (DLL) because:

• Each node (carriage) has a link (pointer) to both the next and previous nodes.

• It allows fast insertion and removal from anywhere in the list.
  

So we can now technically go step by step for the implementation of DLL + hashmap based LRU cache, where firstly we create a class Node with a constructor accpeting key, value as its args and a prev and next set to be null for storing the addresses of the doubly linked list nodes.

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null; // Pointer to previous node
        this.next = null; // Pointer to next node
    }
}

Now its time for creating a LRU cache class where the below code have

• this.cache = new Map();

  • Stores keys → Node references for O(1) lookup.

• this.head & this.tail

  • Dummy nodes to make inserting/removing nodes easier.

  • Head points to the Most Recently Used (MRU).

  • Tail points to the Least Recently Used (LRU).

class LRUCache {
    constructor(cacheLength) {
        this.cacheLength= cacheLength;
        this.cache = new Map(); // Key --> Node mapping for O(1) access
        this.head = new Node(0, 0); // Dummy Head
        this.tail = new Node(0, 0); // Dummy Tail
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
}

Now its time for some generic func which helps us in get or put operation for adding a node at front or removing from the DLL

• remove(node): Unlinks the node from the DLL.

• insertAtFront(node): Moves the node to the front (most recently used).

remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

insertAtFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
}

While now adding a get method , we will as usual check the same stuff we used to check before in our only Hashmap approach (the bruteforce one). which is

• If the key does not exist, return -1.

• If the key exists:

  • Remove the node from its current position.

  • Move it to the front (since it was just accessed).

  • Return the value.

get(key) {
    if (!this.cache.has(key)) return -1; // Key not found
    let node = this.cache.get(key);
    this.remove(node); // Remove from current position
    this.insertAtFront(node); // Move to the front
    return node.value;
}

Again we will be using the same logic for put operation, which indeed will be somewhat like

• If the key already exists --> Remove the old node.

• If cache is full --> Remove the Least Recently Used (last node in DLL).

• Create a new node and add it to the front (Most Recently Used).

• Store the key → node mapping in this.cache.

put(key, value) {
    if (this.cache.has(key)) {
        this.remove(this.cache.get(key)); // Remove existing node
    } else if (this.cache.size >= this.cacheLength) {
        let lruNode = this.tail.prev; // Get LRU node (last node)
        this.remove(lruNode);
        this.cache.delete(lruNode.key); // Remove from HashMap
    }
    let newNode = new Node(key, value);
    this.cache.set(key, newNode);
    this.insertAtFront(newNode); // Move to front as MRU
}

And this way if we combine the whole code for the DLL + hashmap we can easily get to the same implementation logically that we used to write before but in a better and optimized way for lage level systems too.

🚀 That’s a Wrap!

If only life had an LRU Cache to evict our most regrettable decisions, right? 😆

if you feel droppin me a message about the blog review or want to work on a product mvp together, I am alway active on Peerlist for a quick chat or also you can sent me a calendly invite by booking a suitable slot. Links in my socials.

My socials : tw bluesky calendly

Resources:

• Theory of Map - MDN web docs

• Designing LRU cache 101 by geeks for geeks