JS implementation with very detailed explanation, easy to understand


  • 2

    First, the LRU(least recently used) means we need some data structure to record the order of the last used time of each node. An intuitive solution is a Queue. Because First-In-First-Out is exactly the LRU concept. And a Queue can be implemented using linkedlist.

    Second, after we GET a node from cache, we need to move that node to the head of queue, meaning it is most recently used. To achieve it in O(1) time, we need a hashmap to record a key-(node) info for each node. After we identify that node, we just cut it from the queue and attach it to the head.

    Third, how about SET? First we try to locate a node with the KEY, if we found a node, we just change the value of that node and move the node to head(means it is most recently used). If we cannot find a node, we will create a new node with (key,val) and attach it to the head. If the size of cache exceeds the capacity, we need to REMOVE the LAST node(last recently used).

    In sumary, we basically need 3 operations

    • attachToHead: attach an isolated node to head
    • moveToHead: move an existing node in the linkedlist to head
    • removeLast: remove the last node in the linkedlist

    As you can see, to access head and tail in O(1) time, doubly linkedlist is a good choice.

    Node

    prev<=>(key,value)<=>next

    Doubly LinkedList

    (head)<=>(node1)<=>(node2)<=>...<=>(nodex)<=>(tail)
    most recently used >>>>>>>>>>>>>> least recently used

    HashMap

    [key1]=>(node1)
    [key2]=>(node2)
    ...

    /**
     * @constructor
     */
    var ListNode = function(key,val){
        this.prev = null;
        this.next = null;
        this.val = val;
        this.key = key;
    }
    var LRUCache = function(capacity) {
        this.head = new ListNode(-1,-1);
        this.tail = new ListNode(-1,-1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
        this.capacity = capacity;
        this.map = new Map();
    };
    
    /**
     * @param {number} key
     * @returns {number}
     */
    LRUCache.prototype.get = function(key) {
        let node = this.map.get(key);
        if(node){
            this.moveToHead(node);
            return node.val;
        }else{
            return -1;
        }
    };
    
    /**
     * @param {number} key
     * @param {number} value
     * @returns {void}
     */
    LRUCache.prototype.set = function(key, value) {
        let node = this.map.get(key);
        if(!node){
            node = new ListNode(key,value);
            this.attachToHead(node);
            this.size++;
        }else{
            node.val = value;
            this.moveToHead(node);
        }
        if(this.size > this.capacity){
            this.removeLast();
            this.size--;
        }
        this.map.set(key,node);
    };
    
    LRUCache.prototype.attachToHead = function(node){
        node.next = this.head.next;
        node.next.prev = node;
        this.head.next = node;
        node.prev = this.head;
    }
    
    LRUCache.prototype.moveToHead = function(node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.attachToHead(node);
    }
    
    LRUCache.prototype.removeLast = function(){
        let last = this.tail.prev;
        last.prev.next = this.tail;
        this.tail.prev = last.prev;
        this.map.delete(last.key);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.