ArticleZip > Lru Cache Implementation In Javascript

Lru Cache Implementation In Javascript

Implementing an LRU (Least Recently Used) cache in JavaScript can significantly improve the performance of your applications by efficiently managing and storing frequently accessed data. In this guide, we will walk you through the process of implementing an LRU cache in JavaScript step by step.

Firstly, let's understand what exactly an LRU cache does. An LRU cache stores key-value pairs similar to a regular cache, but it evicts the least recently used items first when the cache reaches its maximum capacity. This mechanism ensures that only the most relevant data is retained in the cache, optimizing memory usage.

To implement an LRU cache in JavaScript, we can use a combination of objects and doubly linked lists. The objects will store the key-value pairs, while the linked list will keep track of the order in which the items were accessed.

To begin, let's define the structure of a doubly linked list node. Each node will contain a key, a value, and references to the next and previous nodes in the list.

Javascript

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

Next, let's create the LRU cache class. This class will have a maximum capacity, a map to store key-node pairs, and references to the head and tail nodes of the linked list.

Javascript

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

With the basic setup ready, we can implement methods to get and put key-value pairs in the cache. When accessing an item, we will update its position in the linked list to reflect its most recent use.

Javascript

LRUCache.prototype.get = function(key) {
  if (this.cache[key]) {
    const node = this.cache[key];
    this.removeNode(node);
    this.addNodeToHead(node);
    return node.value;
  } else {
    return -1; // Return -1 for cache misses
  }
};

LRUCache.prototype.put = function(key, value) {
  if (this.cache[key]) {
    this.removeNode(this.cache[key]);
  } else if (Object.keys(this.cache).length >= this.capacity) {
    const tailKey = this.removeTail();
    delete this.cache[tailKey];
  }

  const newNode = new Node(key, value);
  this.cache[key] = newNode;
  this.addNodeToHead(newNode);
};

By following these steps and understanding the logic behind an LRU cache, you can efficiently manage data in your JavaScript applications, improving their performance and efficiency. Experiment with different implementations and adapt them to suit your specific use cases to harness the full potential of LRU caching in JavaScript.

Related posts:

×