第4章｜链表

Unit 13 · 哈希表与双向链表综合设计

← Unit 12

仅本次页面有效

U13

LRU CacheHash Map · Doubly Linked List

定位交给哈希表，
顺序交给双向链表。

LRU 缓存要求查询、更新、移动和淘汰都在平均 O(1) 时间完成。单一结构无法同时满足这些要求，因此本单元将整章链表能力编译成一个真实的数据结构设计。

已恢复上次学习进度阶段、动画、代码与编辑框高度均已恢复。

LeetCode #146 题目模型所有 get / put 操作要求平均 O(1)

题目要求

设计一个遵循最近最少使用策略的缓存。get(key) 在键存在时返回值并将该键标记为最近使用；put(key, value) 更新或插入键值，并在超过容量时淘汰最久未使用的键。

class LRUCache: def __init__(self, capacity: int): ... def get(self, key: int) -> int: ... def put(self, key: int, value: int) -> None: ...

复杂度目标

get：平均 O(1)
put：平均 O(1)
空间：O(capacity)

操作示例

capacity = 2 put(1,1) → [1] put(2,2) → [2,1] get(1) → 1，顺序变为 [1,2] put(3,3) → 淘汰 2，顺序变为 [3,1] get(2) → -1

顺序约定

本页所有链表从左到右表示：最近使用 MRU → 最久未使用 LRU。业务节点位于两个哨兵 head 与 tail 之间。

从 Unit 12 到 Unit 13：映射继续负责“身份定位”，链表开始负责“顺序修改”

Unit 12 · 节点复制

哈希映射保存“原节点 → 副本节点”，解决复杂引用中的对象定位。

→

Unit 13 · LRU

哈希映射保存“key → 链表节点”，双向链表负责 O(1) 删除、移动和淘汰。

LRU / MRU

LRU 是最久未使用节点；MRU 是最近使用节点。每次成功访问都会改变顺序。

Sentinel 哨兵

head 与 tail 不保存业务数据，用来统一空链表、首节点和尾节点的边界操作。

Bidirectional Unlink

删除任意节点时，同时更新前驱的 next 与后继的 prev，才能保持双向结构一致。

Composite Structure

哈希表提供 O(1) 定位；双向链表提供 O(1) 顺序修改。两者必须始终同步。

认知任务 1

访问一个已有键后，谁会成为新的最近使用节点？

先跟随标准操作序列，不要急着选择数据结构。

缓存顺序与节点动画步骤 1 / 10

← 最近使用 MRU最久未使用 LRU →

缓存尚为空，准备执行第一个 put。

哈希定位O(1)

根据 key 直接得到节点对象。

双向改边O(1)

已知节点后直接修改相邻引用。

capacity=2，依次 put(1)、put(2)、get(1) 后，谁是 LRU？

选择后会停留在当前问题，由你手动继续。

关键表达式补全主结构已经给出，只补同步改边

class Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() def _remove(self, node): previous = node.prev following = node.next def _add_to_front(self, node): def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] return node.value def put(self, key: int, value: int) -> None: # 已有键：更新并移动；新键：创建并插到最前。 ... if len(self.cache) > self.capacity: lru = self._remove(lru)

先保证两个哨兵互连，再完成 remove、add_to_front 和淘汰同步。

分层提示：先定位职责，再补表达式

层 1｜两个哨兵先形成稳定空结构
head.next 应指向 tail，tail.prev 应指向 head。这样空链、首节点和尾节点都无需特殊分支。

层 2｜删除不是“清空 node”，而是让两个邻居互相绕过它
先保存 previous = node.prev、following = node.next，再分别修改 previous.next 与 following.prev。

层 3｜插到 MRU 端需要四条局部赋值
node 的前驱是 head，后继是原 head.next；随后让原首节点的 prev 指回 node，最后更新 head.next。

层 4｜命中已有键时必须刷新使用顺序
get 命中后、put 更新已有键后，都应复用“先 remove，再 add_to_front”的移动操作。

层 5｜淘汰必须同时修改两套状态
淘汰对象来自 tail.prev。将其从双向链表删除后，还必须按 lru.key 从 cache 删除映射，保持一一对应。

代码—哈希表—双向链表联动1 / 1

operationinit

order[]

cache{}

return—

进入构造函数。

完成主代码或完整轨迹后进入 #460「LFU 缓存」官方迁移各模块可独立进入，也可以按推荐顺序训练。

LeetCode 官方迁移题 · Hard

#460 LFU 缓存

LRU 只维护时间顺序；LFU 需要先按访问频率选择淘汰桶，再在同频节点中按 LRU 淘汰。迁移重点不是背一份长代码，而是理解三份状态怎样协同保持平均 O(1)。

打开官方原题

题目要求

实现 LFUCache(capacity)、get(key) 和 put(key,value)。键不存在时 get 返回 -1；容量满时先淘汰访问频率最低的键，若频率相同，则淘汰其中最久未使用的键。

class LFUCache: def __init__(self, capacity: int): ... def get(self, key: int) -> int: ... def put(self, key: int, value: int) -> None: ...

关键规则与约束

