TypeScript implementation of lru cache

lru-cache.tsx

// The problem can be solved with a HashTable that keeps track of the keys and its values in the double linked list.
// One interesting property about Double Linked List is that the node can remove itself without other reference.
// In addition, it takes constant time to add and remove nodes from the head or tail.

// we need to restrict key types as it is not possible
// to support any type of keys in Association data

/**
 * draw io
 * https://app.diagrams.net/#G1CGQ2rrhcgyjLS9ZYQSHXLsxfqn7vH402
 */

type Key = string | number;

// just for convenience
// type Nullable<T> = T | null;
type Undefinable<T> = T | undefined;

/**
 *
 */
class Node<V> {
  key: Key;
  value?: V;
  next?: Node<V> = undefined;
  prev?: Node<V> = undefined;

  constructor(key: Key, value?: V) {
    this.key = key;
    this.value = value;
  }
}

/**
 * Cache eviction policy: least recently used item removal
 * Tradeoff between space and time,
 * in this case get better time complexity at the cost of more space
 *
 * DoubleLinkedList that I implemented contains pseudo head and tail nodes to mark the boundary,
 * so that we don't need to check the NULL node during the update. This makes the code
 * more concise and clean, and also it is good for the performance.
 *
 */
export class LRUCache<V> {
  public readonly size: number;
  public readonly head = new Node<V>('head');
  public readonly tail = new Node<V>('tail');
  public map: Record<string, unknown>;

  constructor(capacity: number) {
    this.size = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;

    this.map = {};
  }

  /**
   * Space complexity: O(1)
   * Time complexity:
   */
  get(key: Key): Undefinable<V> {
    const node = this.map[key] as Node<V>;

    this.dequeue(node); // update priority
    this.enqueue(node); // this causes this item to be moved to the front

    return node.value;
  }

  /**
   *
   */
  put(key: Key, value: V): void {
    const node = this.map[key] as Node<V>;

    if (!node) {
      const newNode = new Node(key, value);
      // if cache is full we need evict last record using tail
      if (Object.keys(this.map).length === this.size) {
        const key = this.tail?.prev?.key;
        if (key) {
          delete this.map[key]; // delete from hashmap
        }
        this.dequeue(this.tail.prev); // delete from LinkedList
      }

      this.map[key] = newNode;
      this.enqueue(newNode);
    } else {
      // updates value and its priority in the cache
      this.dequeue(node);

      node.value = value;
      this.enqueue(node);
    }
  }

  print(): void {
    console.log('not implemented yet');
  }

  /**
   * putting item at the front of cache
   * @param node
   * @returns
   */
  private enqueue(node: Node<V>): void {
    const headNext = this.head.next; // take head's next ref for later use

    this.head.next = node;
    node.prev = this.head;

    node.next = headNext;
    headNext!.prev = node;

    // (this.head.next as Undefinable<Node<V>>) = node;
    // node.prev = this.head as unknown as Undefinable<Node<V>>;

    // node.next = headNext as unknown as Undefinable<Node<V>>;
    // (headNext!.prev as Undefinable<Node<V>>) = node;
  }

  private dequeue(node: Node<V> | undefined): void {
    if (!node) return;

    const prevNode: Undefinable<Node<V>> = node.prev;
    const nextNode: Undefinable<Node<V>> = node.next;

    // this.tail.prev =
    // needs improvement
    if (prevNode) prevNode.next = nextNode;
    if (nextNode) nextNode.prev = prevNode;
  }
}

/**
 * Sample usage
 */

const lru = new LRUCache<string>(4);

// for brevity, values skipped only keys shown in comments
// head -> [head, ..., tail] <- tail

lru.put(3, 'ramda'); // [3]
lru.put(2, 'fabric'); // [2, 3]
lru.put(5, 'axios'); // [5, 2, 3] or ['axios', 'fabric', 'ramda'] became full

lru.get(3); // [3, 5, 2]

lru.put(11, 'jest'); // [11, 3, 5, 2]
lru.put(8, 'vue'); // [8, 11, 3, 5]
lru.put(2, 'react'); // [2, 8, 11, 3]

lru.get(11); // [11, 2, 8, 3]
lru.get(1); // [] // miss

lru.put(1, 'styled'); // [1, 11, 2, 8]

lru.print(); // [1, 11, 2, 8]