lru-cache.js

export class ListNode {
  constructor({
    prev,
    next,
    val,
    hNext,
  }) {
    this.prev = prev;
    this.next = next;
    this.val = val;
    this.hNext = hNext;
  }
}

export class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;

    this.hash = null;
    this.head = null;
  }

  get = (key) => {
    if (this.hash) {
      const node = this.hash.get(key);

      if (node) {
        if (node === this.tail) {
          if (!this.tail.prev) {
            return node.val;
          }

          this.tail = this.tail.prev;
          this.tail.next = null;
        }

        if (node.prev) {
          node.prev.next = node.next;
        }

        if (node.next) {
          node.next.prev = node.prev;
        }

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

        return node.val;
      }
    }

    return -1;
  }

  put = (key, data) => {
    const node = new ListNode({
      prev: null,
      val: data,
      next: null,
      hNext: key,
    });

    if (this.hash && this.tail && this.head) {
      if (this.hash.get(key)) {
        this.get(key);
      } else {
        if (this.hash.size >= this.capacity) {
          this.hash.delete(this.tail.hNext);
          this.tail = this.tail.prev;

          if (this.tail) {
            this.tail.next = null;
          }
        }

        this.head.prev = node;
        node.next = this.head;
        this.head = node;
      }
    } else {
      this.hash = new Map();

      this.head = node;
      this.tail = node;
    }

    this.hash.set(key, node);
  }
}

export default LRUCache;