LRU

class ListNode {
  constructor(value = null, key = null, prev = null, next = null) {
    this.value = value;
    this.key = key;
    this.prev = prev;
    this.next = next;
  }
}

class LruCache {
  constructor(MAX_SIZE) {
    this.MAX_SIZE = MAX_SIZE;
    this.size = 0;
    this.headGuard = new ListNode();
    this.tailGuard = new ListNode();
    this.headGuard.next = this.tailGuard;
    this.tailGuard.prev = this.headGuard;
    this.lookup = new Map();
  }

  #moveToFront(node) {
    node.next.prev = node.prev;
    node.prev.next = node.next;
    this.#addToFront(node);
  }

  #removeFromBack() {
    if (this.headGuard.next === this.tailGuard) {
      return;
    }
    this.headGuard.next = this.headGuard.next.next;
    this.headGuard.next.prev = this.headGuard;
  }

  #addToFront(node) {
    node.prev = this.tailGuard.prev;
    node.next = this.tailGuard;
    this.tailGuard.prev = node;
    node.prev.next = node;
  }

  get(key) {
    const node = this.lookup.get(key);
    if (!node) return null;
    this.#moveToFront(node);
    return node.value;
  }

  set(key, value) {
    let node = this.lookup.get(key);
    if (node) {
      this.#moveToFront(node);
      return;
    }
    if (this.size === this.MAX_SIZE) {
      this.lookup.delete(this.headGuard.next.key);
      this.#removeFromBack();
    } else {
      this.size++;
    }
    node = new ListNode(value, key);
    this.#addToFront(node);
    this.lookup.set(key, node);
  }
}

const cache = new LruCache(3);
console.log(cache.get("a"));
cache.set("a", "foo");
console.log(cache.get("a"));
cache.set("b", "bar");
cache.set("c", "baz");
console.log(cache.get("c"));
console.log(cache.get("a"));
console.log(cache.get("b"));
cache.set("d", "qux");
console.log(cache.lookup);