Implement an LFU Cache Using Doubly Linked List
To avoid iterating through the whole list, remove the element directly, and insert it against other count value sortedCountMap, we'll be needing a Doubly Linked List. Note that this will now take O(1) time.
1let sortedCountMap = new Map();
Here, we'll store Node object as the value in valueMap. It will have key, value, and the position of the node in the linked list stored as the value in sortedCountMap:
1var valueMap = {};1class Node {
2 constructor(key, value) {
3 super();
4 this.key = key;
5 this.value = value;
6 }
7}Let's have a look at the DoubleLinkedList class:
1class DoubleLinkedList {
2
3 constructor(){
4 this.n = 0;
5 this.head = null;
6 this.tail = null;
7 }
8
9 add(node) {
10
11 if (this.head == null) {
12
13 this.head = node;
14 }
15
16 else {
17
18 this.tail.next = node;
19 node.previous = this.tail;
20
21 }
22 this.tail = node;
23 this.n++;
24
25 }
26
27 remove(node) {
28
29 if (node.next == null) {
30 this.tail = node.previous;
31
32 } else {
33
34 node.next.previous = node.previous;
35
36 }
37
38 if (node.previous == null) {
39
40 this.head = node.next;
41 } else {
42
43 node.previous.next = node.next;
44
45 }
46
47 this.n--;
48
49 }
50
51 size() {
52
53 return this.n;
54
55 }
56
57 getHead() {
58 return this.head;
59 }
60
61}To get an element, and update the value in sortedCountMap takes O(1) time now:
1get(key) {
2 if (!this.valueMap.has(key) || this.size === 0) {
3 return -1;
4 }
5 let nodeToRemove = this.valueMap.get(key);
6 let node = new Node(key, nodeToRemove.value);
7 let count = this.countMap.get(key);
8 this.sortedCountMap.get(count).remove(nodeToRemove);
9 this.removeEntryFromSortedCountMapIfListIsEmpty(count);
10 this.valueMap.delete(key);
11 this.countMap.delete(key);
12 this.valueMap.set(key, node);
13 this.countMap.set(key, count + 1);
14 this.sortedCountMap.set(count + 1, this.sortedCountMap.get(count + 1) || new DoubleLinkedList());
15 this.sortedCountMap.get(count + 1).add(node);
16 return this.valueMap.get(key).value;
17}Finally, let's have a look at how a new element can be inserted, or existing can be updated:
1put(key, value) {
2 if (valueMap.has(key) == false && size > 0) {
3
4 var node = new Node(key, value);
5 if (valueMap.size() == size) {
6 var lowestFrequency = Math.min(...sortedCountMap.keys());
7 var nodeToRemove = sortedCountMap.get(lowestFrequency).getHead();
8 sortedCountMap.get(lowestFrequency).remove(nodeToRemove);
9 removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);
10
11 var keyToRemove = nodeToRemove.getKey();
12 valueMap.delete(keyToRemove);
13 countMap.delete(keyToRemove);
14 }
15 sortedCountMap.set(1, (sortedCountMap.get(1) || new DoubleLinkedList())).add(node);
16 valueMap.set(key, node);
17 countMap.set(key, 1);
18
19 } else if (valueMap.has(key) && size > 0) {
20 var node = new Node(key, value);
21 var nodeToRemove = valueMap.get(key);
22 var count = countMap.get(key);
23 sortedCountMap.get(count).remove(nodeToRemove);
24 removeEntryFromSortedCountMapIfListIsEmpty(count);
25 valueMap.delete(key);
26 countMap.delete(key);
27 valueMap.set(key, node);
28 countMap.set(key, count + 1);
29 sortedCountMap.set(count + 1, (sortedCountMap.get(count + 1) || new DoubleLinkedList())).add(node);
30
31 }
32}