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

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


var LRUCache = function(capacity) {
    this.mapper=new Map();
    this.head=null;
    this.tail=null
    this.capacity=capacity;
    this.length=0;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.mapper.has(key)){
        let node=this.mapper.get(key)
        if(this.tail!==this.head &&  this.head!==node){
            this.moveToTop(node);
        }
        return node.val;
    }
    return -1;

};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.mapper.has(key)){
        let node=this.mapper.get(key);
        if(this.tail!==this.head && this.head!==node){
            this.moveToTop(node);
        }
        node.val=value;
    }
    else{
        let node=new linkNode(key,value);
        if(this.head){
            node.next=this.head;
            this.head.pre=node;
            this.head=node;
            if(this.length==this.capacity){
                this.mapper.delete(this.tail.key);
                this.tail.pre.next=null;
                this.tail=this.tail.pre;
            }
            else{
                this.length++;
            }
        }
        else{
            this.head=node;
            this.tail=node;
            this.length++;
        }
        this.mapper.set(key,node);
    }
};


LRUCache.prototype.moveToTop=function(node){
    if(node.next){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }
    else{
        this.tail=node.pre;
        this.tail.next=null;
    }
    node.next=this.head;
    this.head.pre=node;
    this.head=node;
    node.pre=null;
    return ;
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

// 执行用时：
// 220 ms
// , 在所有 JavaScript 提交中击败了
// 96.33%
// 的用户
// 内存消耗：
// 51 MB
// , 在所有 JavaScript 提交中击败了
// 48.05%
// 的用户

console.log()