What is LRU and How to Implement LRU Cache in JavaScript

Introduction

LRU stands for Least Recently Used, a cache eviction policy. When the cache reaches its storage limit, LRU removes the least recently used entry. This policy is based on the assumption that recently used data is likely to be used again in the near future, while the least recently used data is less likely to be accessed again.

JavaScript Implementation of LRU Cache

In JavaScript, an LRU cache can be implemented using a combination of Map and a doubly linked list. Map ensures the insertion order of elements, and the doubly linked list helps efficiently move the recently used element to the head and remove the least recently used element.

Code Implementation

Here is a simple LRU cache implementation:

1
// Define the doubly linked list node class
2
class Node {
3
  constructor(key, value) {
4
    this.key = key;
5
    this.value = value;
6
    this.prev = null;
7
    this.next = null;
8
  }
9
}
10


11
// Define the LRU Cache class
12
class LRUCache {
13
  constructor(capacity) {
14
    this.capacity = capacity; // Cache capacity
15
    this.map = new Map(); // Store cache data
16
    this.head = new Node(null, null); // Virtual head node
17
    this.tail = new Node(null, null); // Virtual tail node
18
    this.head.next = this.tail;
19
    this.tail.prev = this.head;
20
  }
21


22
  // Get cache value
23
  get(key) {
24
    if (!this.map.has(key)) {
25
      return -1; // Return -1 if the key is not in the cache
26
    }
27


28
    const node = this.map.get(key);
29
    this._remove(node); // Remove the node from the doubly linked list
30
    this._add(node); // Add the node to the end of the list (indicating recent use)
31


32
    return node.value;
33
  }
34


35
  // Add or update cache value
36
  put(key, value) {
37
    if (this.map.has(key)) {
38
      this._remove(this.map.get(key)); // Remove the old node if the key already exists in the cache
39
    }
40


41
    const newNode = new Node(key, value);
42
    this._add(newNode); // Add the new node to the end of the list
43
    this.map.set(key, newNode);
44


45
    if (this.map.size > this.capacity) {
46
      const lruNode = this.head.next; // Get the least recently used node
47
      this._remove(lruNode); // Remove the least recently used node from the list
48
      this.map.delete(lruNode.key); // Delete the least recently used key from the cache
49
    }
50
  }
51


52
  // Remove a node from the doubly linked list
53
  _remove(node) {
54
    node.prev.next = node.next;
55
    node.next.prev = node.prev;
56
  }
57


58
  // Add a node to the end of the doubly linked list
59
  _add(node) {
60
    node.prev = this.tail.prev;
61
    node.next = this.tail;
62
    this.tail.prev.next = node;
63
    this.tail.prev = node;
64
  }
65
}

Example Usage

1
const lru = new LRUCache(2);
2


3
lru.put(1, 1);
4
lru.put(2, 2);
5
console.log(lru.get(1)); // Output 1
6
lru.put(3, 3); // Evict key 2
7
console.log(lru.get(2)); // Output -1 (not found)
8
lru.put(4, 4); // Evict key 1
9
console.log(lru.get(1)); // Output -1 (not found)
10
console.log(lru.get(3)); // Output 3
11
console.log(lru.get(4)); // Output 4

Code Explanation

  1. Node Class: A class for the doubly linked list node, containing key, value, prev, and next pointers.
  2. LRUCache Class: The main class to manage the cache. It initializes with a capacity, creates a Map, and two sentinel nodes head and tail.
  3. get Method: Retrieves the value from the cache. If it exists, moves the node to the end (indicating recent use).
  4. put Method: Inserts a new value into the cache. If the key-value pair already exists, deletes the old node first. After inserting the new node, checks if the capacity is exceeded and removes the node at the front (indicating least recent use).
  5. _remove Method: Deletes a node from the doubly linked list.
  6. _add Method: Adds a node to the end of the doubly linked list.

This implementation ensures that both get and put operations can be completed in constant time complexity ( O(1) ).

Conclusion

Through the above code and detailed comments, we have learned how to implement a simple LRU cache using JavaScript. LRU cache is a common cache eviction policy, widely used in various caching systems. I hope this article helps you better understand the implementation principles and applications of LRU cache.

Similar Posts

How to Install and Renew Let’s Encrypt Certificates on Alibaba Cloud Server

How to Install and Renew Let’s Encrypt Certificates on Alibaba Cloud Server

How to Build a Blog：Comprehensive Guide and Platform Analysis

How to Build a Blog：Comprehensive Guide and Platform Analysis