When it comes to managing data efficiently in programming, one of the vital structures you will encounter is caching. Caching allows programs to store data temporarily to allow for faster retrieval later on. The Least Recently Used (LRU) cache is an effective caching algorithm that helps in optimizing memory usage by evicting the least recently accessed items first. In this post, we will explore how to implement an LRU cache in JavaScript.

Understanding LRU Cache

Before we jump into code, let’s clarify what an LRU cache is. The LRU cache keeps track of what data has been most recently used. When the cache is full and new data needs to be added, it will remove the least recently accessed item to make room for the new data. This algorithm is especially useful when dealing with memory-limited environments or high-performance applications, such as web servers, databases, and application state management.

How the LRU Cache Works

To build an LRU cache, we need:

1. Capacity: The maximum number of items the cache can hold.
2. Data structure: We will use a combination of a hashmap and a doubly linked list. The hashmap allows for O(1) access to cache items, while the linked list will keep track of the access order.

Here’s a breakdown of how it functions:

1. When accessing an item, if it is in the hashmap, we move that item to the front of the linked list (marking it as recently used).
2. If we try to access an item that is not in the cache, we check if we have room. If we are at capacity, we remove the item at the end of the linked list (the least recently used item) before adding the new item to the cache.
3. Each time an item is accessed or added, the structure keeps itself organized to reflect usage order.

Implementing the LRU Cache in JavaScript

Let’s start coding the LRU Cache. Here's our implementation:

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); 
        this.head = new Node(null, null); 
        this.tail = new Node(null, null); 
        this.head.next = this.tail; 
        this.tail.prev = this.head; 
    }

    _remove(node) {
        const prevNode = node.prev;
        const nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    _addToFront(node) {
        const nextNode = this.head.next;
        this.head.next = node;
        node.prev = this.head;
        node.next = nextNode;
        nextNode.prev = node;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1; 
        }
        const node = this.cache.get(key);
        this._remove(node); 
        this._addToFront(node); 
        return node.value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            this._remove(node); 
            this._addToFront(node);
            node.value = value; 
        } else {
            if (this.cache.size === this.capacity) {
                const lruNode = this.tail.prev;
                this._remove(lruNode);
                this.cache.delete(lruNode.key); 
            }
            const newNode = new Node(key, value);
            this._addToFront(newNode);
            this.cache.set(key, newNode);
        }
    }
}

How to Use the LRUCache

Now that we have built our LRUCache class, let’s see how we can use it in a practical example:

const lruCache = new LRUCache(2); // Create an LRU Cache with a capacity of 2

lruCache.put(1, 'One'); // Cache is {1='One'}
lruCache.put(2, 'Two'); // Cache is {1='One', 2='Two'}
console.log(lruCache.get(1)); // Returns 'One', Cache is now {2='Two', 1='One'}
lruCache.put(3, 'Three'); // Evicts key 2, Cache is {1='One', 3='Three'}
console.log(lruCache.get(2)); // Returns -1 (not found)
lruCache.put(4, 'Four'); // Evicts key 1, Cache is {3='Three', 4='Four'}
console.log(lruCache.get(1)); // Returns -1 (not found)
console.log(lruCache.get(3)); // Returns 'Three'
console.log(lruCache.get(4)); // Returns 'Four'

In this example, we create an LRU cache with a capacity of 2. As we add elements and perform retrievals, the cache automatically evicts the least recently used items according to the rules we defined.

By implementing an LRU cache, we can efficiently handle data storage and retrieval, optimizing our applications for both speed and memory usage. With its simple yet effective logic, the LRU cache is a valuable tool in every developer's toolkit.