新插入键的使用计数从 1 开始；
成功的 get，以及对已有键的 put，都会使频率加一；
同频率时使用 LRU 规则打破平局；
get 与 put 均要求平均 O(1)；
1 ≤ capacity ≤ 10⁴，调用次数最多 2×10⁵。

官方操作序列LFUCache(2), put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4)输出：[null,null,null,1,null,-1,3,null,-1,3,4]

读题门槛

① key=1 与 key=3 的频率相同，谁先被淘汰？

② 对已存在的 key 执行 put(key,newValue) 后，频率如何变化？

可直接进入结构对照，也可以先完成这两题。

从一条 LRU 链，扩展为“频率桶 + 桶内 LRU”

#146 LRU	#460 LFU	迁移含义
`cache[key] → node`	`nodes[key] → node`	O(1) 定位节点保持不变
一条 MRU→LRU 双向链	`freq_lists[f]` 各维护一条 LRU 链	先按频率分桶，再在桶内维护时间
`tail.prev` 是淘汰对象	`freq_lists[min_freq]` 的 LRU 端是淘汰对象	`min_freq` 直接定位最低频桶
访问后移动到链头	从旧频桶删除，频率加一，插入新频桶 MRU 端	一次 touch 跨越两条链

排列一次成功访问 `_touch(node)` 的依赖顺序

点击下列步骤组成执行序列。错误顺序会清空重试。

尚未排列

先删除旧桶中的节点，才能判断旧的最小频率桶是否已经清空。

四个语义槽位：先确定职责，再组装代码

槽位 A｜全局状态必须同时支持节点定位、频率分桶和最低频率定位。槽位 B｜离开旧频率桶删除的是桶内链表位置，不是删除缓存键。槽位 C｜维护最小频率只有当前最低频桶被清空，最低频率才上移。槽位 D｜淘汰与新键频率优先，时间只负责同频平局。

四项全部正确后，才会开放官方样例轨迹。

组装后的状态机

touch(node):
  从 freq_lists[node.freq] 删除
  若清空了 min_freq 桶：min_freq += 1
  node.freq += 1
  加入 freq_lists[node.freq] 的 MRU 端

evict():
  从 freq_lists[min_freq] 的 LRU 端删除
  同步删除 nodes[victim.key]

官方样例运行轨迹1 / 11

LFUCache(2)

min_freq：0返回：null淘汰：—

初始化容量为 2 的缓存。

轨迹中必须观察的两层优先级

第一层：频率始终从 min_freq 对应的桶选择淘汰对象。

第二层：最近使用同一频率桶内部按 MRU→LRU 排列，淘汰桶尾节点。

新键规则新插入节点频率为 1，因此插入后 min_freq = 1。

独立重写 LFU 核心

辅助类 Node 与 DoublyLinkedList 已提供 add_front/remove/pop_lru/is_empty。请独立实现 LFUCache 的状态、_touch、get 与 put。

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # TODO: nodes、freq_lists、min_freq

    def _touch(self, node):
        # TODO: 从旧频率桶移出，维护 min_freq，频率加一并加入新桶
        pass

    def get(self, key: int) -> int:
        # TODO
        pass

    def put(self, key: int, value: int) -> None:
        # TODO
        pass

必须先把官方样例运行到最后一步。检查器关注结构职责，不要求变量命名完全一致。

完成后停留在本页

这是链表章节终局。可以继续复看 LRU 与 LFU 的结构差异，不会自动跳转。

Unit 13 Skill 卡：用复合结构同时获得 O(1) 定位与 O(1) 顺序修改

你已经完成 LRU 主结构，并通过官方 LFU 样例与独立重写验证了“频率优先、同频按最近使用”的两级淘汰逻辑。页面会停留在这里。

触发信号既要按 key 快速定位，又要维护动态访问顺序

核心表示cache: key → node + 双向链表 MRU → LRU

核心不变量映射与链表业务节点一一对应，tail.prev 始终是 LRU

核心操作remove、add_to_front、move_to_front、evict

常见错误只更新 map、漏改 prev、已有键重复建节点、淘汰哨兵

复杂度get / put 平均 O(1)，空间 O(capacity)

CH04

链表章节完成你已经从节点、可达性和局部改边，走到快慢指针、复杂引用复制，以及哈希表与双向链表的系统组合。

定位交给哈希表，顺序交给双向链表。

题目要求

复杂度目标

操作示例

顺序约定

从 Unit 12 到 Unit 13：映射继续负责“身份定位”，链表开始负责“顺序修改”

capacity=2，依次 put(1)、put(2)、get(1) 后，谁是 LRU？

#460 LFU 缓存

题目要求

关键规则与约束

读题门槛

从一条 LRU 链，扩展为“频率桶 + 桶内 LRU”

排列一次成功访问 _touch(node) 的依赖顺序

四个语义槽位：先确定职责，再组装代码

轨迹中必须观察的两层优先级

独立重写 LFU 核心

Unit 13 Skill 卡：用复合结构同时获得 O(1) 定位与 O(1) 顺序修改

定位交给哈希表，
顺序交给双向链表。

排列一次成功访问 `_touch(node)` 的依赖顺序