不该从零手写链表，因Python list是动态数组，随机访问O(1)、尾部操作近O(1)，而手写链表受对象开销、指针跳转和缓存不友好拖累，性能通常更差。
为什么不该从零手写链表？
Python 的 list 底层是动态数组，随机访问 O(1)，插入删除尾部接近 O(1)；而手写链表在 CPython 中反而因对象开销、指针跳转、缓存不友好，实际性能通常更差。除非你明确需要：
- 在特定位置（非尾部）高频
insert/pop且数据量极大（万级+） - 教学理解指针逻辑或对接 C 扩展
- 实现定制行为（如带锁的线程安全节点、内存池复用）
否则直接用 collections.deque —— 它是双向链表实现，O(1) 头尾操作，C 语言加速，已足够“高性能”。
单向链表的最小可行实现要点
核心是避免 Python 对象的隐式引用循环和过度封装。常见错误是给每个节点加太多方法，导致调用栈深、属性查找慢。
- 节点类只保留
val和next两个实例变量，不用@property包装 - 链表类不实现
<strong>iter</strong>（用显式 while 循环更快），只提供append、find、remove等必要方法 - 插入/删除时务必检查
head是否为None，否则触发AttributeError: 'NoneType' object has no attribute 'next' - 不要试图支持负索引或切片——这会迫使你先遍历计数，完全丧失链表优势
class ListNode:
__slots__ = ('val', 'next') # 减少内存占用
def __init__(self, val):
self.val = val
self.next = None
<p>class SinglyLinkedList:
def <strong>init</strong>(self):
self.head = None</p><pre class='brush:python;toolbar:false;'>def append(self, val):
new = ListNode(val)
if not self.head:
self.head = new
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = new双向链表必须处理的三个边界场景
collections.deque 可以直接用，但若真需自定义，prev 指针的维护比 next 更易出错。重点防以下三种漏判：
立即学习“Python免费学习笔记（深入）”；
- 头节点删除时，忘记更新
new_head.prev = None，导致残留引用、GC 延迟 - 尾节点插入时，没把原
tail.next指向新节点，或新节点prev没指向原 tail - 单节点链表执行
remove后，未将self.head和self.tail同时置为None，后续操作崩溃
另外，双向链表的内存占用约是单向的 1.8 倍（多一个指针 + Python 对象头开销），小数据量下毫无意义。
性能对比中容易被忽略的陷阱
用 timeit 测链表操作时，常犯的错是：
- 在测试循环内反复创建新链表，结果测的是构造耗时而非操作耗时
- 用
range(1000)测插入，但 Pythonrange是惰性对象，真实数据应提前转成list或用random.randint生成 - 忽略 GC 干扰：加
gc.disable()再测，否则频繁创建节点会触发垃圾回收抖动 - 比较
deque.appendleft()和手写链表头插时，没关掉 deque 的块分配优化（它实际按 64 元素分块），导致看似“链表更快”——其实是缓存局部性碾压
真正值得手写的时刻，往往不是“我要个链表”，而是“我需要一个能快速 splice 的结构”或“我要在节点上挂载元数据并批量迭代”。这时候，再考虑裸指针 + <strong>slots</strong> + 手动内存管理。
