Python单链表实现：引用思维、边界条件与增删查改

上个月帮一个朋友看代码他甩过来一句“Python 自带 list 什么都能干为什么还要手写单链表”我没直接回答而是让他把 list 从中间插一万个元素的耗时打出来再跟我手写的单链表头插一万个元素比一比。结果出来后他自己就明白了单链表真正的价值不在于“能不能存数据”而在于它把“指针操作”这件事暴露在你面前让你不得不去想每一个 next 到底指向谁。用Python创建一个单链表表面看是练数据结构实质上练的是引用思维和边界条件思维——这两样东西后面写树、写图、写任何链式结构都绕不开。这篇内容面向三类人刚学完 Python 语法、想拿链表练手的入门者准备面试、需要把增删查改一次性写对的同学以及写过链表但总是栽在“删除头节点”和“遍历到底”上的朋友。我会从内存模型讲到完整可运行代码再把几个我亲自踩过的坑摊开讲清楚。代码全部可以直接复制到文件里跑不依赖任何第三方库。1. 先把“指针”翻译成 Python 的“引用”1.1 单链表在内存里到底长什么样很多人一上来就抄代码结果第二步就懵了。我建议第一步先在纸上画图。一个单链表由若干个节点串起来每个节点只负责两件事存一份数据记住“下一个节点在哪”。最后一个节点的“下一个”是空表示到头了。关键点在于这些节点在内存里并不挨着。你在纸上画的是一条连续的线实际内存里它们是散落的彼此之间靠“地址”连起来。这跟 Python 的 list 完全不同——list 底层是一块连续的数组元素挨着元素所以按下标访问是瞬时的而单链表想找第 5 个元素必须从第 1 个开始一个一个“跳”过去。我用一个生活类比list 像一排连号的储物柜你知道 5 号柜在哪直接走过去开单链表像一张寻宝纸条上面写着“下一个线索在图书馆三楼某本书里”你必须按顺序解完前面的线索才能拿到最后那个。这个差别决定了后面所有的时间复杂度结论不是背下来的是推出来的。1.2 Python 里 next 存的既不是值也不是下标这是新手最容易糊掉的地方。在 C 里next 存的是一个内存地址你可以打印出来看可以做指针运算。Python 没有这套东西Python 的变量本质上是对象的引用——变量名贴在对象上赋值就是把标签贴到另一个对象上。所以当你在 Python 里写node.next other_node发生的是node这个对象的next属性指向了other_node所代表的那个对象。它同样能实现“A 找到 B”的效果但它不能做地址加减也不能手动释放。这带来两个直接后果第一你不需要考虑内存分配和释放对象没人引用时自动回收代码量大幅减少这是好事。第二你失去了“地址”这个抓手调试时不能打印指针看连接关系只能靠你自己在脑子里或者纸上维护一张图。很多人写链表写崩本质是脑子里的图跟代码里的图对不上了。提示调链表代码时养成在纸上画三个方框、用箭头连起来的习惯比盯着屏幕看十遍有用。尤其是删除和反转图上画一遍代码基本不会错。1.3 新手第一版代码最常错的三个地方我把这些年看别人包括早期的自己写的单链表代码归了归类错误高度集中在这三处。第一处把node node.next写成node.next node。前者是“我走到下一个节点”后者是“我让下一个指向我自己”后者会直接把链剪断还可能造出一个自环遍历时永远出不来。第二处删除节点时只改前驱忘了处理被删节点自己的 next。在 Python 里对象会被自动回收所以不断开通常不会“内存泄漏”但如果这个被删节点被你另外的变量引用着比如返回值、日志、缓存它依然指向原来的后继你的链表就悄悄多出一条“影子链”后面排查起来极其痛苦。所以我的习惯是删除时一律补一句node.next None成本几乎为零。第三处空链表和单节点链表没有单独处理。头插的时候没考虑 head 是 None删除的时候没考虑删的正好是头遍历的时候没考虑一开始就空。这三个特殊路径占了链表 bug 的一大半后面我会专门开一节讲。2. 节点类与链表骨架先把地基打正2.1 Node 为什么只留两个字段节点类的设计有一个很实用的原则能少一个字段就少一个字段。你常见的教材写法是self.data和self.next足够了。有些教程会加self.prev那是双向链表本篇不讲有些会加self.index那是给节点编号属于典型的过度设计——节点一旦插入删除编号就全乱了维护成本远大于收益。我习惯用__slots__理由很实在class Node: __slots__ (data, next) def __init__(self, dataNone, next_nodeNone): self.data data self.next next_node__slots__的作用是告诉 Python“这个类的实例只会用到这两个属性不要给我准备那个默认的__dict__”。省内存是次要的更重要的好处是防拼写错误如果你不小心写了node.nxt x用普通类会静默创建一个新属性程序不报错但逻辑全错用了__slots__立刻抛 AttributeError问题在一秒内暴露。参数名我用next_node而不是next因为next是 Python 内置函数名虽然在__init__的参数位置写next也能跑但会遮蔽内置函数属于给自己埋雷。属性名保留self.next是可以的因为它是挂在实例上的不会影响全局的next()。2.2 链表类该维护哪些状态链表的全部状态其实只有一个头节点在哪。你可能会问长度要不要存我的答案是存但要清楚这是用空间换时间。class LinkedList: def __init__(self): self.head None self._size 0只维护 head每次取长度就要遍历一遍是 O(n)维护_size长度是 O(1)代价是每个增删操作都要记得同步更新它——忘更新就是 bug。这是个典型的工程折中我倾向于维护因为实际使用里“问长度”的频率远高于“省一个整数”。但写的时候必须守纪律任何改动节点数量的地方_size必须同步加减一处都不能漏。我用下划线开头命名_size是给使用者一个信号这是内部状态别直接改请通过方法操作。Python 不做强制访问控制但命名约定在这个行业里是被认真对待的。2.3 三个“白送”的魔术方法能让调试轻松一半写完核心逻辑后强烈建议补上这三个方法它们不影响功能但极大影响你排查问题的效率。第一个是__len__让len(ll)直接可用。第二个是__iter__让链表能用 for 循环遍历这是 Python 里最自然的姿势。第三个是__repr__让你print(ll)时看到[1 - 2 - 3]而不是一串内存地址。__repr__的写法要小心不要在遍历里调用可能修改结构的方法也不要处理环——万一你链出环了__repr__会直接死循环连调试信息都打不出来。我的做法是加一个计数上限def __repr__(self): parts [] cur self.head guard 0 while cur is not None and guard 1000: parts.append(repr(cur.data)) cur cur.next guard 1 suffix - … if cur is not None else return - .join(parts) suffix if parts else 空链表这个 guard 是我吃了亏才加的。有一次调试一个环加 print 之后程序直接卡死等了半分钟才反应过来是打印自己在死循环。2.4 第一版可运行骨架把上面拼起来先跑通一个最小版本确认思路没错再往里填方法。这一步别贪快骨架对了后面就是填空。class Node: __slots__ (data, next) def __init__(self, dataNone, next_nodeNone): self.data data self.next next_node class LinkedList: def __init__(self): self.head None self._size 0 def __len__(self): return self._size def __iter__(self): cur self.head while cur is not None: yield cur.data cur cur.next def __repr__(self): return - .join(repr(x) for x in self) if self.head else 空链表 ll LinkedList() print(ll, len(ll)) # 空链表 0跑通这十几行你就已经拥有一个可以遍历、可以打印、可以问长度的空壳了。接下来往里加东西每一步都可以立刻验证。3. 增删查改每一处边界都值得单独讲3.1 头插和尾插指针的赋值顺序不一样头插是最简单的操作也是理解“引用搬移”的最佳入口def prepend(self, data): node Node(data) node.next self.head self.head node self._size 1顺序不能反。如果你先写self.head node再写node.next self.head那 node 的下一个就指向了自己直接造环。规则是先让新节点接上旧链条再让入口指向新节点。这个顺序在所有链式结构里通用树、图都一样。尾插稍微麻烦因为单链表没有“尾指针”必须从头走到尾def append(self, data): node Node(data) if self.head is None: self.head node self._size 1 return cur self.head while cur.next is not None: cur cur.next cur.next node self._size 1注意while cur.next is not None而不是while cur is not None。前者停下来时 cur 正好是最后一个节点可以直接挂后者停下来时 cur 已经是 None你没法挂任何东西。这个“看 next 还是看自己”的区别是链表遍历里最容易搞混的一点我把它记成一句话要改前驱就停下在最后一个节点要读数据就停在 None。顺带说一句如果尾插用得非常多可以额外维护一个self.tail把尾插降到 O(1)。但删尾会变麻烦还是要从头找前驱所以维护 tail 的收益要看你实际用法别一上来就上。3.2 按下标插入prev 指针一个都不能少按下标插入的本质是找到目标位置的前一个节点然后做两次赋值。顺序依然关键def _node_at(self, index): cur self.head for _ in range(index): cur cur.next return cur def insert(self, index, data): if index 0 or index self._size: raise IndexError(f插入位置越界: {index}) if index 0: self.prepend(data) return prev self._node_at(index - 1) node Node(data, prev.next) prev.next node self._size 1Node(data, prev.next)这一行把“新节点的下一个”直接指定为原来的后继然后才让prev.next指向新节点。先接后断这四个字是链式插入的通用口诀。如果你先写prev.next node那么原来的后继就丢了因为唯一指向它的引用被你覆盖了那一整段链在 Python 里会因为没有引用而被回收——你甚至不会收到任何报错只是数据凭空消失。这就是我常说的单链表最可怕的地方不是报错而是不报错。list 越界会给你 IndexError链表写错了它一声不吭只在你后面取数的时候发现少了东西。3.3 删除的三种情形和被删节点自己的 next删除是链表里唯一需要同时处理“前驱”和“自身”的操作。分三种情况def remove_at(self, index): if index 0 or index self._size: raise IndexError(f删除位置越界: {index}) if index 0: node self.head self.head node.next node.next None self._size - 1 return node.data prev self._node_at(index - 1) node prev.next prev.next node.next node.next None self._size - 1 return node.data情况一删头。只需要移动 head没有前驱需要处理。这是最容易漏的分支因为很多人写完prev.next prev.next.next就以为完事了结果删头的时候_node_at(-1)直接崩掉或者绕死。情况二删中间或尾。找到前驱跳过目标。删尾的时候node.next是 None所以prev.next None正好把尾巴收掉不需要特判——但如果你的代码里写的是prev.next node.next.next删尾就会 AttributeError。用prev.next node.next永远安全这个写法值得养成肌肉记忆。情况三空链表删任何东西。上面第一行判断就挡住了。最后那句node.next None就是我前面强调的“断开”。它让被返回的节点彻底脱离链表如果你把这个返回的节点交给调用方调用方拿到的就是一个干净的单点而不是带着半条链的怪物。我见过真实案例有人把删除的节点放进一个列表做审计结果每个被删节点都还牵着后续节点整个列表实际上把全量数据又存了一遍内存翻倍。3.4 查找与修改遍历终止条件的写法差异查找分两种按值找位置、按下标取值。def get(self, index): if index 0 or index self._size: raise IndexError(f下标越界: {index}) return self._node_at(index).data def set(self, index, data): if index 0 or index self._size: raise IndexError(f下标越界: {index}) self._node_at(index).data data def index_of(self, data): cur self.head i 0 while cur is not None: if cur.data data: return i cur cur.next i 1 return -1index_of里用的是while cur is not None因为我们只读不改可以放心走到末尾然后返回 -1。这跟前面尾插的写法形成了对照你可以再回头看 3.1 那句口诀两个条件就是这么分出来的。还有一个细节值得说index_of里我用比较意味着如果 data 是自定义对象你得保证这个对象实现了__eq__。如果链表里存的是可变对象改完之后index_of可能就找不到了这不是链表的锅是你把对象当键用了。我一般建议链表里存不可变数据数字、字符串、元组或者至少保证你清楚比较语义。3.5 完整代码与一组自测把上面所有片段拼成一个文件跑下面这组自测全过就说明基本功能没问题if __name__ __main__: ll LinkedList() for x in [1, 2, 3]: ll.append(x) ll.prepend(0) ll.insert(2, 99) print(ll) # 0 - 1 - 99 - 2 - 3 print(len(ll)) # 5 print(ll.index_of(99)) # 2 print(ll.remove_at(0)) # 0 print(ll.remove_at(len(ll) - 1)) # 3删尾 print(ll) # 1 - 99 - 2 ll.set(1, 100) print(list(ll)) # [1, 100, 2] print(ll.get(2)) # 2自测用例的设计比代码本身更能体现水平。我覆盖了空链表加元素、头插、中间插入、头删、尾删、按值查找、按下标改、转 list。头删和尾删必须各测一次因为它们是分支最容易错的两端。中间插入也必须测因为它同时考验_node_at和赋值顺序。4. 调试现场我实际栽过的四个坑4.1 用复制链表结果两条链表会互相影响这是最经典的一个。有人想“备份一下当前链表”写了backup ll # 错这根本不是复制只是给同一个对象多贴了一个标签。之后你对ll做任何增删backup也跟着变。链表这种带引用结构的对象浅拷贝同样不靠谱copy.copy会复制链表对象本身但 head 还是指向同一批节点你在一条链上改node.data另一条也会变。正确做法是深拷贝或者更简单——重建def clone(self): new_ll LinkedList() cur self.head while cur is not None: new_ll.append(cur.data) cur cur.next return new_ll注意这里append每次创建新 Node所以两条链完全不共享节点。如果数据元素本身是可变对象还得对 data 再做一次深拷贝那就用copy.deepcopy(cur.data)。我一般在实际项目里尽量让链表只存不可变数据从源头上避开这个坑。4.2 遍历时改结构循环跑不完场景很常见你遍历链表发现某个值要删掉顺手就在循环里删了。cur ll.head while cur is not None: if cur.data % 2 0: ll.remove_at(...) # 危险 cur cur.next问题在于remove_at内部改了指针关系而你手里的cur可能已经不在链上了更糟的是如果删的是当前节点cur.next可能还指向原后继看起来“没事”但_size已经乱了再删就删错位置。正确的姿势只有两种先收集、后删除或者用前驱指针手动走。# 姿势一先收集再删 to_remove [i for i, v in enumerate(ll) if v % 2 0] for i in reversed(to_remove): ll.remove_at(i) # 从后往前删下标才不会错位这里reversed是关键。如果你从前向后删删掉第 0 个之后原来的第 1 个变成第 0 个你的下标就全错位了。这个小细节我在代码评审里见过太多次。4.3 空链表和单节点链表是最容易漏的两条路径我的习惯是每写完一个方法先问自己两个问题——head 是 None 时会怎样只有一个节点时会怎样拿reverse反转来说如果写成这种形式def reverse_buggy(self): prev None cur self.head while cur.next is not None: # 空链表直接崩 nxt cur.next cur.next prev prev cur cur nxt self.head cur空链表时cur是 Nonecur.next立刻 AttributeError。正确写法是while cur is not None循环条件本身就把空链表挡在外面了def reverse(self): prev None cur self.head while cur is not None: nxt cur.next cur.next prev prev cur cur nxt self.head prev反转这段代码我建议你手动画三遍图。核心就是三个指针的轮转先把下一步存下来nxt cur.next再掉头cur.next prev然后整体前移prev cur; cur nxt。存下一步必须放在最前面否则掉头之后你就找不到原来的后继了。这个 4 行的顺序是死的别自己改。4.4_size忘了同步导致越界判断失效这个坑最阴。功能测试全过因为遍历用的是cur is not None跟_size无关但insert、remove_at、get的下标检查全靠_size。一旦_size偏小你明明可以插入的位置被判定越界偏大则直接跑飞。我的解决办法是加一个断言式的自检方法只在调试时开def _check_size(self): n 0 cur self.head while cur is not None: n 1 cur cur.next assert n self._size, fsize 记录错误: 实际 {n}, 记录 {self._size}在开发阶段每个修改结构的方法末尾调一次。上线时用if __debug__或者环境变量关掉。这个习惯帮我省了不知道多少个通宵——凡是维护了冗余状态的地方就要有校验它的机制这在任何数据结构实现里都成立。5. 什么时候它真的比 list 强5.1 复杂度要按“最坏”和“平均”分开看教材上那张表人人会背但真正理解它的人不多。我把两种实现的真实差异列出来操作单链表Python list说明按下标访问O(n)O(1)链表必须从头跳头部插入O(1)O(n)list 头插要整体后移尾部插入O(n)均摊 O(1)链表无尾指针就得走到底已知前驱插入O(1)O(n)链表只需改两个指针按下标删除O(n)O(n)找到位置都得花时间按值查找O(n)O(n)都只能线性扫内存连续性差好影响 CPU 缓存命中这张表最需要读懂的是“头部插入”这一行。链表在头部插入只需要动两个引用跟链表多长完全无关而 list 头插要把所有元素往后挪一位一万个元素就挪一万次。这就是我在开篇让那位朋友做的实验他实测下来差距是几十倍。但别急着下结论说链表更快。list 的均摊尾部插入是 O(1)链表的按索引访问是 O(n)在绝大多数“读多写少、更多是顺序遍历”的场景里list 反而更快原因在下一节。5.2 缓存友好性一个被教材忽略的因素CPU 读内存不是一次读一个字节而是一次读一整个缓存行通常是 64 字节。list 元素在内存里挨着读第 1 个的时候后面十几个元素已经被顺带搬进缓存了所以你遍历 list 时大部分访问都命中了缓存。链表节点是散落的每读一个几乎都要去主存取一次命中率极低。结果是理论复杂度一样都是 O(n) 的遍历list 实测可能快好几倍。这是纯性能层面的现实写代码时如果链表不是“必须”list 往往是更务实的选择。那什么时候单链表真的值得用我的判断标准是三条满足任意一条就有意义需要在头部频繁插入、且完全不需要随机访问比如栈的链式实现、撤销历史记录需要把大对象“零拷贝”地串起来节点只存引用插入删除不搬运数据本体需要在遍历过程中做结构拼接比合并两个有序序列、把若干个片段连成一条链表改指针是 O(1)list 得重建。除这三条之外用 list 几乎都不会吃亏。5.3 和 collections.deque 比还是差一点如果你只是想要一个两端都能高效增删的容器Python 标准库里的collections.deque就是现成的双向链表实现底层是分块数组两头操作都是 O(1)还带 C 层加速。日常开发里我以为真正该手写单链表的场合基本都集中在“我需要理解结构本身”或者“面试需要现场写”而不是生产环境。这一点想清楚很重要能让你在写代码时保持诚实我写它是为了练手和理解不是为了在大项目里替换 list。心态摆正了你反而会更认真地扣每一个边界条件。6. 拿四道题把手感练出来6.1 反转理解指针轮转的母题反转是链表练习的第一题也是我建议反复写三遍的题。理由很简单它把“先存后改”这个动作暴露得最彻底。代码在 4.3 已经给出这里再强调一遍思路三个指针 prev / cur / nxt每一步做四件事顺序固定。写完一定要用空链表、单节点、两节点、三节点四种情况各测一遍。测的时候有个小技巧反转之后用__repr__打出来看。如果打印不出来、卡住了十有八九是造了环——多半是cur.next prev写在了nxt cur.next前面。6.2 快慢指针一趟扫描解决中点和判环快慢指针这个技巧的优雅之处在于它只用“速度差”就换来了空间上的零开销。def 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 False两个地方要抠。第一while条件必须写fast is not None and fast.next is not None顺序不能反。因为fast可能是 None你再去取fast.next就崩了Python 的and是短路求值前面为假就不会算后面。第二比较必须用is而不是因为我们要问的是“是不是同一个节点对象”不是“两个节点的数据是否相等”。用在数据有重复时会误判成环这个错误极难发现。判环还有个附加题找到环的入口。方法是用快慢指针相遇后把一个指针挪回头部然后两个指针都改成一次走一步再次相遇的地方就是入口。这个结论的推导有点绕但记住做法很容易面试时能直接写出来。6.3 合并两个有序链表dummy 节点的威力合并是链表里最能体现“代码整洁度”的题。不用 dummy 节点的版本要写一堆 if 判断头节点是谁用了之后可以写得非常干净def merge(a: LinkedList, b: LinkedList) - LinkedList: dummy Node() tail dummy pa, pb a.head, b.head while pa is not None and pb is not None: if pa.data pb.data: tail.next pa pa pa.next else: tail.next pb pb pb.next tail tail.next tail.next pa if pa is not None else pb result LinkedList() result.head dummy.next return resultdummy是个哨兵节点它的 data 没有意义存在的唯一目的是“让 tail 一开始就有个挂载点”。这样一来第一个节点的处理和后面的节点完全一样代码里一个特判都不需要。这个技巧在删除倒数第 n 个节点、分割链表、重排链表里都能用可以说是链表套路里性价比最高的一个。提示用 dummy 时千万记得最后返回的是dummy.next不是dummy。我第一次写的时候就是忘了结果返回的链表前面多了一个空数据节点排查了半小时。6.4 删除倒数第 n 个两个指针拉开距离思路很直观让 fast 先走 n 步然后两个指针一起走等 fast 到头的时候slow 正好停在要删节点的前一个。def remove_nth_from_end(ll: LinkedList, n: int): dummy Node(next_nodell.head) slow fast dummy for _ in range(n): fast fast.next while fast.next is not None: slow slow.next fast fast.next slow.next slow.next.next ll.head dummy.next return ll这里也用 dummy因为如果要删的正好是第一个节点slow 需要停在 dummy 上没 dummy 就没地方站。这个“用哨兵消掉头节点特判”的思路和 6.3 是同一个你会发现链表题里反复出现的都是这么几个套路。写完记得把ll.head从 dummy 上接回来并且同步_size。如果是在封装好的类里做_size - 1别忘。7. 我个人在实际操作中的体会写链表这件事我最大的体会是它教的不是数据结构而是“改一处、想三处”的谨慎。改一个 next你要同时问自己三个问题——原来的后继还有人指吗前驱现在指对了吗长度和边界条件同步了吗这三个问题问熟了后面写任何带引用关系的东西都会形成一个自动的检查反射。如果让我给刚上手的人一条最实用的建议那就是每加一个方法先在纸上画四个场景——空链表、单节点、两节点、三节点以上。这四个场景能覆盖掉九成以上的边界 bug。代码写完后不要信自己的眼睛直接跑断言尤其是头删和尾删这两个位置值得专门写两条测试盯着。再补一个我常用的小习惯链表类里所有修改结构的方法统一在末尾加一行# assert self._check_size()开发时取消注释发布时注掉。这行注释看着不起眼但它能让你在长长的一次调试里第一时间知道到底是逻辑错了还是计数错了。分清这两件事能省掉很多个夜晚。