Horje
LRU Cache using JavaScript

The LRU (Least Recently Used) Cache is a type of the data structure that is used to the store a limited number of items with the capability to the quickly retrieve and manage these items. When the cache reaches its limit the least recently used item is removed to the make space for the new item. This is particularly useful in the scenarios where you need to the maintain a fixed amount of the data and ensure quick access and updates such as in web browsers database management systems and memory management.

These are the following approaches:

Table of Content

Using Map and Doubly Linked List

The combination of a Map and a Doubly Linked List is a common approach to the implement an LRU Cache. The Map provides an average O(1) time complexity for the get and set operations while the Doubly Linked List helps in the keeping track of the order of the usage. When an item is accessed it is moved to the front of list ensuring that the least recently used item is at the end of the list.

Example: This illustrates an LRUCache (Least Recently Used Cache) data structure in JavaScript using a doubly linked list and a map, allowing efficient storage and retrieval of key-value pairs with a specified capacity, discarding the least recently used items when the capacity is exceeded.

JavaScript 
class ListNode {
    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 ListNode(null, null);
        this.tail = new ListNode(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    _remove(node) {
        let prev = node.prev;
        let next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    _add(node) {
        let next = this.head.next;
        this.head.next = node;
        node.prev = this.head;
        node.next = next;
        next.prev = node;
    }
    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        let node = this.cache.get(key);
        this._remove(node);
        this._add(node);
        return node.value;
    }
    put(key, value) {
        if (this.cache.has(key)) {
            this._remove(this.cache.get(key));
        }
        let newNode = new ListNode(key, value);
        this._add(newNode);
        this.cache.set(key, newNode);
        if (this.cache.size > this.capacity) {
            let lru = this.tail.prev;
            this._remove(lru);
            this.cache.delete(lru.key);
        }
    }
}
// Example usage
let lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
console.log(lru.get(1)); 
lru.put(3, 3); 
console.log(lru.get(2)); 
lru.put(4, 4); 
console.log(lru.get(1)); 
console.log(lru.get(3)); 
console.log(lru.get(4));

Output
1
-1
-1
3
4

Time Complexity: O(1) for the both get and put operations.

Using Map and Array

This approach is to the use a Map in conjunction with the Array. The Map provides the fast access to the cache items while the Array keeps track of the order in which items were used. This method is simpler but less efficient for the large caches due to the need to perform the array operations to the maintain the order.

Example: This illustrates an LRU (Least Recently Used) cache using a Map and an array to store key-value pairs with a fixed capacity.

JavaScript 
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.order = [];
    }
    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        let value = this.cache.get(key);
        this._updateOrder(key);
        return value;
    }
    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.set(key, value);
            this._updateOrder(key);
        } else {
            if (this.cache.size >= this.capacity) {
                let lru = this.order.shift();
                this.cache.delete(lru);
            }
            this.cache.set(key, value);
            this.order.push(key);
        }
    }
    _updateOrder(key) {
        let index = this.order.indexOf(key);
        if (index > -1) {
            this.order.splice(index, 1);
        }
        this.order.push(key);
    }
}
// Example usage
let lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
console.log(lru.get(1)); 
lru.put(3, 3); 
console.log(lru.get(2)); 
lru.put(4, 4); 
console.log(lru.get(1)); 
console.log(lru.get(3)); 
console.log(lru.get(4));

Output
1
-1
-1
3
4

Time complexity: O(n) for the updating the order array.


 


Reffered: https://www.geeksforgeeks.org

JavaScript

Related
How to Add a Line Break in JavaScript? How to Add a Line Break in JavaScript?
Find the Sum of All Left Leaves in a Given Binary Tree using JavaScript Find the Sum of All Left Leaves in a Given Binary Tree using JavaScript
Polyfill for Array.prototype.filter Method in JavaScript Polyfill for Array.prototype.filter Method in JavaScript
How to Fix "Invalid Shorthand Property Initializer" in JavaScript? How to Fix "Invalid Shorthand Property Initializer" in JavaScript?
Difference Between Sums of Odd Level and Even Level Nodes of a Binary Tree using JavaScript Difference Between Sums of Odd Level and Even Level Nodes of a Binary Tree using JavaScript

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje