单链表这个东西很多人第一次栽跟头不是因为概念难而是因为写完append之后print(head)屏幕上蹦出来一行__main__.Node object at 0x000001F...当场就懵了。我当年也这样甚至一度怀疑自己是不是没学会 Python 的对象模型。后来折腾久了才明白单链表真正的门槛不在怎么写而在想没想清楚节点之间靠什么串起来、头尾两端的边界怎么处理、删除时哪根线该先断。这篇就把我用 Python 手写单链表的完整过程摊开讲从一个能跑的最小版本开始一步步补上尾指针、长度、索引访问、删除、迭代器、反转和快慢指针中间夹着我踩过的坑和绕开的弯路。适合两类人看——正在学数据结构、需要一个能调试的参考实现的新手以及平时写业务代码、想搞清楚链表和 Python 的 list 到底差在哪的开发者。看完你应该能默写出一份带哨兵思维、尾指针维护正确、不踩NoneType报错的单链表并且知道它在什么场景下值得用、什么场景下纯属给自己找麻烦。1. 先把问题想清楚为什么还要手写单链表1.1 从一次真实需求说起为什么会需要分散存放的结构很多人学单链表的时候会有一个疑问Python 的list这么好用切片、append、pop、sort一应俱全为什么还要自己造一个链表这个问题如果不想明白后面写出来的代码就只是照着抄写完三天就忘。我最早遇到必须用链表的场景是做一个简单的日志缓冲区。需求很朴素数据源源不断进来我只要保留最近 N 条每来一条新记录就丢掉最老的一条同时还要支持从头到尾按顺序遍历输出。用list不是不行collections.deque也能干但当我想在中间插入一条优先级更高的记录、并且要求插入之后已有记录的位置关系不被整体搬家打乱时list的insert(0, x)每次都要把后面的元素统一往后挪一格数据量一上来就是白白的时间开销。单链表解决的正是这一类问题它把连续存放换成分散存放 指针串联。每个元素各自待在自己的一块内存里谁在谁后面靠每个元素身上带的一根线在 Python 里就是一个引用指过去。这样插入和删除只需要改动一两根线不需要让一大批元素集体搬家。代价也很明确——想找到第 100 个元素你没法像数组那样一步跳过去只能从头一个一个数过去。这就是单链表全部的设计哲学一句话概括用查找变慢换插入删除变快用内存分散换结构灵活。理解了这句话后面所有的细节选择——要不要尾指针、要不要哨兵节点、删除时先改哪根线——都能自己推导出来不需要死记。1.2 单链表与 Python list 的本质差异把两者的底层摆在一起看差别一目了然。对比维度Pythonlist手写单链表底层结构动态数组元素引用连续存放节点对象分散存放靠引用串联按下标访问O(1)直接算偏移O(n)必须从头走头部插入O(n)整体后移O(1)改两根引用尾部追加均摊 O(1)偶尔扩容复制O(1)需维护尾指针中间插入/删除O(n)搬移元素O(n) 找位置 O(1) 改链内存局部性好CPU 缓存命中率高差节点散落各处单元素额外开销一个指针槽位8 字节一个对象头 两个槽位迭代速度极快C 层实现慢纯 Python 循环这张表里最容易被忽略的是最后两行。单链表的每一个节点都是一个独立的 Python 对象一个最朴素的Node实例光对象头就要占几十字节加上__dict__如果没写__slots__开销更大而list里存的只是指向已有对象的指针连续排在一整块内存里遍历时 CPU 的预取机制能一路顺畅地读下去。所以同样是遍历十万个元素list往往比手写链表快一个数量级——这不是你代码写得不好是结构决定的。我特意把这点放在前面讲是想让你在动手之前就有一个正确预期手写单链表在 Python 里几乎永远不是为了性能而是为了理解结构、应对面试、或者实现某些链表独有的算法比如 O(1) 删除给定节点、原地反转、快慢指针找中点。如果你在业务代码里为了性能优化把list换成手写链表大概率是反向优化这一点后面第 4 节还会细说。1.3 设计阶段的三次取舍节点分离、尾指针、哨兵动手写之前有三个设计决定必须先定下来它们会直接影响后面代码的写法。第一个取舍节点和链表要不要分成两个类我的答案是必须分。节点只关心我存了什么值、我后面是谁链表只关心我从哪开始、我有多长、我尾巴在哪。分开之后节点的代码可以薄到只有几行链表负责所有操作逻辑职责清晰调试的时候p p.next这种走链动作也不会牵扯到链表自身的状态。第二个取舍要不要维护尾指针如果不维护每次append都要从头走一遍找到最后一个节点尾部追加退化成 O(n)这是很多人写完第一版之后发现怎么加一万条数据卡住了的根本原因。维护一个self._tail指向最后一个节点追加就变成 O(1)。代价是每次插入、删除、反转之后都要检查尾指针是否还指向正确的位置——这是最容易出错的地方也是我后面会反复强调的同步更新原则。第三个取舍要不要引入哨兵节点dummy head哨兵是一个不存业务数据的假节点永远挂在真正的第一个节点前面。它的价值是把在头部插入删除第一个节点这些特殊情况和普通情况统一起来代码里少一大堆if self._head is None的判断。经典的链表题解几乎都用哨兵因为它能显著降低边界错误的概率。不过对于初学者我建议第一版先不用哨兵因为不用哨兵的时候你会被NoneType报错反复捶打捶打的过程就是理解头指针可能为空这件事的过程。等你能不看文档写出正确的删除逻辑再引入哨兵做重构那才是真正的进步。本文的代码采用不用哨兵但维护尾指针的方案同时用注释标出哨兵方案的写法差异。2. 核心细节节点、引用与几个容易混淆的概念2.1 一个节点到底需要几样东西单链表的节点只需要两样东西值和指向下一个节点的引用。就这两样没有第三样。前驱指针不需要那是双向链表的事。索引不需要索引是逻辑位置靠走链数出来。在 Python 里写成这样class Node: 单链表节点只负责存值和指向下一个节点 __slots__ (value, next) def __init__(self, valueNone, nextNone): self.value value self.next next def __repr__(self): return fNode({self.value!r})这里的__slots__是一个小优化它告诉 Python 这个类的实例不需要__dict__属性固定就这两个。实测下来一个节点实例的内存占用能从那句对象头 dict 两个槽位的百来字节压到五十字节上下节点数量上万的时候差别是看得见的。__repr__则是为了调试——没有它你打印节点只会得到一串内存地址加了之后打印出来是Node(3)一眼就知道这个节点存了什么。还有一个细节值得说next这个属性名故意用了和内置函数next()同名的写法。它不会冲突因为在类里面self.next是属性访问跟内置函数next(iterator)是两回事但如果你在同一段代码里两个都用读起来会有点绕。我个人习惯就是沿用next因为链表讲下一个讲得太多用别的名字反而别扭。真要避开用nxt也完全可以命名一致性比名字本身更重要。2.2 Python 里的指针到底是个什么东西讲链表绕不开指针这个词但 Python 里没有 C 语言那种裸指针有的是引用。理解这一点能帮你避开一大半的概念混淆。具体说self.next other_node这行代码做的事情是让当前节点的next这个名字指向other_node那个对象。它不复制对象也不搬运内存只是让两个名字指向同一块地方。你后面如果通过other_node.value 100改了值从self.next.value看过去也是 100因为是同一个对象。这就引出一个初学者极容易踩的坑赋值不是复制。a Node(1) b a # b 和 a 指向同一个节点不是新的节点 b.value 99 print(a.value) # 99如果你想要一个独立的新节点必须显式Node(a.value)构造。在链表操作里凡是写p p.next的地方你只是把游标挪到了下一个节点没有产生任何新对象凡是写node Node(x)的地方才是真的造了一块新内存。搞清楚这两种语句的区别链表代码就不会写成一锅粥。还有一个常被问的问题比较节点该用还是is在链表里判断是不是同一个节点必须用is因为它比的是对象身份内存地址而默认也比身份但一旦你在Node里定义了__eq__按value比较的结果就不可靠了。我写删除逻辑的时候一律用is就是这个道理。2.3 头指针、首元节点、哨兵节点三者别混这三个词经常被混着用但它们说的是不同的东西。头指针self._head是一个变量它本身不是节点它只是指向第一个节点的一个名字。链表为空的时候头指针的值是None。首元节点是真正存第一个业务数据的那个节点。哨兵节点也叫哑节点、dummy head则是一个不存业务数据的假节点它的next才指向首元节点。为什么要把这三者分清因为几乎所有链表报错都来自头指针为None的时候还去访问.next。比如这段代码# 空链表时执行会直接崩 p self._head p p.next # AttributeError: NoneType object has no attribute next如果用了哨兵self._head永远不会是None哨兵本身是个实在的节点那么p.next就是合法的只是可能为None。这就是哨兵能消灭大量边界判断的原因。我的建议是写链表操作的时候在脑子里画三个格子——head 变量、第一个节点、第二个节点每次移动游标之前先问一句我确定当前这个格子不是空的吗很多 bug 就在这一问里被掐死了。2.4 长度和尾指针的维护约定self._size和self._tail这两个成员是缓存性质的东西它们的信息其实都能从头指针走出来但每次现算太浪费所以单独存一份。存一份就要承担一份责任每一个改变链表结构的操作都必须同步更新它们。我给自己定的规矩是四条写代码时逐条对照链表从空变成非空时_head和_tail都要指向那个唯一的节点。在尾部追加时只动_tail_head不变除非原来是空。删除最后一个节点后_tail必须回退到新的尾节点如果删完链表空了两个都置None。反转链表之后_head和_tail的身份会互换必须重新赋值。这四条听着简单但第 3 条和第 4 条我敢说九成的手写实现第一版都是错的。第 3 条错在删了尾节点忘了退尾指针导致后面append把新节点挂到一个已经不在链上的孤儿节点后面链表从此断头_size还在涨遍历出来的却少一个。第 4 条错在反转之后_tail还指着原来的尾现在变成头了接着append就出乱子。这两类 bug 都不报错只是结果不对排查起来非常费劲——所以一定要在方法末尾加断言或者写单元测试兜住。3. 动手写一份能真正用起来的单链表实现3.1 最小可运行骨架从空链表到能打印先给一份完整但精简的骨架包含初始化、长度、迭代和打印。这段代码不长但每一行都有讲究我逐段解释。class LinkedList: 单链表维护头指针、尾指针和长度三个状态 def __init__(self, iterableNone): self._head None self._tail None self._size 0 if iterable is not None: for item in iterable: self.append(item) def __len__(self): return self._size def __iter__(self): cur self._head while cur is not None: yield cur.value cur cur.next def __repr__(self): return LinkedList([ , .join(repr(v) for v in self) ])构造函数接受一个可迭代对象这是模仿内置容器的习惯LinkedList([1, 2, 3])就能直接建好。__len__返回缓存的_sizeO(1)。__iter__用生成器写注意循环条件是cur is not None而不是cur.next is not None——这两者的差别在于最后一个节点的值会不会被吐出来写成后者会漏掉尾巴这是遍历链表最经典的 off-by-one 错误。__repr__用join拼出LinkedList([1, 2, 3])这种形式调试时极其受用。要注意这里必须先list(...)或者直接迭代self而不要在repr里调用self.__str__否则容易递归。我一开始写成str(list(self))虽然能用但输出成[1, 2, 3]就看不出这是链表还是普通列表了加上类名外壳更清楚。还有一个小细节_head、_tail、_size都用了单下划线前缀意思是内部状态外部别直接改。Python 不会强制阻止你但这是一个约定团队协作时别人看到下划线就知道动它要小心。3.2 头部插入与尾部追加尾指针怎么同步追加是最常写的操作也是尾指针维护的主战场。def append(self, value): node Node(value) if self._head is None: # 空链表头和尾都指向它 self._head node self._tail node else: # 非空挂在尾巴后面尾指针前移 self._tail.next node self._tail node self._size 1 return self三个动作的顺序不能乱先让老尾巴的next指向新节点再把_tail挪到新节点上。如果反过来先挪尾指针老尾巴的next就没机会被设置链就断了。这个顺序问题在小数据量下不一定暴露但一旦出问题就是前面全对、后面全丢。头部插入更简单注意尾指针的处理def appendleft(self, value): node Node(value, nextself._head) self._head node if self._tail is None: # 原来是空链表尾也要指过来 self._tail node self._size 1 return self这里最容易漏的就是那个if self._tail is None。如果链表原来是空的你只更新了_head_tail还挂着None下一次append执行self._tail.next node直接AttributeError。我在第一版里漏过这个判断测试用例刚好是先追加一个、再头部插一个没触发线上跑到空链表先头部插入才炸。从那以后我养成了习惯任何修改_head的方法结尾都要检查_tail是否需要跟着变。两个方法都返回self是为了支持链式调用ll.append(1).append(2).appendleft(0)这样写起来顺手代价很小。3.3 按索引插入与访问把负数索引和越界处理干净链表按下标访问必须走链这是 O(n) 的活儿。但索引本身有一堆边界要处理负数、越界、等于长度追加。def _node_at(self, index): 返回第 index 个节点0 起越界抛 IndexError if index 0: index self._size if index 0 or index self._size: raise IndexError(linked list index out of range) cur self._head for _ in range(index): cur cur.next return cur def get(self, index): return self._node_at(index).value负数索引转正是照抄list的行为-1表示最后一个。_node_at单独抽出来是有意为之get、insert、__setitem__、pop都要走到第 i 个节点抽出来之后只有一份走链逻辑改起来只改一处。插入的时候索引可以等于_size表示追加到末尾这个边界要单独放行def insert(self, index, value): if index 0: index self._size if index 0: index 0 # 太负就插到最前面 if index 0: return self.appendleft(value) if index self._size: return self.append(value) prev self._node_at(index - 1) # 找到前驱 prev.next Node(value, nextprev.next) self._size 1 return self注意prev.next Node(value, nextprev.next)这一行的求值顺序右边先算prev.next拿到的是原来的后继然后构造新节点指向它最后才把prev.next改成新节点。顺序天然正确因为 Python 先算右边。如果你写成两行prev.next Node(value) prev.next.next old_next # 这时 prev.next 已经是新节点了就必须先存old_next prev.next否则就丢了后半条链。这类断链错误是链表 bug 的头号来源我后面第 5 节会专门列一份排查表。用生活化的比喻插入就像在两个人中间塞一个人你必须先让新人拉住后一个人的手再让前面那个人松开旧手改拉新人。先松手再拉中间就掉下去了。3.4 删除节点先断链还是先改引用删除的逻辑看起来简单实际要处理三种情况删头、删尾、删中间而且尾指针必须跟着动。def remove(self, value): 删除第一个值等于 value 的节点返回是否删除成功 prev, cur None, self._head while cur is not None: if cur.value value: if prev is None: # 删的是首元节点 self._head cur.next else: prev.next cur.next if cur is self._tail: # 删的是尾节点 self._tail prev cur.next None # 帮 GC 一把断开引用 self._size - 1 return True prev, cur cur, cur.next return False这里几个点值得掰开说。双指针prev和cur同步往前走是链表删除的标准姿势。因为删除需要知道目标的前一个是谁单链表只有单向的路你没法从当前节点回退所以必须提前留一手。删尾节点时self._tail prev这一句如果没有链表状态就坏了。而且如果删完之后_size变成 0prev恰好是None_tail None也自动正确不需要额外特判这是这个写法优雅的地方。cur.next None这一行是锦上添花不是必须的。Python 有引用计数加循环垃圾回收你不主动断那个被删掉的节点只要外部没人引用也会被回收。但如果你的业务代码里别处还留着对这个节点的引用比如调试变量断开next能保证它不会拖着后半条链一起活着——在长链表里手动删节点这个习惯能省内存。我把它当规范写不省这一步。按位置删除的pop类似只是用_node_at定位def pop(self, index-1): if self._size 0: raise IndexError(pop from empty linked list) if index 0: index self._size target self._node_at(index) value target.value # 复用 remove 会有重复值问题这里直接按节点删 if index 0: self._head target.next if self._tail is target: self._tail None else: prev self._node_at(index - 1) prev.next target.next if self._tail is target: self._tail prev target.next None self._size - 1 return value注意这里不能图省事去调remove(value)因为链表里可能有重复值remove删的是第一个值相等的而pop(index)要删的是位置正好是 index 的那个语义不同。这个坑我踩过当时图省事复用了remove测试用例里正好有[1, 2, 2, 3]去pop(2)结果删掉了第一个 2断言直接红。3.5 遍历、反转与快慢指针三个必须自己写一遍的算法遍历已经在__iter__里写了这里不重复。真正值得单独练的是原地反转和快慢指针它们是链表思维的代表作。原地反转的核心是三指针滚动prev记住前一个cur是当前nxt临时存下一个。每一轮把cur.next掉头指向prev然后三个指针整体往后挪一格。def reverse(self): prev None cur self._head while cur is not None: nxt cur.next # 先存后路否则断链 cur.next prev # 掉头 prev cur # prev 前移 cur nxt # cur 前移 self._head, self._tail prev, self._head return self循环结束时prev指向原来的尾节点也就是新链表的头原来的_head现在是新链表的尾。所以最后那行同时更新两个指针。这里如果只写self._head prev而忘了_tail后续append就会出问题——这是第 2.4 节第 4 条规矩的实际应用。nxt cur.next这一句必须在改cur.next之前否则你改完之后就找不到原来的后继了循环走不下去或者走到一半成为孤环。这个顺序是反转算法的命门没有别的技巧就是记住。快慢指针解决的是找中点和判断有没有环def find_middle(self): 返回中间节点偶数个节点时返回靠后的那个 slow fast self._head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next return slow def has_cycle(self): slow fast self._head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow is fast: return True return Falsefind_middle的逻辑是快指针一次走两步慢指针一次走一步快指针走到头的时候慢指针正好在中间。循环条件里的fast.next is not None不能少否则fast.next.next在快指针到最后一个节点时会崩。has_cycle是同一套骨架加一个相遇判断。为什么一定能相遇因为如果有环快指针进环之后每轮比慢指针多走一步环长度有限迟早追上。这个证明不复杂但面试里能讲清楚的人不多值得自己推一遍。顺带提醒一句判断链表有没有环、找入口节点这类题除了快慢指针另一种思路是边遍历边把节点 id 塞进集合写起来更直白。但那个方案要额外 O(n) 空间在面试里通常会被追问能不能 O(1) 空间所以快慢指针还是得会。3.6 三个实操心得写代码前先记住写到这里代码基本成型了。补三条纯经验性的东西都是我在反复重写中攒下来的。第一_head每一次被赋值都要在下一行想一想_tail和_size。这个动作我练成了条件反射。链表的所有状态错误几乎都来自三个状态没同步而它们之间没有自动关联全靠你手动维护。第二写完任何一个方法用一个空链表、一个单节点链表、一个双节点链表各跑一遍。这三个用例能覆盖绝大部分边界空链表测的是你会不会访问None.next单节点测的是删完之后头尾是不是都成了None双节点测的是删头删尾的指针转移对不对。我后来把这三种情况写成了自动化测试每次改完立即跑比手动 print 靠谱得多。第三调试时永远先打印结构再看值。用__repr__输出整条链比逐个 printnode.value有效得多。更狠一点可以写一个专门的调试函数把链上的id(node)也打出来用来确认我以为的两个节点到底是不是同一个对象。这个技巧帮我定位过好几次莫名少了一个节点的诡异问题。4. 复杂度和真实性能什么时候它值得用4.1 各操作时间复杂度对照把上面实现的所有操作摊在表里方便你写代码时心里有数。操作时间复杂度说明append尾部追加O(1)依赖尾指针维护正确appendleft头部插入O(1)改两根引用get(index)O(n)必须从头走insert(index, v)O(n)找前驱是瓶颈改链本身 O(1)remove(value)O(n)找目标 找前驱pop(0)O(1)只改头指针pop(-1)O(n)需要找尾的前驱reverseO(n)一趟扫描原地完成find_middleO(n)快慢指针lenO(1)缓存_size有两行值得特别注意。pop(0)是 O(1)这正好是Python list的短板list.pop(0)需要整体前移O(n)这也是链表的经典优势场景。反过来pop(-1)在链表里是 O(n)而在list里是 O(1)正好反过来。所以选结构的时候要问自己的是我的热点操作到底在头还是在尾答案不同结论完全相反。如果你既需要两端都 O(1)那就不该用单链表该用双向链表加头尾指针或者直接用collections.deque——它就是双向队列的 C 实现两端操作都是 O(1)性能远好于手写结构。4.2 实测感受为什么 Python 里链表总是慢一截我在本地做过一次简单对比同一条 10 万条整数数据用list求和遍历和用手写链表sum(ll)链表这边慢了一倍以上。原因不神秘主要是三条。第一是内存局部性。Python 的list底层是一块连续的指针数组遍历时 CPU 一次读进来一串地址后面的几个很可能已经在缓存里了。链表的节点是散落的每个节点都可能触发一次缓存未命中走一步等一次内存累积起来非常可观。第二是对象开销。每个Node是一个完整对象哪怕加了__slots__也有引用计数、类型指针这些固定成本。10 万个节点的内存占用通常是同等list的几倍。第三是纯 Python 解释开销。for v in list的迭代在 C 层完成而手写链表的while cur is not None: cur cur.next每一步都走一遍字节码。这个差距在 Python 这种解释型语言里尤其明显。所以我的结论很明确在 Python 里手写单链表的价值在于学会它和应对特定算法题而不是用它替换 list 提速。如果你需要频繁在两端增删用deque如果需要随机访问用list如果只是练习数据结构那就老老实实手写链表但要清楚它的性能边界在哪。4.3 什么场景适合什么场景别碰适合的几个场景我按可信度排一下序教学与面试准备链表题是数据结构的基本盘反转、找中点、判环、合并有序链表这套题背后考的是指针操作和边界处理能力值得认真练。实现更复杂结构的零件哈希表的拉链法、LRU 缓存的节点链、图的邻接表底层都是节点 引用的变体。频繁头部插入、极少随机访问比如维护一个任务栈、逆序收集结果头插 O(1) 确实比list.insert(0, x)划算。不适合的场景同样明确数据量大且需要遍历十万级以上链表遍历的劣势会被放大。需要频繁按下标访问这是链表最不擅长的。业务代码里的普通容器需求list、deque、dict覆盖了绝大多数场景手写结构只会增加维护成本。多线程环境下的共享链表Python 里链表操作不是原子性的节点之间的引用关系也可能处于中间状态需要自己在外部加锁这一点后面第 5 节会提。5. 常见问题与排查实录5.1 报错与现象速查表这份表是我从自己的调试记录里整理的按出现频率从高到低排列。现象/报错大概率原因处理办法AttributeError: NoneType object has no attribute next在None上调用了.next通常是空链表或走到尾之后没停在循环和赋值前加if cur is not None判断打印出来是Node object at 0x...没写__repr__给Node和LinkedList都加__repr__遍历结果每次一样、无限循环循环里忘了推进游标cur cur.next检查循环体末尾是否有推进语句遍历少一个元素循环写成while cur.next is not None改成while cur is not Noneappend之后链表断头只剩一个节点尾指针没维护新节点挂在孤儿节点后检查空链表分支是否同时设了_head与_tail删除后_size不对某个分支忘了self._size - 1所有改动结构的路径结束前统一加减反转后append出错_tail没跟着反转反转结束同时更新_head和_tailpop删错元素复用了remove(value)导致按值而非按位置删按位置删除时单独走_node_at定位insert之后链断了一半先改了prev.next再去找原后继先存old_next或写成一行嵌套构造内存持续增长删掉的节点仍被外部或自身引用删除时把node.next置None表里前四条是新手期最常见的后面几条是写多了才会遇到的隐性状态错误。区分方法很简单报错的属于第一类不报错但结果不对的属于第二类。第二类只有靠断言和测试兜住。5.2 几条没人告诉你的避坑经验别用递归遍历长链表。Python 默认递归深度只有一千层左右链表超过这个长度直接RecursionError。我见过有人用递归写reverse本地测试五个节点很完美跑真实数据时直接崩。链表的遍历和反转请一律用迭代。删除时判断是不是尾节点要用is不要用。cur is self._tail判断的是同一个对象cur self._tail在节点有相同value时会误判成同一个节点。这个 bug 极其隐蔽因为它在没有重复值时表现完全正常。注意别在迭代过程中修改链表。for v in ll: ll.append(1)这种写法会出问题__iter__是生成器它在遍历期间如果链表被改行为可能出乎意料甚至死循环。要么先取快照list(ll)再改要么显式禁用这种操作。我在自己的实现里干脆在文档字符串里写明迭代期间不要修改结构。__slots__和继承要小心。加了__slots__之后这个类就没法动态加属性了如果你打算继承Node加点调试字段记得子类也要声明__slots__否则子类实例会自动获得__dict__优化效果就没了。多线程下别共享链表。Python 的引用赋值虽然是单一字节码操作但链表的一次插入涉及好几步赋值中间状态被别的线程看到就会读到不完整结构。要么外部加锁要么每个线程各用各的链表。这一点在处理并发任务队列时尤其要注意。调试时打印id。当你怀疑两个节点是不是同一个的时候id(node)是最快的验证手段。我在排查一次删除后链表长度对但内容错的问题时就是靠对比id发现目标节点和_tail其实是两个不同的对象。5.3 用测试把边界固定下来最后分享一下我怎么给这份实现配测试。不是追求覆盖率而是专门盯着边界打。import unittest class TestLinkedList(unittest.TestCase): def setUp(self): self.ll LinkedList([1, 2, 3]) def test_empty_append(self): ll LinkedList() ll.append(1) self.assertEqual(list(ll), [1]) self.assertEqual(len(ll), 1) def test_appendleft_into_empty(self): ll LinkedList() ll.appendleft(1) ll.append(2) # 关键验证 _tail 没坏 self.assertEqual(list(ll), [1, 2]) def test_pop_last_resets_tail(self): ll LinkedList([1, 2]) self.assertEqual(ll.pop(), 2) ll.append(9) # 关键验证尾指针回退正确 self.assertEqual(list(ll), [1, 9]) def test_reverse_keeps_tail(self): ll LinkedList([1, 2, 3]) ll.reverse() self.assertEqual(list(ll), [3, 2, 1]) ll.append(0) # 关键验证反转后尾指针可用 self.assertEqual(list(ll), [3, 2, 1, 0]) def test_remove_head_and_tail(self): ll LinkedList([1, 2]) self.assertTrue(ll.remove(1)) self.assertTrue(ll.remove(2)) self.assertEqual(len(ll), 0) self.assertIsNone(ll._head) self.assertIsNone(ll._tail) if __name__ __main__: unittest.main()这套用例的设计思路值得说一下。每个测试里我都在操作之后追加一个看似无关的动作比如删完尾节点再append、反转后再append。这些动作用来验证内部状态指针有没有被带坏——因为单纯比较列表内容很多状态错误是看不出来的只有后续操作才会暴露。这也是我前面反复说尾指针必须同步的落地检查方式。如果你想让实现更完整还可以继续加两个方法一个__getitem__支持ll[2]下标语法一个to_list()直接导出成 Python 列表方便和其他代码对接。前者调用_node_at即可后者一行return list(self)。这两个是纯便利性方法加上之后这份链表在日常调试和刷题里就基本够用了。后续想继续深挖的话我建议按这个顺序走先补双向链表体会用空间换回退能力再写一个带索引跳转的跳表雏形最后把链表用到 LRU 缓存的实现里去。每一步都能让你对引用关系怎么组织多一层体感这比刷十道同类题管用。