Python链表实现：单双链表详解

本文深入剖析了Python中单向与双向链表的手动实现要点，从Node和LinkedList类的基本设计、空链表边界处理、prev/next指针同步更新的常见陷阱，到__iter__和__len__的高效实现策略，既揭示了教学场景下理解指针逻辑的核心价值，也直言不讳地指出：在真实项目中，list和deque才是更安全、高效、内存友好的首选——手写链表仅适用于特定学习目的或极少数需原地节点操作的特殊场景，盲目自造反而易陷性能与维护泥潭。

Python里写单向链表，Node和LinkedList两个类就够了

单向链表的核心是每个节点只存一个指向后继的引用，不需要考虑回溯。实际写的时候，Node类只管数据和next指针，LinkedList类封装增删查逻辑——别把所有功能塞进一个类里，否则插入头尾、遍历、删除时容易混淆边界。

常见错误是初始化head为None后，在append()或insert()里忘记判空，直接调head.next导致AttributeError: 'NoneType' object has no attribute 'next'。

实操建议：

• Node类的__init__只接收data，next默认设为None
• LinkedList的head始终是Node或None，不存“虚拟头节点”（除非你明确需要简化边界处理）
• 插入到头部用new_node.next = self.head; self.head = new_node，比遍历到尾再插快得多
• 遍历时用current = self.head然后while current:，别写while current.next:，否则漏掉最后一个节点

双向链表必须多管一个prev，但remove()和insert_before()才真正值回票价

双向链表的Node要多一个prev属性，LinkedList操作时前后指针必须同步更新。这不是为了炫技，而是让某些操作从 O(n) 降到 O(1)：比如已知某节点引用时删除它，或者在它前面插入新节点。

最容易踩的坑是更新prev和next顺序错乱。例如删除中间节点target时，如果先执行target.prev.next = target.next，再执行target.next.prev = target.prev，看起来没问题；但如果target是尾节点，target.next是None，就会报AttributeError: 'NoneType' object has no attribute 'prev'。

实操建议：

• 所有涉及prev和next的赋值，先检查相邻节点是否为None，尤其处理头/尾时
• 写remove(node)前，先确保node确实在链表中（可加if node not in self，但更高效的是维护_size或用身份比较）
• insert_before(existing_node, new_node)比insert_at_index()更符合双向链表的设计本意——它不依赖索引遍历
• 不要为了省两行代码，在Node.__init__里把prev和next都默认设为self（即自环），这会让后续逻辑彻底混乱

__iter__和__len__要不要实现？看你怎么用

不实现__iter__，你就得手动写current = ll.head; while current: ...；实现了，就能直接for node in my_list:。同理，__len__返回缓存的_size还是每次遍历统计，直接影响性能。

问题在于：很多人实现__len__时每次遍历计数，结果在循环里反复调用len(my_list)，把 O(1) 操作拖成 O(n²)。而如果维护_size，就得在每个修改结构的方法（append、remove、pop）里同步更新——漏一次，len()就永远不准了。

实操建议：

• 只要链表会被多次迭代，就实现__iter__，返回生成器（yield current.data）比构建列表更省内存
• 如果链表长度常被查询（比如做条件判断if len(ll) > 10:），务必维护self._size并在所有变更方法中增减它
• 不要在__iter__里返回self本身（即不实现__next__），否则多次迭代会相互干扰
• __repr__可以返回f"LinkedList({list(self)})"，方便调试，但注意大链表会卡住

真实项目里，99%的情况该用list或collections.deque，不是自己写链表

Python 的 list 是动态数组，按索引访问 O(1)，尾部增删接近 O(1)；collections.deque 是双向队列，头尾增删都是 O(1)，内部用双向链表+块内存实现，但对外不暴露节点指针。

自己写链表的唯一合理场景，是教学理解指针逻辑、或极特殊需求（比如需要在任意节点原地拆分/拼接，且不能拷贝数据）。一旦涉及序列化、线程安全、内存视图、或与 NumPy/Pandas 交互，手写链表立刻变成维护黑洞。

容易被忽略的一点：Node实例本身有较大内存开销（每个对象带__dict__和引用计数），10 万个节点比等长list多占 2–3 倍内存。真要高性能，连__slots__都得加上，但那就离“教学清晰”越来越远了。

理论要掌握，实操不能落！以上关于《Python链表实现：单双链表详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！