上个月帮一个朋友看代码，他甩过来一句：“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, data=None, next_node=None): 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, data=None, next_node=None): 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 += 1

Node(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 -1

index_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是 None，cur.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, f"size 记录错误: 实际 {n}, 记录 {self._size}"

在开发阶段，每个修改结构的方法末尾调一次。上线时用if __debug__或者环境变量关掉。这个习惯帮我省了不知道多少个通宵——凡是维护了冗余状态的地方，就要有校验它的机制，这在任何数据结构实现里都成立。

5. 什么时候它真的比 list 强

5.1 复杂度要按“最坏”和“平均”分开看

教材上那张表人人会背，但真正理解它的人不多。我把两种实现的真实差异列出来：

这张表最需要读懂的是“头部插入”这一行。链表在头部插入只需要动两个引用，跟链表多长完全无关；而 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 result

dummy是个哨兵节点，它的 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_node=ll.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()，开发时取消注释，发布时注掉。这行注释看着不起眼，但它能让你在长长的一次调试里，第一时间知道到底是逻辑错了，还是计数错了。分清这两件事，能省掉很多个夜晚。