不用collections.deque而手写双向链表，因其不支持o(1)按值删除和节点指针访问；手写链表通过哨兵节点、显式初始化prev/next、维护_size计数器及手动断引用，实现稳定o(1)移动/删除/插入。

为什么不用 collections.deque 而要手写双向链表？

因为 deque 不支持 O(1) 时间按值删除（需先 list.index() 或遍历），也不暴露内部节点指针，无法做 LRU 缓存中「把某节点快速移到头部」这类操作。手写双向链表的核心价值是：节点可被任意移动、删除、插入，且所有操作都稳定 O(1)（前提是已有该节点引用）。

Node 类必须带 prev 和 next，且初始化要清空

常见错误是只设 next、漏掉 prev，或初始化时没置为 None，导致后续 if node.prev 判断出错。节点本身不负责维护链表结构，只承载数据和指针。

示例：

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None  # 必须显式设为 None
        self.next = None  # 同上

链表头尾用哨兵节点（dummy nodes）能大幅减少边界判断

不用单独处理空链表、单节点、插头部、删尾部等 case。加 self.head 和 self.tail 两个永不删除的哨兵，实际数据节点永远在它们之间。

python学习

Python 编程学习助手 skill，面向零基础用户。 当用户表达以下意图时触发： - 学习 Python 基础概念（变量、数据类型、循环、函数、类等） - 请求 Python 练习题或测验 - 请求审查或调试 Python 代码 - 请求 Python 项目实战指导（爬虫、数据分析、Web 开发等入门项目） - 泛化表述如"教我 Python""我想学编程""Python 怎么写""帮我学 Python" 此 skill

下载

关键操作逻辑：

• 插入到头部：new_node.next = self.head.next → self.head.next.prev = new_node → self.head.next = new_node → new_node.prev = self.head
• 按引用删除节点：node.prev.next = node.next → node.next.prev = node.prev（两步必须都做，否则断链）
• 注意：删除后建议手动置 node.prev = node.next = None，避免悬垂引用影响 GC 或调试

Python 中双向链表的性能陷阱：不要在循环里反复查 len() 或遍历

手写链表没有内置长度缓存，__len__ 如果每次遍历数节点就是 O(n)。LRU 等场景常需判断容量，务必维护一个 self._size 计数器，增删节点时同步更新。

另外，避免写 for i in range(len(ll)): 这类代码——它会让复杂度从 O(k) 退化成 O(k·n)。

容易被忽略的一点：Python 的引用计数机制下，若节点被外部变量强引用（比如你把它存进 dict），即使从链表摘除，也不会自动释放内存。需要确保业务层主动解除引用，或使用 weakref 管理反向关系。

Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！