数据结构与算法 / 系统课时
双向链表与最近使用缓存
双向链表与最近使用缓存
LRU 缓存既要按键快速查找数据,又要随访问不断调整新旧顺序。本课用哈希映射定位节点,用双向链表维护使用次序,实现固定容量且平均 O(1) 的 get 与 put。
学习目标
- 理解双向链表删除和移动已知节点的方式
- 掌握哈希映射与双向链表在 LRU 中的分工
- 实现容量淘汰、读取更新顺序和覆盖写入
结构与核心操作
链表使用两个虚拟节点统一边界:head.next 是最近使用节点,tail.prev 是最久未使用节点。哈希映射保存 key -> node,负责平均 O(1) 定位。

任意有效数据节点都同时存在于映射和链表中。移动节点时先从原位置摘除,再插到 head 后;淘汰时必须同时删除链表节点与映射项。
下面是删除操作的片段示例,依赖一个已连接到双向链表中的 node:
python
node.prev.next = node.next
node.next.prev = node.prevget 命中也表示该键刚被使用,必须移动到最近位置。put 更新已有键时修改值并移动;新增键导致容量超限时,淘汰 tail.prev。
主示例
python
from dataclasses import dataclass
from typing import Optional
@dataclass
class Node:
key: str
value: int
prev: Optional["Node"] = None
next: Optional["Node"] = None
class LRUCache:
def __init__(self, capacity: int) -> None:
if capacity <= 0:
raise ValueError("capacity 必须大于 0")
self.capacity = capacity
# 映射负责定位,链表负责维护新旧顺序
self.nodes: dict[str, Node] = {}
self.head = Node("<head>", 0)
self.tail = Node("<tail>", 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
# 仅摘除连接,不在这里修改映射
assert node.prev is not None and node.next is not None
node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
def _add_front(self, node: Node) -> None:
first = self.head.next
assert first is not None
node.prev = self.head
node.next = first
self.head.next = node
first.prev = node
def _move_to_front(self, node: Node) -> None:
self._remove(node)
self._add_front(node)
def get(self, key: str) -> Optional[int]:
node = self.nodes.get(key)
if node is None:
return None
self._move_to_front(node)
return node.value
def put(self, key: str, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._move_to_front(node)
return
node = Node(key, value)
self.nodes[key] = node
self._add_front(node)
if len(self.nodes) > self.capacity:
# tail 前的真实节点就是最久未使用项
oldest = self.tail.prev
assert oldest is not None and oldest is not self.head
self._remove(oldest)
del self.nodes[oldest.key]
def keys(self) -> list[str]:
result: list[str] = []
current = self.head.next
while current is not None and current is not self.tail:
result.append(current.key)
current = current.next
return result
def main() -> None:
cache = LRUCache(2)
cache.put("A", 100)
cache.put("B", 200)
print("初始:", cache.keys())
print("读取 A:", cache.get("A"))
print("读取后:", cache.keys())
cache.put("C", 300)
print("写入 C:", cache.keys())
print("读取 B:", cache.get("B"))
if __name__ == "__main__":
main()运行命令:
bash
python lru_cache.py预期输出:
text
初始: ['B', 'A']
读取 A: 100
读取后: ['A', 'B']
写入 C: ['C', 'A']
读取 B: None边界与复杂度
虚拟节点不进入映射,也不计入容量。容量必须大于 0,否则每次写入都无法形成稳定状态。每次新增、移动和淘汰后,都应保持前后引用成对更新,否则可能出现遍历断裂或错误环。
该实现不是线程安全的。并发环境下,映射更新、链表移动和容量淘汰必须由同一把锁保护,不能分别加锁。
在哈希查找平均 O(1) 的前提下,定位、摘除、头插和尾部淘汰都是 O(1),因此 get 与 put 的平均时间复杂度均为 O(1)。空间复杂度为 O(capacity)。
按自己的节奏,确认真正理解。