17 How to Implement LRU-LFU Cache Through LinkedLists #

Hello, I am Ishikawa.

In the previous lectures 10-13, we have discussed the array data type and the data structures derived from it, such as stacks and queues. Later, when we talked about hash tables, we mentioned a data structure called linked list. Today, let’s delve into the linked list and the related caching algorithms it supports. Linked lists have many use cases, with the most popular example being the current hot topic of blockchain. It uses the idea of a linked list, where each block is connected to the next block through a linked list. In a linked list structure, each element is a node, and each node has its own content and a reference to the address of the next element.

Since we are talking about JavaScript, let’s go back to a familiar example, which is caching. Whether it’s our operating system or browser, caching is indispensable. By combining linked lists and hash tables, we can apply them to the caching mechanism we often talk about. So, how is this kind of caching implemented? Let’s start with the linked list.

How to Implement Single and Double Circular Linked Lists #

Single Linked List #

First, let’s take a look at how a singly linked list is implemented. A linked list is a data structure that links individual nodes together. Each node contains two main components: data and a pointer to the next node, which we call the next pointer. In the example below, we create a node with data and a reference to the next node.

To implement this, we can create a class called Node, which includes properties for storing data and the next node.

class Node {
  constructor(data){
    this.data = data;
    this.next = null;
  }
}

Next, we create a class called LinkedList to represent the linked list. In a linked list, the most common operations are inserting and deleting at the beginning and end, which have a time complexity of O(1). However, if you want to traverse from front to back or perform insertions and deletions at arbitrary positions, the corresponding time complexity would be O(n). The focus here is not on the implementation, but rather on understanding the main functionalities of a linked list. Therefore, I have not included all the code here, but you can see the core structure.

class LinkedList {
  constructor(){
    this.head = null;
    this.size = 0;
  }
  isEmpty(){ /* Check if the linked list is empty */ }
  size() { /* Get the size of the linked list */ }
  getHead() { /* Get the head node of the linked list */ } 
  indexOf(element) { /* Get the position of a specific element */ } 
  insertAtTail(element) { /* Insert an element at the end of the linked list */ }
  insertAt(element, index) { /* Insert an element at a specific position */ }
  remove(element) { /* Remove a specific element */ }
  removeAt(index) { /* Remove an element at a specific position */ }
  getElementAt(index) { /* Get the element at a specific position */ }
  removeAtHead(){ /* Remove an element at the head position */ }
}

Note that you might have observed that the last node is null or undefined. What is its purpose? This is a sentinel node, which optimizes the performance of insertions and deletions. With this approach, we can use the same code to handle operations on both the first and last nodes, as well as the intermediate nodes. In small-scale data, this difference may seem insignificant. However, when dealing with cache operations or other operations that require frequent insertions, deletions, modifications, and searches, it can have a significant impact.

Double Linked List #

Now that we have covered singly linked lists, let’s take a look at double linked lists. In the example of a singly linked list, you can see that it is unidirectional, meaning each node has a reference to the next node but not to the previous node. A double linked list, on the other hand, is bidirectional, meaning we can traverse from the last node to the first node using the previous pointer in each node.

To implement a double linked list, we can add a previous pointer property to the basic node implementation of a single linked list. Similarly, a double linked list can be built on top of a single linked list by adding a tail node. Both traversing from back to front and front to back have a time complexity of O(n).

class DoublyNode extends Node { 
  constructor(data, next, prev) {
    super(data, next); 
    this.prev = prev; 
  }
}

class DoublyLinkedList extends LinkedList {
  constructor() {
    this.tail = undefined;
  }
}

Circular Linked List #

Next, let’s take a look at a circular linked list. As the name suggests, a circular linked list is formed by connecting the head and tail nodes.

If it is a doubly circular list, it means that besides the head and tail nodes being connected in a clockwise direction, we can also traverse from the counterclockwise direction in a doubly circular linked list.

How to Implement Cache Using Linked List #

After understanding single and double linked lists, we can now go back to the topic of how to implement cache using a linked list. Let’s start by understanding the purpose of caching. Caching mainly involves storing data in temporary memory space for easier access. For example, databases have caches to reduce access to the hard disk, and web browsers have caches to avoid re-downloading text, images, or other materials when revisiting a page. Through a linked list, we can achieve caching. In this article, we will introduce two caching algorithms: Least Recently Used (LRU) and Least Frequently Used (LFU) caches.

An optimal caching solution should replace the least likely to be accessed content with new elements that are most likely to be accessed. However, in reality, this is impossible because no one can predict the future. Therefore, as a suboptimal solution, caching usually considers two factors: temporal locality and spatial locality. Temporal locality assumes that a recently accessed memory location is likely to be accessed again, while spatial locality assumes that locations near a recently accessed memory location are also likely to be accessed.

In practical usage, LRU caches are more commonly used than LFU caches. You may wonder why. Let’s leave this question for now and focus on the core mechanisms and implementation logic of these two caching algorithms. We will come back to this question later.

