原題來自力扣,這裡用到了JS中的Map這個資料結構。利用散清單和雙向連結清單實作。
力扣LRU原題
var LinkNode = function(key,value){
this.key = key;
this.value = value;
this.next = null;
this.pre = null;
}
var DoubleLinkedList = function(){
this.size = 0;
this.head = new LinkNode();
this.tail = new LinkNode();
this.head.next = this.tail;
this.tail.pre = this.head;
}
DoubleLinkedList.prototype.addNode = function(node){
if (!(node instanceof LinkNode)) throw new Error('param must be a LinkNode');
// 插入節點時,使用尾插法。這裡可以利用雙向連結清單一直在尾結點前驅插入節點。
const preNode = this.tail.pre;
const nextNode = this.tail.pre.next;
node.pre = preNode;
node.next = nextNode;
preNode.next = node;
nextNode.pre = node;
this.size++;
}
DoubleLinkedList.prototype.deleteNode = function(node){
if (!(node instanceof LinkNode)) throw new Error('param must be a LinkNode');
// 将剛剛通路過的節點插入到連結清單最後一位。
const preNode = node.pre;
const nextNode = node.next;
preNode.next = nextNode;
nextNode.pre = preNode;
this.size--;
}
DoubleLinkedList.prototype.refreshList = function(node){
this.deleteNode(node);
this.addNode(node);
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.maxSize = capacity;
this.map = new Map();
this.doubleLinkedList = new DoubleLinkedList();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.map.get(key) === undefined ) return -1;
const curNode = this.map.get(key);
this.doubleLinkedList.refreshList(curNode);
return curNode.value;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
const newNode = new LinkNode(key,value);
// 如果key已經存在,則變更其值
if (this.map.get(key)) {
this.doubleLinkedList.refreshList(this.map.get(key))
return this.map.get(key).value = value;
}
if (this.map.size < this.maxSize) {
this.doubleLinkedList.addNode(newNode);
} else {
// 需要清理連結清單中的首元節點,并将新節點插入到尾部
const firstNode = this.doubleLinkedList.head.next;
this.doubleLinkedList.deleteNode(firstNode);
this.doubleLinkedList.addNode(newNode);
// 同時需要清理掉散清單中的key
this.map.delete(firstNode.key);
}
this.map.set(key,newNode);
};