标准答案
- Map 保存 key 到双向链表节点的映射。
- get 命中和 put 更新都把节点移到头部；超过容量时删除尾部并从 Map 移除。
- 每次操作的时间复杂度 O(1)，空间复杂度 O(capacity)，边界包括容量为 0 和更新已有 key。
题目解析
LRU 的两个操作分别需要两种能力：Map 负责按 key 找到节点，双向链表负责把节点从当前位置摘下并移动到头部。两者结合后 get、更新和淘汰都不需要扫描。
头部代表最近使用，尾部代表最久未使用。更新已有 key 要保留节点或替换值并移动到头部；超出容量时先从链表删除尾部，再从 Map 删除对应 key。
容量为零、重复 set、未命中和 value 为 undefined 都要有明确语义。操作复杂度 O(1)，空间复杂度 O(capacity)，前提是链表指针维护始终正确。
代码示例
省略节点类的完整 LRU 核心：
TypeScript
get(key: string) {
const node = this.map.get(key)
if (!node) return undefined
this.remove(node); this.addFirst(node)
return node.value
}
set(key: string, value: string) {
const old = this.map.get(key)
if (old) { old.value = value; this.remove(old); this.addFirst(old); return }
const node = { key, value, prev: null, next: null }
this.map.set(key, node); this.addFirst(node)
if (this.map.size > this.capacity) {
const last = this.removeLast(); this.map.delete(last.key)
}
}常见误区
- 误区：只用 Map 却声称能按访问顺序 O(1) 淘汰。改正：需要 Map 加双向链表，或使用明确支持该语义的数据结构。
- 误区：更新已有 key 后没有移动到头部。改正：set 命中也代表最近使用，必须刷新链表顺序。
- 误区：容量为 0 时仍保留节点。改正：在写入前处理零容量，保证 Map 和链表都不留下条目。