JavaScript bidirectional linked list implementation LFU cache algorithm

This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

describe

You design and implement data structures for least-used (LFU) caching algorithms.

Implement the LFUCache class:

LFUCache(int Capacity) – Initializes the object with the capacity of the data structure

Int get(int key) – Gets the value of the key if it exists in the cache, otherwise -1 is returned.

Void put(int key, int value) – If the key already exists, change its value; If the key does not exist, insert a key-value pair.

When the cache reaches its capacity, the least frequently used items should be removed before new items are inserted.

In this problem, when there is a tie (that is, two or more keys with the same frequency of use), the most recent and oldest unused key should be removed.

To determine the least-used key, you can maintain a usage counter for each key in the cache. The key with the smallest use count is the key that has not been used for the longest time.

When a key is first inserted into the cache, its usage counter is set to 1 (due to the PUT operation). Perform a GET or put operation on a key in the cache, and the value of the use counter will be incremented.

The functions get and PUT must run in O(1) average time complexity.

Their thinking

1. Construct the node structure

Save the corresponding data information

const LFUNode = function (
  key = "",
  val = "",
  freq = 0,
  pre = null,
  next = null
) {
  this.key = key;
  this.val = val;
  this.freq = freq;
  this.pre = pre;
  this.next = next;
};
Copy the code

2. Construct bidirectional linked lists

Construct a bidirectional linked list with head and tail nodes, head and tail are sentinel nodes, do not store information, only used to mark the head and tail.

const LFULinkLine = function (node) {
  let head = new LFUNode("head");
  let tail = new LFUNode("tail");
  head.next = node;
  tail.pre = node;
  node.pre = head;
  node.next = tail;
  this.head = head;
  this.tail = tail;
};
Copy the code

3, write a list header to add a node method

After inserting a node into the head of the list, the other nodes move back.

LFULinkLine.prototype.addNode = function (node) {
  this.head.next.pre = node;
  node.pre = this.head;
  node.next = this.head.next;
  this.head.next = node;
};
Copy the code

4. Write methods to delete nodes

Remove the node from the linked list.

LFULinkLine.prototype.removeNode = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};
Copy the code

5. Construct LRU cache structure

Capacity is used to store the maximum number of caches, that is, the capacity of the class. Num Stores the amount of data currently stored, which is used to determine whether the maximum capacity is exceeded. MinFreq stores the minimum frequency of the data currently stored. When deleting data, the lowest frequency should be deleted first. KvMap stores detailed node information. The index is the key value of the node. FreqMap stores the linked list information of the corresponding frequency. The index is the FREQ (frequency) of the node. When deleting the node, you can quickly obtain the information about the node to be deleted from this list.

/ * * *@param {number} capacity* /
var LFUCache = function (capacity) {
  this.capacity = capacity;// Maximum cache
  this.num = 0;// The current number
  this.minFreq = 0;// Current minimum frequency
  this.kvMap = new Map(a);// Save the node information
  this.freqMap = new Map(a);// Save the linked list information of the corresponding frequency
};
Copy the code

6. Write the GET method

There are two main cases of GET:

(1) The node exists

• The corresponding node is obtained through kvMap
• Delete the node from freqMap
• Check whether minFreq needs to be modified
• Example Change the freQ of a controller
• Re-insert the node into freqMap
• Returns the value of the node

(2) The node does not exist

If capacity is 0 or the node information does not exist in kvMap, return -1.

/ * * *@param {number} key
 * @return {number}* /
LFUCache.prototype.get = function (key) {
  if (this.capacity === 0) return -1;
  if (!this.kvMap.has(key)) return -1;
  // Obtain the corresponding node through kvMap
  let node = this.kvMap.get(key);
  let linkLine = this.freqMap.get(node.freq);
  // Delete the node from freqMap
  linkLine.removeNode(node);
  // Determine whether minFreq needs to be modified
  / / to empty
  if (linkLine.head.next === linkLine.tail) {
    this.freqMap.delete(node.freq);
    if (this.minFreq == node.freq) this.minFreq++;
  }
  // Change the freq of the controller
  node.freq++;
  // Re-insert the node into freqMap
  if (this.freqMap.has(node.freq)) {
    linkLine = this.freqMap.get(node.freq);
    linkLine.addNode(node);
  } else {
    this.freqMap.set(node.freq, new LFULinkLine(node));
  }
  // Returns the value of the node
  return node.val;
};
Copy the code

7. Write the put method

The PUT operation has the following two scenarios:

(1) Update

• The corresponding node is obtained through kvMap
• Delete the node from freqMap
• Check whether minFreq needs to be modified
• Updating Node Information
• Re-insert the node into freqMap

(2) Deposit

In the case of deposit, there are two cases:

Capacity is full

• Use minFreq to find the node to delete
• Delete the node from freqMap
• Check whether minFreq needs to be modified
• Insert the new node into freqMap
• Update minFreq

Capacity under

• Modify the num
• Insert the new node into freqMap
• Update minFreq

/ * * *@param {number} key
 * @param {number} value
 * @return {void}* /
