Implement an LFU Cache Using Singly Linked List

Here, we'll introduce a new data structure in which we'll insert the key as the count, and value as the list of elements with the same count. For this we'll be using TreeMap as it will store the count in sorted order:

1let sortedCountMap = new Map();

Now accessing the element that has been least recently accessed along with the lowest count will become straightforward. The first key in sortedCountMap will be the lowest frequency. Now to find the element that has been least recently accessed with that frequency, all you have to do is remove the first element from that list. This will take O(1) time.

Now, let's discuss the steps that are different from our previous implementation to get an element:

• First, we'll find the count from the countMap.
• Next, we'll remove the key from the sortedCountMap, and insert it again with a new count value.
• Note that we'll remove the entry of the previous count from the sortedCountMap if that element was the only element in the list.

1private removeEntryFromSortedCountMapIfListIsEmpty(count) {
2    if (this.sortedCountMap.get(count).size() === 0) {
3        this.sortedCountMap.remove(count);
4    }
5}

1get(key) {
2
3	if (!this.valueMap.has(key) || this.size === 0) {
4		return -1;
5	}
6
7	let count = this.countMap.get(key);
8	this.sortedCountMap.get(count).delete(key);
9	this.removeEntryFromSortedCountMapIfListIsEmpty(count);
10
11	if (!this.sortedCountMap.has(count + 1)) {
12		this.sortedCountMap.set(count + 1, new LinkedList());
13	}
14	this.sortedCountMap.get(count + 1).add(key);
15
16	this.countMap.set(key, this.countMap.get(key) + 1);
17
18	return this.valueMap.get(key);
19
20}

Let's discuss the steps that are different from our previous implementation to insert an element:

If the key doesn't exist, and the cache is full, the eviction strategy will be different now:

• We'll first remove the least frequently used key from the sortedCountMap.
• Next, we'll also remove that entry from the sortedCountMap if that key was the only element in the list.
• After that, we'll remove the key/value pair from both the countMap and the valueMap.
• Finally, we'll update the countMap, valueMap, and sortedCountMap.

Let's discuss the case, when the key already exists:

• Now, we'll update the position of the key in sortedCountMap.
• We'll also remove the entry if the key was the only element in the list with that previous count value.

1put(key, value) {
2  if (!this.valueMap.has(key) && this.size > 0) {
3    if (this.valueMap.size === this.size) {
4      let lowestFrequency = [...this.sortedCountMap.keys()][0];
5      let evictKey = this.sortedCountMap.get(lowestFrequency).shift();
6      if (!this.sortedCountMap.get(lowestFrequency).length) {
7        this.sortedCountMap.delete(lowestFrequency);
8      }
9      this.valueMap.delete(evictKey);
10      this.countMap.delete(evictKey);
11    }
12    this.valueMap.set(key, value);
13    this.countMap.set(key, 1);
14    if (!this.sortedCountMap.has(1)) {
15      this.sortedCountMap.set(1, []);
16    }
17    this.sortedCountMap.get(1).push(key);
18  } else if (this.valueMap.has(key) && this.size > 0) {
19    let count = this.countMap.get(key);
20    this.valueMap.set(key, value);
21    this.countMap.set(key, count + 1);
22    this.sortedCountMap.get(count).remove(key);
23    if (!this.sortedCountMap.get(count).length) {
24      this.sortedCountMap.delete(count);
25    }
26    if (!this.sortedCountMap.has(count + 1)) {
27      this.sortedCountMap.set(count + 1, []);
28    }
29    this.sortedCountMap.get(count + 1).push(key);
30  }
31}

There exists a problem in this implementation.

The keys having the same count are in a list. Now to access a key, inorder to update it's entry in the sortedCountMap, we'll have to iterate through the entire list. The worst complexity in this case will be O(n).

To solve this problem, we'll move to our next implementation.