LRU 缓存机制
/**
* 双向链表结点
* @param {any} data: 列表结点数据
* @param {ListNode|null} pre: 前指针
* @param {ListNode|null} next: 后指针
*/
var ListNode = function(data, pre=null, next=null){
this.val = data;
this.pre = pre;
this.next = next;
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
// 大小
this.currSize = 0;
this.capacity = capacity;
// 双向链表记录数据（{key, value}）
this.headNode = null;
this.tailNode = null;
// 对象字典记录：键为数据key，值为其双向链表结点
this.dict = {};
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
// key in
if(key in this.dict){
let node = this.dict[key];
// node 不是 时，需要更新位置
if(node !== this.tailNode){
// pre 存在
// node 从原位置 “出来”
if(node.pre){
// 更新 2 指针
node.pre.next = node.next;
node.next.pre = node.pre;
}
// pre 不存在，说明 node 为
else{
this.headNode = node.next;
this.headNode.pre = null;
}
// node 进入新位置（）
this.tailNode.next = node;
node.pre = this.tailNode;
this.tailNode = node;
this.tailNode.next = null;
}
return node.val.value;
}
// key not in
else return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
// key in
if(key in this.dict){
// 更新数据
let node = this.dict[key];
node.val.value = value;
// 不是tailNode，需要更新位置
if(this.tailNode !== node){
// node 从原位置 “出来”
// node 有 pre
if(node.pre){
// 更新 2 指针位置
node.pre.next = node.next;
node.next.pre = node.pre;
}
// node 无 pre, 说明node是headNode
else{
this.headNode = node.next;
this.headNode.pre = null;
}
// node 进入新位置（结尾）
this.tailNode.next = node;
node.pre = this.tailNode;
this.tailNode = node;
this.tailNode.next = null;
}
}
// key not in
else{
// LRU 满，先剔除headNode
if (this.currSize >= this.capacity){
delete this.dict[this.headNode.val.key];
this.headNode = this.headNode.next;
this.headNode && (this.headNode.pre = null); // capacity为1时，可能为null
this.currSize--;
}
// LRU 为空
if(this.currSize === 0){
this.dict[key] = this.headNode = this.tailNode = new ListNode({'key': key, 'value': value});
}
// LRU 不为空
else{
this.dict[key] = this.tailNode.next = new ListNode({'key': key, 'value': value}, this.tailNode);
this.tailNode = this.dict[key];
}
// 更新 currSize
this.currSize++;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = (key)
* (key,value)
*/