题解 | #设计LRU缓存结构#

/**
 * @param {number} capacity
 */

function ListNode (val){
    this.val = val;
    this.key = null;
    this.next = null;
    this.pre = null;
    
}

var Solution = function(capacity) {
    // write code here
    this.map = new Map();
    this.max = capacity;
    this.latestUsedPtr = null; //最近调用
    this.oldestUnusedPtr = null; //最久未调用
};

/** 
 * @param {number} key
 * @return {number}
 */
Solution.prototype.get = function(key) {
    // write code here
    
    if(this.map.has(key)){
        let valueNode = this.map.get(key);

        // 如果当前被get的节点不是最近一次调用过的，则将其提到第一个。
        if(valueNode.pre){
            // 如果当前节点是最久未调用，将最久未调用设为前一个
            if(!valueNode.next && valueNode.pre){
                this.oldestUnusedPtr = valueNode.pre;
            }
            //将该节点的前后节点连接起来，以维持链表结构
            valueNode.pre.next = valueNode.next;
            if(valueNode.next)
                valueNode.next.pre = valueNode.pre;
            
            //将该节点插入链表头
            valueNode.next = this.latestUsedPtr;
            this.latestUsedPtr.pre = valueNode;
            valueNode.pre = null;
            this.latestUsedPtr = valueNode;
            
        }
        return valueNode.val;
       
    }
    else{
        return -1;
    }
    
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
Solution.prototype.set = function(key, value) {
    // write code here
    
    let nodeToInsert = new ListNode(value);
    nodeToInsert.key = key;

    // 超出限额，拿掉最久未调用节点
    if(this.map.size === this.max && !this.map.has(key)){
       
        let preNode = this.oldestUnusedPtr.pre;
        preNode.next = null;
        this.map.delete(this.oldestUnusedPtr.key);
        this.oldestUnusedPtr = preNode;
    }
    // 已经存在该key
    if(this.map.has(key)){
        let curNode = this.map.get(key);
        //将旧节点从链表中移除
        if(curNode.pre){
            curNode.pre.next = curNode.next;
        }
        //将旧节点从表中移除
        this.map.delete(key);
    }
    
    
    // 将其添加到第一个，为最近掉用节点
    this.map.set(key,nodeToInsert);
    nodeToInsert.pre = null;
    nodeToInsert.next = this.latestUsedPtr;
    if(this.latestUsedPtr)
        this.latestUsedPtr.pre = nodeToInsert;
    
    if(nodeToInsert.next)
        nodeToInsert.next.pre = nodeToInsert;
    this.latestUsedPtr = nodeToInsert;
    // 如果只剩一个节点。
    if(!this.oldestUnusedPtr) 
        this.oldestUnusedPtr = nodeToInsert;

    return 
};

module.exports = {
    Solution : Solution
};

/**
 * Your Solution object will be instantiated and called as such:
 * var solution = new Solution(capacity)
 * var output = solution.get(key)
 * solution.set(key,value)
 */