带你读《图解算法小抄》九、LRU（2）

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }}
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.cache = new Map();
    this.head = new Node(0, 0); // 伪头节点
    this.tail = new Node(0, 0); // 伪尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  get(key) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
this.moveToHead(node);
      return node.value;
    }
    return -1;
  }
  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.moveToHead(node);
    } else {
      const newNode = new Node(key, value);
      this.cache.set(key, newNode);
      this.addToHead(newNode);
      this.size++;
      if (this.size > this.capacity) {
        const tailNode = this.removeFromTail();
        this.cache.delete(tailNode.key);
        this.size--;
      }
    }
  }
  moveToHead(node) {
    this.removeFromList(node);
    this.addToHead(node);
  }
  removeFromList(node) {
    const prevNode = node.prev;
    const nextNode = node.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }
  addToHead(node) {
    const nextNode = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    node.next = nextNode;
    nextNode.prev = node;
  }
  removeFromTail() {
    const tailNode = this.tail.prev;
    this.removeFromList(tailNode);
    return tailNode;
  }}