Least Recently Used Algorithm (LRU)

One useful algorithm that can use the LinkedList implementation is the LRU (Least Recently Used) cache algorithm, which is used to keep track of a limited number of recently used items and remove the least recently used item when the cache is full.

To implement an LRU cache using a LinkedList, we can use the LinkedList to keep track of the order in which items were most recently accessed. Each time an item is accessed, we can move it to the front of the LinkedList to indicate that it was the most recently used item. When the cache is full, we can remove the last item in the LinkedList to make room for a new item.

Here's an example implementation of an LRU cache using the LinkedList implementation provided earlier:

class LRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.cache = new LinkedList();
    this.map = new Map();
  }

  get(key) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      this.cache.remove(this.cache.indexOf(node));
      this.cache.unshift(node.data);
      return node.data.value;
    } else {
      return null;
    }
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.data.value = value;
      this.cache.remove(this.cache.indexOf(node));
      this.cache.unshift(node.data);
    } else {
      if (this.cache.getSize() === this.maxSize) {
        const removedKey = this.cache.pop().key;
        this.map.delete(removedKey);
      }
      const newNode = new Node({ key, value });
      this.cache.unshift(newNode);
      this.map.set(key, newNode);
    }
  }
}

In this implementation, the LRU cache uses a LinkedList to keep track of the order in which items were most recently accessed. Each item in the cache is represented as a Node object that contains a key and a value. The get method looks up the key in the cache's Map, moves the corresponding Node object to the front of the LinkedList to indicate that it was the most recently used item, and returns the value associated with the key. The put method first checks if the key already exists in the cache, in which case it updates the corresponding Node object's value and moves it to the front of the LinkedList. If the key doesn't exist, the method creates a new Node object, inserts it at the front of the LinkedList, and adds the key and Node object to the cache's Map. If the cache is full, the method removes the last item in the LinkedList (which is the least recently used item) and deletes the corresponding key from the cache's Map.

An example that uses this LRUCache

• Fibonacci with LRUCache