Caching: Building an LRU Cache from Scratch!

Today's article is special, we'll be building an LRU cache system from scratch! Be ready!

Hello again, brave coder 👨‍💻! Ever heard of LRU Cache but thought, “What in the world is this tech jargon?!” hahah. I thought that too at first place! But don’t worry at all! In today’s article, we’ll embark on a funny, beginner-friendly journey to understand and implement an LRU (Least Recently Used) Cache from scratch using JavaScript (you can follow with me, with any programming language of your choice).

Let’s learn using a funny way, as we always do! Bissmilah 🙏

---

What's a Cache?

To make you understand what a cache is, let’s imagine you’re playing a video game, okay? Your character needs quick access to potions, mushrooms, or whatever items you need. Now, wouldn’t it be so annoying if you had to search the entire game items list, for the item you need to use, every single time?!

That’s what a cache comes to solve! It’s like the character pocket that can be filled with up to 4 items for example that you might need ASAP, and you get to access these 4 items you chose easily, without going back to the game list of items every single time!

Computers use caches to store information like:

• Frequently visited web pages 🌐

• Recent search results 🔍

• and more…

Caches make things faster. Instead of fetching data from slow storage or servers, you grab it from this nearby, lightning-fast stash (cache).

---

Okay, but... LRU Cache?

Now, that we understood what a cache is, another problem comes to the scene: limited space!

As we discussed earlier, your game character have a pocket that can hold only up to 4 items, the pocket can’t handle more of that! So, what to do if we need to add another item on top of the old ones?

Enter the LRU (Least Recently Used) Cache !

If the cache is full, and you need to add something new, LRU kicks out (remove) the least recently used item, “like throwing out the expired milk in your fridge 😂”.

---

Where Is LRU Cache Used?

LRU Cache is everywhere nowadays:

1. Browsers: Store recently visited web pages.

2. Databases: Speed up access to frequently queried records.

3. Operating Systems: Keep track of recently used files.

Basically, it’s used wherever speed is critical, and space is limited!

---

Building an LRU Cache in JavaScript

Now, the fun will begin 👨‍💻! Let’s create our LRU Cache using a Doubly Linked List data structure. Don’t worry, it’s eaaaasy-peaaasy LOL (kind of 😅).

PS: If you don’t now what a Linked List is, go and check my previous articles, where I explained this data structure, in a beginner-friendly way!

Level1 : Preparing a game plan!

Here’s what we need to build:

1. A Map for Fast Access:
   JavaScript’s Map gives us instant access to stored items (use any Map data structure that can gives you O(1) lookup time).

2. A Doubly Linked List for Order: To keep track of most recently used and least recently used items.

3. Cache Size Limit: To decide when to throw out old data.

Level 2: Let’s Code It 👨‍💻!

Here’s our LRU Cache implementation:

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;  // Maximum items the cache can hold
        this.map = new Map();      // Fast access map
        this.head = new Node(null, null);  // Dummy head
        this.tail = new Node(null, null);  // Dummy tail
        this.head.next = this.tail;  // Connect head to tail
        this.tail.prev = this.head;  // Connect tail to head
    }

    // Remove a node from the linked list
    _removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // Add a node to the front (most recently used)
    _addNodeToFront(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }

    // Get value by key
    get(key) {
        if (!this.map.has(key)) return -1; // Key not in cache
        const node = this.map.get(key);
        this._removeNode(node);  // Remove from current position
        this._addNodeToFront(node); // Move to front (most recently used)
        return node.value;
    }

    // Put key-value in cache
    put(key, value) {
        if (this.map.has(key)) {
            const existingNode = this.map.get(key);
            this._removeNode(existingNode); // Remove existing node
        } else if (this.map.size === this.capacity) {
            const lru = this.tail.prev; // Least recently used node
            this._removeNode(lru); // Remove it
            this.map.delete(lru.key); // Delete from map
        }

        const newNode = new Node(key, value);
        this.map.set(key, newNode); // Add to map
        this._addNodeToFront(newNode); // Add to front
    }
}

Level 3: Let’s Test it using Fruits (I’m hungry 😂)

Here’s a quick example:

const cache = new LRUCache(3); // Max 3 items

cache.put(1, '🍎');  // Add 1 -> 🍎
cache.put(2, '🍌');  // Add 2 -> 🍌
cache.put(3, '🍇');  // Add 3 -> 🍇

console.log(cache.get(1)); // 🍎 (Most recently used now!)

cache.put(4, '🍉');  // Add 4 -> 🍉, removes 2 🍌 (least recently used)

console.log(cache.get(2)); // -1 (It's gone!)
console.log(cache.get(3)); // 🍇 (Still there!)

Level 5: Why This Works Like Magic?

1. Map for Fast Access: O(1) speed for checking if something’s in the cache.

2. Doubly Linked List: Keeps items in order of usage.

3. Capacity Limit: Ensures we don’t overload the cache.

---

Wrapping it up!

An LRU Cache is a smart way to manage limited memory by keeping the most recently used data readily available while discarding the least used data when the cache is full.

Using a combination of a Map (for quick lookups) and a Doubly Linked List (to track usage order), you can efficiently implement an LRU Cache with O(1) operations for both adding and retrieving data. That’s superfast!

It's a practical tool used in real-world applications like browsers, databases, and operating systems to improve performance!

And If you followed the tutorial, and achieved to build the LRU cache, I can say that you are one of the good programmers that exists nowadays! (no joke)

That’s it for today’s tutorial. In upcoming articles, we’ll uncover more real life design systems tools and try our best to recreate it from scratch!

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!