LRU Cache

[kokocan12]

Problem

Implement LRU Cache, LRU Cache means Least Recently Used Cache.
LRU Cache has a capacity that indicates max count of store.
If input into the cache when cache is full, The cache delete Least Recently Used key and set the new key-value into cache.
Use cases are get, put.
Get and Put should have a time complexity of O(1).

Approach

Using Map, we can store key-value pairs.
Also we can access to least used key by using Linked-List.
If "get" some value using key, the key's position in Linked-List is re-arranged.
When "put" some key, we can delete least recently used key using Linked-List, because the left most node is the oldest node.
There is a trick to remove node from Linked-List and insert node into Linked-List.
The trick is saving node into cache instead of value.

The code is below.

/**
 * @param {[key, value]} val
 */
const Node = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}


/**
 * @param {number} capacity
 */
const LRUCache = function(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
    this.leftEnd = new Node(null);
    this.rightEnd = new Node(null);
    
    this.leftEnd.right = this.rightEnd;
    this.rightEnd.left = this.leftEnd;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.cache.get(key)) {
        const existingNode = this.cache.get(key);
        this.remove(existingNode);
        this.insert(existingNode);
        
        return existingNode.val[1];
    } else {
        return -1;
    }
};

/**
 * @param {Node} node
 * @return {void}
 */
LRUCache.prototype.remove = function(node) {
    const leftNode = node.left;
    const rightNode = node.right;
    
    leftNode.right = rightNode;
    rightNode.left = leftNode;
    node.left = null;
    node.right = null;
}

/**
 * @param {Node} node
 * @return {void}
 */
LRUCache.prototype.insert = function(node) {
    const mostRecentlyUsedNode = this.rightEnd.left;
    mostRecentlyUsedNode.right = node;
    node.left = mostRecentlyUsedNode;
    this.rightEnd.left = node;
    node.right = this.rightEnd;
}

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.cache.get(key)) {
        // OVERWRITE.
        const existingNode = this.cache.get(key);
        this.remove(existingNode);
        const insertingNode = new Node([key, value]);
        this.insert(insertingNode);
        this.cache.set(key, insertingNode);
    } else {
        if(this.cache.size === this.capacity) {
            const leastRecentlyUsedNode = this.leftEnd.right;
            const leastRecentlyUsedKey = leastRecentlyUsedNode.val[0];
            this.remove(leastRecentlyUsedNode);
            this.cache.delete(leastRecentlyUsedKey);
            
            const insertingNode = new Node([key, value]);
            this.insert(insertingNode);
            this.cache.set(key, insertingNode);
        } else {
            const insertingNode = new Node([key, value]);
            this.insert(insertingNode);
            this.cache.set(key, insertingNode);
        }
    }
};