LFU Cache #

Let’s start by discussing LFU caching. In a classic LFU cache, there are two hash tables: a key-value hash table that stores nodes, and a frequency hash table that contains a doubly linked list for each access frequency. For example, if nodes with keys 2 and 3 have been accessed once, they will be added to the frequency 1 doubly linked list in the order of their access, as shown in the figure below.

In the LFU cache, we need to introduce the implementation of the LFU node and the LFU doubly linked list. The LFU node can inherit from the doubly linked list node class and add additional fields, such as the key and a counter to calculate the frequency of getting and setting the element.

class LFUNode extends DoublyNode {
  constructor(key) {
    this.key = key;
    this.freqCount = 1;
  }
}

class LFUDoublyLinkedList extends LinkedList {
  constructor() {/* LFU Doubly Linked List */ }
}

As mentioned earlier, an LFU cache consists of two hash tables: the key-value hash table and the frequency hash table. Both hash tables can be implemented using objects. The key-value hash table stores instances of LFU nodes. The frequency hash table has keys from 1 to n, representing different frequencies. The most frequently accessed and set content will have a frequency of n. Each key in the frequency hash table corresponds to a doubly linked list.

Now, let’s look at three key operation scenarios: insertion, update, and retrieval.

For the insertion scenario, which involves inserting a new node, we need to check if the cache is full. If it is, the frequency of the inserted element is set to 1. If the cache is not full, the new element will be inserted, and the tail element will be removed at the same time.

For the update scenario, which involves updating an existing node, the element will be moved to the head of the doubly linked list. Additionally, to calculate the next element to be removed, the minimum frequency minFreq will be decremented.

For the retrieval scenario, which involves getting a node, the cache can return the node, increment its frequency count, and move it to the head of the doubly linked list. Similar to the insertion scenario, the last step is to adjust the value of the minimum frequency minFreq to determine the element to be replaced in the next operation.

class LFUCache {
  constructor() {
    this.keys = {}; // key-value hash table for LFU nodes
    this.freq = {}; // frequency hash table for LFU linked lists
    this.capacity = capacity; // capacity of the cache
    this.minFreq = 0; // initialize the minimum access frequency to 0
    this.size = 0; // initialize the cache size to 0
  }
  set() {/* insert a node */}
  get() {/* retrieve a node */}
}

LRU Cache #

The above explanation covered the mechanism and core implementation logic of LFU caching. Now let’s move on to the Least Recently Used (LRU) cache. The goal of an LRU cache is to clear the oldest cached content from limited memory space when new content needs to be cached. When an element in the cache is accessed, it will be moved to the end of the linked list. When a content that is not in the cache is accessed, the oldest content at the front, i.e., the least recently used content, will be removed.

In the implementation of an LRU cache, the most important aspect is to track which node was accessed and when it was accessed. To achieve this, a doubly linked list and a hash table are utilized. The doubly linked list is used to keep track of the oldest content that needs to be removed from the front, as well as to insert the most recently accessed content at the end.

From the implementation perspective, LRU nodes are similar to LFU nodes. They require a key-value hash table, but they do not need a frequency hash table. An LRU cache can define the capacity of the cache by passing a capacity parameter. Like LFU, LRU also needs the functionality to remove nodes from the head of the linked list and add nodes to the tail. In addition, it requires two methods for retrieving and setting nodes. Overall, the implementation of LRU caching is simpler compared to LFU caching.

class LRUNode extends DoublyNode {
  constructor(key) {
    this.key = key;
  }
}

class LRUCache {
  constructor() {
    this.keys = {}; // key-value hash table for LRU nodes
    this.capacity = capacity; // capacity of the cache
    this.size = 0; // initialize the cache size to 0
  }
  set() {/* insert a node */}
  get() {/* retrieve a node */}
}

Summary #

Intuitively, LFU (Least Frequently Used) may seem like a more reasonable caching method compared to LRU (Least Recently Used) as it caches or clears content based on its access frequency. Then why is LRU more commonly used in practical applications? This is because, firstly, high-frequency access in a short period does not guarantee long-term value of the cache. Secondly, LFU may displace some content that is not accessed frequently except in the short term. Thirdly, content that has just been accessed may not be accessed frequently, but it could still be accessed again, increasing the possibility of accidental removal.

So, overall, LFU does not consider temporal locality, which means it does not address the issue of “recently accessed content may be accessed again.” Therefore, in practical applications, the probability of using LRU is higher than LFU. Hopefully, through this lesson, you will have a better understanding of the use of linked lists and hash tables, and, more importantly, when you need to write your own cache, you can consider these factors.

Reflection Question #

It’s time for reflection questions. Although LFU has limited applications, it can still be very useful in certain specific scenarios. Can you think of some related situations and implementations?

Feel free to share your answers, exchange learning experiences, or ask questions in the comments section. If you find it valuable, you are also welcome to share today’s content with more friends.