Least Recently Used Cache
Intuition
We use a LinkedList to move the keys with larger rank to the top whenever we use them. Naturally, the keys with the lowest rank key will become the tail.
We also maintain a map of key to node.
Approach
This solution LinkedList to effectively read and set in cache in $O(1)$ time.
Complexity
- Time complexity: $O(1)$
- Space complexity: $O(capacity)$
Code
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.pre = null;
this.post = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null; // this will be the eviction key
}
addToTop(node) {
if (this.tail == null) {
this.tail = node;
}
if (this.head != null) {
this.head.pre = node;
node.post = this.head;
}
this.head = node;
}
unlink(node) {
if (node == null) {
return;
}
let pre = node.pre;
let post = node.post;
if (pre != null) {
pre.post = post;
}
if (post != null) {
post.pre = pre;
}
if (this.head == node) {
this.head = post;
}
if (this.tail == node) {
this.tail = pre;
}
node.pre = null;
node.post = null;
}
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.cap = capacity;
this.map = new Map(); // key: node
this.list = new LinkedList();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (!this.map.has(key)) {
return -1;
}
let node = this.map.get(key);
this.list.unlink(node);
this.list.addToTop(node);
return node.value;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key)) {
let node = this.map.get(key);
node.value = value;
this.list.unlink(node);
this.list.addToTop(node);
return;
}
if (this.map.size >= this.cap) {
let nodeToRemove = this.list.tail;
this.list.unlink(nodeToRemove);
this.map.delete(nodeToRemove.key);
}
let newNode = new Node(key, value);
this.list.addToTop(newNode);
this.map.set(key, newNode);
};
