lruCache.ts

class ListNode {
  value: number;
  pre: ListNode | null;
  next: ListNode | null;
  key: number;

  constructor(
    key: number,
    value: number,
    pre: ListNode | null,
    next: ListNode | null
  ) {
    this.key = key;
    this.value = value;
    this.pre = pre;
    this.next = next;
  }
}

class LRUCache {
  private capacity: number;
  private maxCapacity = 100000;
  private head: ListNode;
  private tail: ListNode;
  private map: Map<number, ListNode> = new Map();

  constructor(capacity: number) {
    if (capacity > this.maxCapacity) {
      throw Error("should less or equal to 100000");
    }
    this.capacity = capacity;
    this.head = new ListNode(0, 0, null, null);
    this.tail = new ListNode(0, 0, null, null);
    this.head.next = this.tail;
    this.tail.pre = this.head;
  }

  get(key: number) {
    // access by key and move it to the front
    const node = this.map.get(key);
    if (node) {
      this.moveToFront(node);
      return node.value;
    }
    return -1;
  }

  put(key: number, value: number) {
    // put it to the front if capacity not full
    // if the capacity is full, remove the least used
    const node = this.map.get(key);
    if (node) {
      node.value = value;
      this.moveToFront(node);
      return;
    }
    const newNode = new ListNode(key, value, null, null);
    if (this.capacity === this.map.size) {
      this.remove(this.tail.pre as ListNode);
      this.prepend(newNode);
      return;
    }

    // append new ListNode to the front
    this.prepend(newNode);
  }

  private prepend(node: ListNode): ListNode {
    // <- h -> origin
    //       ! newNode
    const originalNext = this.head.next as ListNode;
    originalNext.pre = node;
    node.next = originalNext;
    this.head.next = node;
    node.pre = this.head;
    this.map.set(node.key, node);
    return node;
  }

  private moveToFront(node: ListNode) {
    // 1 <- 2 -> 3
    const originalPre = node.pre as ListNode;
    const originalNext = node.next as ListNode;
    originalPre.next = originalNext;
    originalNext.pre = originalPre;
    this.prepend(node);
  }

  private remove(node: ListNode) {
    // 1 <- 2 -> 3
    const originalPre = node.pre as ListNode;
    const originalNext = node.next as ListNode;
    originalPre.next = originalNext;
    originalNext.pre = originalPre;
    node.pre = null;
    node.next = null;
    this.map.delete(node.key);
  }
}

const size = 3;
const LRUCacheIns = new LRUCache(size);

console.log("should be -1", LRUCacheIns.get(1));

LRUCacheIns.put(1, 2);
console.log("should be 2", LRUCacheIns.get(1));

LRUCacheIns.put(1, 3);
console.log("should be 3", LRUCacheIns.get(1));

LRUCacheIns.put(2, 2);
console.log("should be 2", LRUCacheIns.get(2));

LRUCacheIns.put(3, 4);
console.log("should be 4", LRUCacheIns.get(3));

LRUCacheIns.put(4, 5);
console.log("should be 5", LRUCacheIns.get(4));
console.log("should be -1", LRUCacheIns.get(1));

console.log("should be 2", LRUCacheIns.get(2));
console.log("should be 4", LRUCacheIns.get(3));
console.log("should be 5", LRUCacheIns.get(4));

LRUCacheIns.put(3, 6);

console.log("should be 2", LRUCacheIns.get(2));
console.log("key 3 should be update to 6", LRUCacheIns.get(3));
console.log("should be 5", LRUCacheIns.get(4));