LFUCache.prototype.put = function (key, value) {
  if (this.capacity === 0) return;
  if (this.kvMap.has(key)) {
    / / update
    // Obtain the corresponding node through kvMap
    let node = this.kvMap.get(key);
    // Delete the node from freqMap
    let linkLine = this.freqMap.get(node.freq);
    linkLine.removeNode(node);
    // Determine whether minFreq needs to be modified
    if (linkLine.head.next === linkLine.tail) {
      if (this.minFreq == node.freq) this.minFreq++;
      this.freqMap.delete(node.freq);
    }
    // Update node information
    node.val = value;
    node.freq++;
    // Re-insert the node into freqMap
    if (this.freqMap.has(node.freq)) {
      linkLine = this.freqMap.get(node.freq);
      linkLine.addNode(node);
    } else {
      linkLine = new LFULinkLine(node);
      this.freqMap.set(node.freq, linkLine); }}else {/ / in
    if (this.capacity == this.num) {/ / is full
      // Use minFreq to find the node to delete
      let freq = this.minFreq;
      let linkLine = this.freqMap.get(freq);
      let node = linkLine.tail.pre;
      // Delete the node from freqMap
      linkLine.removeNode(node);
      this.kvMap.delete(node.key);
      // Determine whether minFreq needs to be modified
      if (linkLine.head.next === linkLine.tail) {
        this.freqMap.delete(node.freq); }}else {
      / / modify num
      this.num++;
    }
    // Insert the new node into freqMap
    let node = new LFUNode(key, value, 0);
    this.kvMap.set(key, node);
    if (this.freqMap.has(0)) {
      let linkLine = this.freqMap.get(0);
      linkLine.addNode(node);
    } else {
      let linkLine = new LFULinkLine(node);
      this.freqMap.set(0, linkLine);
    }
    / / update the minFreq
    this.minFreq = 0; }};Copy the code

code

const LFUNode = function (
  key = "",
  val = "",
  freq = 0,
  pre = null,
  next = null
) {
  this.key = key;
  this.val = val;
  this.freq = freq;
  this.pre = pre;
  this.next = next;
};
const LFULinkLine = function (node) {
  let head = new LFUNode("head");
  let tail = new LFUNode("tail");
  head.next = node;
  tail.pre = node;
  node.pre = head;
  node.next = tail;
  this.head = head;
  this.tail = tail;
};
LFULinkLine.prototype.addNode = function (node) {
  this.head.next.pre = node;
  node.pre = this.head;
  node.next = this.head.next;
  this.head.next = node;
};
LFULinkLine.prototype.removeNode = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};

/ * * *@param {number} capacity* /
var LFUCache = function (capacity) {
  this.capacity = capacity;
  this.num = 0;
  this.minFreq = 0;
  this.kvMap = new Map(a);this.freqMap = new Map(a); };/ * * *@param {number} key
 * @return {number}* /
LFUCache.prototype.get = function (key) {
  if (this.capacity === 0) return -1;
  if (!this.kvMap.has(key)) return -1;
  let node = this.kvMap.get(key);
  let linkLine = this.freqMap.get(node.freq);
  linkLine.removeNode(node);
  / / to empty
  if (linkLine.head.next === linkLine.tail) {
    this.freqMap.delete(node.freq);
    if (this.minFreq == node.freq) this.minFreq++;
  }
  node.freq++;
  if (this.freqMap.has(node.freq)) {
    linkLine = this.freqMap.get(node.freq);
    linkLine.addNode(node);
  } else {
    this.freqMap.set(node.freq, new LFULinkLine(node));
  }
  return node.val;
};

/ * * *@param {number} key
 * @param {number} value
 * @return {void}* /
LFUCache.prototype.put = function (key, value) {
  if (this.capacity === 0) return;
  if (this.kvMap.has(key)) {
    / / update
    let node = this.kvMap.get(key);
    node.val = value;
    let linkLine = this.freqMap.get(node.freq);
    linkLine.removeNode(node);
    if (linkLine.head.next === linkLine.tail) {
      if (this.minFreq == node.freq) this.minFreq++;
      this.freqMap.delete(node.freq);
    }
    node.freq++;
    if (this.freqMap.has(node.freq)) {
      linkLine = this.freqMap.get(node.freq);
      linkLine.addNode(node);
    } else {
      linkLine = new LFULinkLine(node);
      this.freqMap.set(node.freq, linkLine); }}else {
    / / in
    if (this.capacity == this.num) {
      / / is full
      let freq = this.minFreq;
      let linkLine = this.freqMap.get(freq);
      let node = linkLine.tail.pre;
      linkLine.removeNode(node);
      this.kvMap.delete(node.key);

      if (linkLine.head.next === linkLine.tail) {
        this.freqMap.delete(node.freq); }}else {
      this.num++;
    }
    let node = new LFUNode(key, value, 0);
    this.kvMap.set(key, node);
    if (this.freqMap.has(0)) {
      let linkLine = this.freqMap.get(0);
      linkLine.addNode(node);
    } else {
      let linkLine = new LFULinkLine(node);
      this.freqMap.set(0, linkLine);
    }
    this.minFreq = 0; }};/** * Your LFUCache object will be instantiated and called as such: * var obj = new LFUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */
Copy the code