Learn How to Implement an LRU Cache in JavaScript

In the world of software development, optimizing data retrieval and memory usage is crucial, especially when dealing with large datasets or limited resources. One of the most efficient techniques for managing such data is the Least Recently Used (LRU) Cache.

In this blog post, we'll explore what an LRU Cache is, how it works, and walk through an implementation in JavaScript. We’ll also discuss real-world scenarios where LRU caching can help improve performance and resource management.

What is an LRU Cache?

An LRU Cache is a data structure designed to store a fixed number of items and evict the least recently used items when the cache reaches its limit. This type of cache ensures that the most recently accessed items are retained in memory, while the least accessed items are removed when space is needed.

The key characteristics of an LRU Cache are:

1. Fixed size: It has a predefined limit on the number of items it can hold.
2. Eviction policy: When the cache reaches its limit, the least recently accessed item is evicted.
3. Efficient access: The cache provides fast access to stored items.

How Does an LRU Cache Work?

At its core, an LRU Cache is a key-value store that maintains the order in which items are accessed. When an item is accessed, it becomes the most recently used item, and when new items are added, the least recently used items are pushed out.

LRU Cache Operations

There are three key operations to understand when implementing an LRU Cache:

1. Get: Retrieves an item from the cache. If the item exists, it is moved to the most recently used position.
2. Set: Adds an item to the cache. If the cache is full, it evicts the least recently used item.
3. Eviction: When the cache reaches its limit, the least recently accessed item is removed.

Real-World Scenarios for LRU Cache

LRU caches are used in various situations, including:

• Web browsers: Caching recently visited websites.
• Database management systems: Caching query results.
• Memory management: Optimizing limited memory by retaining the most frequently accessed data.

Implementing an LRU Cache in JavaScript

Let’s dive into the actual implementation of an LRU Cache in JavaScript. We'll use two core data structures:

• Doubly Linked List: To maintain the order of items and make it easy to move items to the most recent position.
• Hash Map: To quickly access and store items.

Step 1: Setting Up the LRU Cache Class

We’ll begin by creating the LRUCache class with the following properties:

• capacity: The maximum number of items the cache can hold.
• cache: A map to store the key-value pairs.
• order: A doubly linked list to keep track of the usage order.

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(); // to store key-value pairs
    this.head = new Node(null, null); // dummy head node
    this.tail = new Node(null, null); // dummy tail node
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
}

Step 2: Implementing the Get Method

The get method retrieves an item from the cache and moves it to the most recently used position (just before the tail).

get(key) {
  if (!this.cache.has(key)) {
    return -1; // return -1 if the item is not found
  }
  
  // Move the accessed node to the end (most recently used)
  const node = this.cache.get(key);
  this.moveToEnd(node);
  return node.value;
}

Step 3: Implementing the Set Method

The set method adds a new item to the cache. If the cache exceeds the capacity, it evicts the least recently used item.

set(key, value) {
  if (this.cache.has(key)) {
    // Update the value if the key already exists
    const node = this.cache.get(key);
    node.value = value;
    this.moveToEnd(node);
  } else {
    // If the key doesn't exist, create a new node
    const newNode = new Node(key, value);
    this.cache.set(key, newNode);
    this.addNode(newNode);
    
    if (this.cache.size > this.capacity) {
      // Remove the least recently used item
      this.removeLRU();
    }
  }
}

Step 4: Helper Methods to Move Nodes

We need a few helper methods:

• addNode: Adds a node right before the tail (most recent position).
• removeNode: Removes a node from the linked list.
• moveToEnd: Moves an existing node to the most recent position.

addNode(node) {
  node.prev = this.tail.prev;
  node.next = this.tail;
  this.tail.prev.next = node;
  this.tail.prev = node;
}

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

moveToEnd(node) {
  this.removeNode(node);
  this.addNode(node);
}

removeLRU() {
  const lru = this.head.next;
  this.removeNode(lru);
  this.cache.delete(lru.key);
}

Step 5: Testing the LRU Cache

Let’s test the implementation with a few examples:

const lruCache = new LRUCache(2);
lruCache.set(1, 1); // cache is {1=1}
lruCache.set(2, 2); // cache is {1=1, 2=2}
console.log(lruCache.get(1)); // returns 1, cache is {2=2, 1=1}
lruCache.set(3, 3); // evicts key 2, cache is {1=1, 3=3}
console.log(lruCache.get(2)); // returns -1 (not found)
lruCache.set(4, 4); // evicts key 1, cache is {3=3, 4=4}
console.log(lruCache.get(1)); // returns -1 (not found)
console.log(lruCache.get(3)); // returns 3
console.log(lruCache.get(4)); // returns 4

Best Practices for Using an LRU Cache

1. Determine Cache Size: Always define a reasonable cache size based on your application’s requirements. Avoid setting the cache size too high or too low.
2. Optimize Performance: Use a combination of hash maps and doubly linked lists for constant time complexity (O(1)) for both get and set operations.
3. Use Caching Wisely: Only cache items that are accessed frequently or expensive to recompute. Avoid caching everything.

Conclusion

An LRU Cache is a powerful tool for optimizing resource management and improving performance in applications that deal with large amounts of data. By understanding its behavior and implementing it correctly in JavaScript, developers can enhance the efficiency of their applications and reduce the risk of memory issues.

This comprehensive guide has taken you through the concepts, real-world scenarios, and implementation of an LRU Cache. By mastering this technique, you can build faster and more efficient applications.