Python高效双向循环链表实现方法

本文深入剖析了Python中高效实现双向循环链表的关键原则与常见陷阱，强调除非有特殊需求（如LRU缓存、编辑器光标管理或C扩展集成），否则应优先选用内置list或collections.deque；而真正需要手写时，必须采用自循环哨兵节点初始化和显式size计数器来统一空链、单节点与多节点下的行为，避免边界错误，并通过严谨的指针操作顺序、安全迭代终止条件及原子化长度维护，确保结构鲁棒、高效且符合循环链表的本质语义。

为什么直接用 list 或 deque 就别手写双向循环链表

除非你在实现底层数据结构课设、调试内存布局，或需要精确控制节点指针（比如配合 C 扩展做对象生命周期管理），否则 list 和 collections.deque 已经是 O(1) 头尾操作 + 内存连续/块状分配的工业级解法。手写双向循环链表的唯一合理动机是：你需要在任意节点处做 insert_before、remove、splice，且不希望触发整体拷贝或索引偏移——比如 LRU 缓存淘汰、编辑器光标邻接链、图的邻接表动态边插入。

Node 类必须显式处理 self.next == self 和 self.prev == self

这是循环链表最易漏的边界。空链表不能留 None 指针，否则所有操作都要加 if 判空，失去“循环”语义。正确做法是让头节点（哨兵）自指：

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = self
        self.prev = self

这样 head.next is head 和 head.prev is head 恒成立，插入、删除逻辑可统一，无需分支判断是否为空链。

insert_after 和 insert_before 的参数顺序容易反

常见错误是把新节点传给旧节点的 insert_after(new_node)，但实际应由旧节点接收新节点并完成链接。正确接口应是：

• node.insert_after(new_node)：把 new_node 插到 node 后面
• node.insert_before(new_node)：把 new_node 插到 node 前面

内部实现只改四条指针：

def insert_after(self, new_node):
    new_node.next = self.next
    new_node.prev = self
    self.next.prev = new_node
    self.next = new_node

注意顺序：必须先设 new_node.next 和 new_node.prev，再更新原链上相邻节点的指针；否则中间状态会断链。

迭代器必须检测是否回到哨兵节点

如果用 while current is not head: 遍历，空链表会无限循环（因为 head.next is head）。正确终止条件是：

def __iter__(self):
    current = self.head.next
    while current is not self.head:
        yield current.value
        current = current.next

另外，__len__ 不能靠遍历计数（O(n)），得维护一个 self._size 计数器，在每次 insert/remove 时增减——否则看似简洁的 len(mylist) 会变成隐式遍历。

真正难的不是写通，而是让所有操作在空链、单节点、多节点下行为一致，且不依赖外部判空逻辑。哨兵节点的自循环初始化和 size 计数器的原子更新，这两点漏掉一个，后续所有上层逻辑都会埋雷。

到这里，我们也就讲完了《Python高效双向循环链表实现方法》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！