We're now in business. Let's start adding stuff by implementing the put method. put should check if the value exists or not in this.cache based on the key. If it doesn't, we can add it in.
However, it's not enough to just add it in-- the whole reason for using a doubly linked list is also to see the order of use. Thus, if we're adding a new value, it means that it's the most recently used, and we should thus move it to the front of the linked list. This serves to be an indication that we should NOT evict it.
put checks if the node is in the cache. If it's not, we create a new node in the doubly linked list (added to the head), and increment our length. We also check at this point if we're over capacity-- if we are, we get rid of the node at the tail, as it's the least recently used.
Alternatively, if the node already exists, we simply overwrite the existing node value and move it to the start.
1class Cache {
2 constructor(capacity) {
3 this.count = 0;
4 this.capacity = capacity;
5 this.cache = {};
6 this.head = new DLinkedNode();
7 this.head.pre = null;
8 this.tail = new DLinkedNode();
9 this.tail.next = null;
10 this.head.next = this.tail;
11 this.tail.pre = this.head;
12 }
13
14 put(key, value) {
15 const node = this.cache[key];
16 if (!node) {
17 const newNode = new DLinkedNode(key, value, null, null);
18 this.cache[key] = newNode;
19 this.addNode(newNode);
20 this.count++;
21 // the overcapacity scenario
22 // evict the value at the end of the linked list
23 if (this.count > this.capacity) {
24 const tail = this.popTail();
25 delete this.cache[tail.key];
26 this.count--;
27 }
28 } else {
29 node.val = value;
30 // move to head as it's the most recently used
31 this.moveToHead(node);
32 }
33 }
34}