链表专题(九)：应用篇的无冕之王——「LRU 缓存机制」

场景想象：

你有一个书架（缓存），容量有限（比如只能放 3 本书）。

规则是 “最近最少使用 (Least Recently Used)” 淘汰：

1. 读取：如果你读了一本书，它就变得“新鲜”了，要把它抽出来放到最前面。
2. 插入：
   • 如果书架没满，新书直接插到最前面。
   • 如果书架满了，必须把最后面那本（最久没人看的那本）扔掉，然后把新书插到最前面。

技术难点：

我们需要两个操作：get（查找）和 put（插入/更新）。

题目要求这两个操作的时间复杂度必须都是 $O(1)$。

• 只用数组？ 插入/删除慢（$O(N)$）。
• 只用链表？ 查找慢（$O(N)$）。
• 只用对象/Map？ 没办法维护“谁是最新的、谁是最旧的”这种顺序。

终极方案：哈希表 + 双向链表

• 哈希表 (Map)：负责 $O(1)$ 找到某个节点。
• 双向链表 (Double Linked List)：负责 $O(1)$ 移动节点位置（因为双向链表删除节点不需要遍历找前驱）。

力扣 146. LRU 缓存

https://leetcode.cn/problems/lru-cache/

题目分析：

• 输入：capacity (容量)。
• 实现：
  • get(key): 如果存在，返回 value，并把它移到最新位置；不存在返回 -1。
  • put(key, value): 如果 key 存在，更新 value 并移到最新；如果不存在，插入新节点（可能需要淘汰最老的）。

核心思维：虚头虚尾 + Map 映射

为了操作方便，我们给双向链表加上 Dummy Head 和 Dummy Tail。

• Head 右边：永远是最新的数据。
• Tail 左边：永远是最旧的数据（淘汰候补）。

代码实现 (JavaScript)

这是一道工程题，代码量稍大，但逻辑非常模块化。

JavaScript

// 1. 定义双向链表节点 class Node { constructor(key, value) { this.key = key; this.value = value; this.prev = null; this.next = null; } } // 2. LRU 缓存类 class LRUCache { /** * @param {number} capacity */ constructor(capacity) { this.capacity = capacity; this.map = new Map(); // key -> Node // 创建虚拟头尾节点 this.head = new Node(0, 0); this.tail = new Node(0, 0); // 连起来：head <-> tail this.head.next = this.tail; this.tail.prev = this.head; // 当前节点数量 this.size = 0; } /** * @param {number} key * @return {number} */ get(key) { if (!this.map.has(key)) { return -1; } // 取出节点 const node = this.map.get(key); // 【关键】既然读了它，它就变“新”了，必须移动到链表头部 this.moveToHead(node); return node.value; } /** * @param {number} key * @param {number} value * @return {void} */ put(key, value) { if (this.map.has(key)) { // 情况 1：key 已存在，修改值，并移到头部 const node = this.map.get(key); node.value = value; this.moveToHead(node); } else { // 情况 2：key 不存在，新建节点 const newNode = new Node(key, value); this.map.set(key, newNode); this.addToHead(newNode); // 放到头部 this.size++; // 检查是否超容 if (this.size > this.capacity) { // 淘汰最久未使用的（也就是 tail 前面那个） const removedNode = this.removeTail(); this.map.delete(removedNode.key); // 别忘了从 Map 里也删掉 this.size--; } } } // --- 内部辅助函数 (这就是链表操作的基本功) --- // 1. 将节点添加到头部 (head 之后) addToHead(node) { node.prev = this.head; node.next = this.head.next; this.head.next.prev = node; this.head.next = node; } // 2. 删除一个节点 (双向链表删除 O(1)) removeNode(node) { node.prev.next = node.next; node.next.prev = node.prev; } // 3. 把一个已有节点移到头部 moveToHead(node) { this.removeNode(node); // 先从原来的位置断开 this.addToHead(node); // 再插到头部 } // 4. 移除尾部节点 (用于淘汰) removeTail() { // tail.prev 才是真正的最后一个有效节点 const node = this.tail.prev; this.removeNode(node); return node; // 返回被删的节点，因为外层还需要它的 key 来删 Map } } 

深度模拟

假设 capacity = 2。

1. put(1, 1): Map {1: Node(1)}. List: Head <-> 1 <-> Tail.
2. put(2, 2): Map {1: Node(1), 2: Node(2)}. List: Head <-> 2 <-> 1 <-> Tail. (2最新)
3. get(1): 读了 1。1 变新了，移到头。
   • List: Head <-> 1 <-> 2 <-> Tail.
4. put(3, 3): 满员了！需要淘汰。
   • 淘汰谁？Tail 前面的那个，也就是 2。
   • Map 删除 2。
   • 插入 3。List: Head <-> 3 <-> 1 <-> Tail.
5. get(2): 此时 Map 里没有 2 了，返回 -1。