-
Notifications
You must be signed in to change notification settings - Fork 0
/
146-LRUCache.js
100 lines (86 loc) · 2 KB
/
146-LRUCache.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Node {
constructor(key, value, next = null, prev = null) {
this.key = key;
this.value = value;
this.next = next;
this.prev = prev;
}
}
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.size = 0;
this.limit = capacity;
this.head = this.tail = null;
this.cache = {};
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
return this.getNode(key) ? this.getNode(key).value : -1;
};
LRUCache.prototype.getNode = function (key) {
const node = this.cache[key];
if (!node) return -1;
const { value } = node;
this.remove(key);
this.put(key, value);
return node;
}
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (key in this.cache) {
this.remove(key);
// this.cache[key].value = value;
}
// remove least used data if cache already full
this.ensureLimit();
const node = new Node(key, value);
if (!this.head) {
this.head = this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.size++;
this.cache[key] = node;
};
LRUCache.prototype.ensureLimit = function () {
if (this.size === this.limit) {
// remove tail (least used)
this.remove(this.tail.key);
}
}
LRUCache.prototype.remove = function (key) {
const node = this.cache[key];
if (node.prev) {
node.prev.next = node.next;
} else {
this.head = node.next;
}
if (node.next) {
node.next.prev = node.prev;
} else {
this.tail = node.prev;
}
delete this.cache[key];
this.size--;
}
/**
* 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)
*/
var cache = new LRUCache(2 /* capacity */);
cache.put(2, 6);
cache.put(1, 5);
cache.put(1, 2);