如何在 JavaScript 中实现一个 LRU Cache？

LRU (Least Recently Used) 缓存通过哈希表和双向链表实现，确保 get 和 put 操作的时间复杂度为 O(1)。实现思路如下：

1. 双向链表节点：存储键值对，并维护前后指针。
2. 哈希表：快速定位节点位置。
3. 容量管理：超出容量时移除链表尾部的最近最少使用节点。

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

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // 存储 key -> node 映射
    this.head = new ListNode(0, 0); // 哨兵头节点
    this.tail = new ListNode(0, 0); // 哨兵尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // 将节点移动到链表头部（表示最近使用）
  _moveToHead(node) {
    this._removeNode(node);
    this._addToHead(node);
  }

  // 移除节点
  _removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // 在头部添加节点
  _addToHead(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  // 移除尾部节点（最近最少使用）
  _removeTail() {
    const node = this.tail.prev;
    this._removeNode(node);
    return node; // 返回被移除的节点以便删除 Map 中的键
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._moveToHead(node); // 更新为最近使用
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this._moveToHead(node); // 更新值并移至头部
    } else {
      const node = new ListNode(key, value);
      this.map.set(key, node);
      this._addToHead(node); // 新节点添加到头部
      if (this.map.size > this.capacity) {
        const removed = this._removeTail(); // 超出容量时移除尾部
        this.map.delete(removed.key);
      }
    }
  }
}

// 使用示例
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 返回 1
cache.put(3, 3); // 移除 key 2
console.log(cache.get(2)); // 返回 -1 (已移除)

关键操作说明：

• _moveToHead：在访问或更新节点时将其移至链表头部。
• _removeTail：当缓存满时删除尾部节点（LRU 策略）。
• 哈希表：确保 O(1) 时间访问节点，双向链表维护使用顺序。