数据结构与算法 / 系统课时

双向链表与最近使用缓存

双向链表与最近使用缓存

LRU 缓存既要按键快速查找数据,又要随访问不断调整新旧顺序。本课用哈希映射定位节点,用双向链表维护使用次序,实现固定容量且平均 O(1) 的 get 与 put。

学习目标

  • 理解双向链表删除和移动已知节点的方式
  • 掌握哈希映射与双向链表在 LRU 中的分工
  • 实现容量淘汰、读取更新顺序和覆盖写入

结构与核心操作

链表使用两个虚拟节点统一边界:head.next 是最近使用节点,tail.prev 是最久未使用节点。哈希映射保存 key -> node,负责平均 O(1) 定位。

LRU 缓存结构与访问顺序变化

任意有效数据节点都同时存在于映射和链表中。移动节点时先从原位置摘除,再插到 head 后;淘汰时必须同时删除链表节点与映射项。

下面是删除操作的片段示例,依赖一个已连接到双向链表中的 node:

python
node.prev.next = node.next
node.next.prev = node.prev

get 命中也表示该键刚被使用,必须移动到最近位置。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)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

双向链表与最近使用缓存

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通