手写双向链表：Python实现与指针操作详解

1. 为什么我劝你手写一遍双向链表单向链表刷过几道题的人都会写但双向链表真正动手从零实现一遍的人并不多。很多人觉得“不就是多一个 prev 指针吗”结果一写插入就断链、一删节点就野指针、一反转就绕晕。我带过几个刚入行的同学单向链表能默写双向链表让他现场写个insert_before十个里有七个会在边界条件上翻车。所以这篇东西不是教科书搬运是我自己反复写、反复讲之后沉淀下来的实操记录围绕Python 实现双向链表这件事把图解思路、指针操作顺序、边界处理、调试技巧一次讲透。先说清楚它是什么、能干什么。双向链表是一种线性数据结构每个节点除了存数据还存两个引用一个指向后一个节点next一个指向前一个节点prev。相比单向链表只能从头往后走双向链表可以双向遍历删除给定节点时不需要再从头找前驱时间复杂度从 O(n) 降到 O(1)。它适合什么场景浏览器前进后退、播放列表上一首下一首、撤销重做栈、LRU 缓存里的淘汰队列底层都常见它的影子。如果你正在学数据结构、准备面试、或者想给某个小工具加一个可双向游走的历史记录功能这篇内容都能直接拿去用。我写这篇的目标很明确让你看完能自己从零写出一个带完整边界处理的DoublyLinkedList类并且知道每一步为什么这么写、哪里最容易错、错了怎么排查。代码用 Python因为引用语义清晰、不用手动管内存能把注意力集中在指针逻辑本身。下面按“设计思路—核心细节—完整实现—踩坑排查”的顺序展开中间穿插图解式的文字描述帮你在大脑里建立节点之间的连线画面。2. 整体设计与思路拆解2.1 为什么用哨兵节点而不是裸头尾指针初学者写双向链表最常见的写法是维护self.head和self.tail两个指针插入删除时对“链表为空”“只有一个节点”“操作头节点”“操作尾节点”分别写 if-else。这么写能跑但分支多到怀疑人生我早期就是这么干的一个remove方法写了四十多行改一个 bug 冒出两个新 bug。后来我统一改成**哨兵节点sentinel**方案创建两个永远存在、不存业务数据的节点一个当虚拟头head一个当虚拟尾tail它们互相指向空链表就是head.next tail且tail.prev head。所有真实节点都夹在这两个哨兵中间。这么设计的好处是插入和删除永远不需要判断“是不是头/尾”“链表是不是空”因为任何真实节点的前后都必然存在一个节点至少是哨兵指针操作模式完全统一。用生活类比哨兵就像电影院每排最两端的固定扶手观众真实节点永远坐在两个扶手之间不管这排坐了几个人你往左往右伸手总能摸到一个实体不会摸空。这个思路把边界条件从“运行时判断”变成了“结构上消除”是我认为双向链表实现里最值得先讲的一个决策。代价是多占两个节点的内存以及遍历时要跳过哨兵。对绝大多数应用来说这点开销可以忽略换来的是代码量减半、bug 率大幅下降。我的建议很直接只要你不是在写极端抠内存的嵌入式代码一律上哨兵。2.2 节点类怎么设计才不别扭节点类本身很简单两个引用加一个值。但有个细节值得说__init__里 prev 和 next 默认给None还是给哨兵我的做法是默认None由链表类在插入时负责接线。原因是节点不应该知道自己属于哪个链表保持它是个“哑”数据载体职责单一调试时也更容易单独构造测试。另一个细节是__repr__。别小看这个方法调试链表时如果你print(node)出来是一串__main__.Node object at 0x...你根本没法看。给它加一个返回fNode({self.val})的 repr打印链表时一眼就能看出结构对不对。这是我自己踩过坑之后养成的习惯成本极低收益极高。至于用不用__slots__看情况。如果你要创建几十万个节点__slots__ (val, prev, next)能省下每个实例的__dict__开销实测内存能降三成左右。但如果你只是刷题或者写个小工具加了反而让代码多一行噪音。我的取舍是教学和日常用不加明确知道节点数量大的场景再加。2.3 核心操作清单与复杂度预期动手前先把要实现的方法列清楚避免写到一半发现漏了。一个够用的双向链表至少包含这些方法作用时间复杂度备注push_front(val)头部插入O(1)哨兵方案下无分支push_back(val)尾部插入O(1)有 tail 哨兵直接定位pop_front()删除头节点并返回值O(1)空链表要报错或返回 Nonepop_back()删除尾节点并返回值O(1)同上remove(node)删除指定节点O(1)双向链表的核心优势insert_before(node, val)在指定节点前插入O(1)考验指针顺序find(val)按值查找O(n)返回节点引用__len__长度O(1)维护 size 计数__iter__正向遍历O(n)跳过哨兵reverse()原地反转O(n)交换每个节点的 prev/next这张表就是我的验收清单。写完之后逐项对照每个方法都拿空链表、单节点、多节点三种情况各测一遍基本能覆盖九成以上的边界 bug。复杂度那一列不是摆设它决定了你选双向链表而不是数组的理由——remove(node)是 O(1) 这件事是双向链表在 LRU 这类场景里不可替代的根本原因后面会展开讲。3. 核心细节解析与实操要点3.1 指针接线的顺序为什么不能乱双向链表所有 bug 里八成出在插入和删除时指针赋值顺序错了。核心原则一句话先处理新节点与两侧节点的连接再断开旧连接赋值时先改“远端”再改“近端”避免自己覆盖自己。拿“在节点 p 前面插入新节点 n”举例。假设 p 的前驱是 a结构是a - p要变成a - n - p。正确顺序是n.prev p.prevn 的前驱先指向 an.next pn 的后继指向 pp.prev.next n也就是 a.next 指向 np.prev np 的前驱改成 n为什么第 1 步不能写成p.prev n先做因为一旦你先改了p.prev第 1 步里p.prev拿到的就已经是 n 而不是 a 了a 这个节点就彻底从链上丢失成了内存里飘着的孤儿。这就是典型的“自己覆盖自己”。我教人的口诀是新节点先认亲把自己的两个指针指好再让邻居认它改邻居的指针最后改被插入节点的指针。顺序记牢基本不会断链。删除节点 n 的顺序同理结构是a - n - b要变成a - bn.prev.next n.nexta.next 指向 bn.next.prev n.prevb.prev 指向 a可选n.prev n.next None断开 n 自身的引用帮助垃圾回收也防止误用前两步顺序其实可以互换因为改的是两个不同节点的字段互不影响。但第 3 步我强烈建议加上尤其在 Python 里虽然 GC 能处理循环引用但主动断开能让“这个节点已经不在链上了”这件事在调试时一目了然也避免你拿着旧引用误操作把已删除节点又接回去。3.2 哨兵方案下空链表的形态长什么样很多人对哨兵的理解停留在“加两个假节点”但没在脑子里建立起空链表的具体画面导致写pop时不知道判断什么。空链表的确切形态是head - tail即head.next is tail且tail.prev is head同时head.prev和tail.next没有意义可以指向 None 或自己我习惯指向 None 并在文档里注明不要访问。判断链表为空就一句self.head.next is self.tail。注意用is而不是因为我们比较的是对象身份不是值相等——万一你的节点实现了__eq__用可能出幺蛾子。有了这个画面pop_front的逻辑就清晰了先判断空空则抛异常否则待删节点n head.next然后走标准删除流程返回n.val。整个过程不需要判断“删完是不是空了”因为删完之后自然又回到head - tail的形态结构自洽。这就是哨兵方案“边界条件结构上消除”的具体体现你写的时候会明显感觉到分支少了、心不慌了。3.3 反转操作为什么是双向链表的照妖镜reverse()是我面试别人时最爱出的题因为它同时考察遍历、指针交换、哨兵处理三件事。双向链表反转的本质是把每个节点的 prev 和 next 互换然后把 head 和 tail 两个哨兵也互换角色。具体做法从head开始注意是从哨兵开始不是从第一个真实节点沿着原来的 next 方向走每到一个节点就交换它的 prev 和 next。走完之后原来的 head 哨兵的 next 指向了原来的第一个真实节点但反转后它应该变成尾哨兵。所以最后要把self.head, self.tail self.tail, self.head交换一下。这里有个极易错点遍历时你交换了当前节点的 prev/next 之后下一个节点要用交换前的 next 去找。如果你写成先交换再cur cur.next那你拿到的是交换后的 next也就是原来的 prev直接往回走了死循环。正确写法是先存nxt cur.next交换再cur nxt。这个坑我见过太多人踩包括我自己第一次写的时候盯着屏幕找了十分钟。3.4 用图解思维辅助调试文字描述指针关系容易绕我的习惯是拿张纸画三个方框代表 a、n、b中间画双向箭头然后按代码顺序一步步擦掉重画箭头。写代码前先在纸上把插入和删除的箭头变化画一遍比对着屏幕空想快得多。如果你不想用纸用 Python 的id()打印节点地址也能辅助验证插入后检查a.next is n、n.prev is a、n.next is b、b.prev is n四个断言是否同时成立全 True 才算接线正确。这种“断言式验证”我在写链表时用得非常多比肉眼盯着看靠谱。4. 完整实现与逐段讲解4.1 节点类与链表骨架先把地基打好。节点类保持极简链表类在__init__里建好两个哨兵并互相连接同时维护一个size计数。class Node: __slots__ (val, prev, next) def __init__(self, valNone): self.val val self.prev None self.next None def __repr__(self): return fNode({self.val}) class DoublyLinkedList: def __init__(self): self.head Node() # 虚拟头哨兵 self.tail Node() # 虚拟尾哨兵 self.head.next self.tail self.tail.prev self.head self.size 0这里我用了__slots__因为链表节点往往数量多省内存是实打实的。size单独维护而不是每次遍历去数是为了让__len__保持 O(1)——这在需要频繁取长度的场景比如判断缓存是否超限里很关键。哨兵的val留 None永远不参与业务。4.2 插入操作的统一写法有了哨兵头部插入和尾部插入可以共用一个内部方法_insert_between(a, b, val)表示在 a 和 b 之间插入新节点。头部插入就是_insert_between(head, head.next, val)尾部插入就是_insert_between(tail.prev, tail, val)。这种“把差异收敛到一个参数化方法”的写法是我认为双向链表实现里第二值得学的设计第一是哨兵本身。def _insert_between(self, a, b, val): n Node(val) n.prev a n.next b a.next n b.prev n self.size 1 return n def push_front(self, val): return self._insert_between(self.head, self.head.next, val) def push_back(self, val): return self._insert_between(self.tail.prev, self.tail, val) def insert_before(self, node, val): return self._insert_between(node.prev, node, val)注意_insert_between里四行赋值的顺序先设 n 的两个指针再改 a 和 b。这正好对应 3.1 节讲的“新节点先认亲邻居再认它”。insert_before直接复用传入node.prev和node即可完全不用判断 node 是不是第一个真实节点——因为它的 prev 至少是 head 哨兵。这就是哨兵带来的红利代码短且没有分支。4.3 删除操作的统一写法删除同样收敛成一个内部方法_unlink(node)负责把 node 从链上摘下来并返回它的值。def _unlink(self, node): if node is self.head or node is self.tail: raise ValueError(不能删除哨兵节点) node.prev.next node.next node.next.prev node.prev node.prev None node.next None self.size - 1 return node.val def pop_front(self): if self.size 0: raise IndexError(链表为空) return self._unlink(self.head.next) def pop_back(self): if self.size 0: raise IndexError(链表为空) return self._unlink(self.tail.prev) def remove(self, node): return self._unlink(node)_unlink里加了一个哨兵保护防止误传 head 或 tail 进来把结构搞崩。这个检查成本极低但能挡住一类很隐蔽的 bug——比如你在遍历时不小心把哨兵当成了真实节点传进去。删除后把 node 的 prev/next 置 None一是帮 GC二是让“这个节点已脱链”这件事在调试时可见。pop_front和pop_back只在空链表时抛异常非空时直接交给_unlink逻辑干净。4.4 查找、遍历与长度查找就是从头哨兵后面开始往后走走到尾哨兵停。遍历用生成器实现天然支持for x in lst。def find(self, val): cur self.head.next while cur is not self.tail: if cur.val val: return cur cur cur.next return None def __iter__(self): cur self.head.next while cur is not self.tail: yield cur.val cur cur.next def __reversed__(self): cur self.tail.prev while cur is not self.head: yield cur.val cur cur.prev def __len__(self): return self.size def __repr__(self): return - .join(str(v) for v in self)__reversed__是双向链表相对单向链表的独有便利从尾哨兵往前遍历即可不需要先反转。__repr__用-连接打印出来一眼能看出双向结构调试时非常顺手。find返回节点引用而不是布尔值或索引是为了配合remove(node)和insert_before(node, val)使用——先 find 拿到节点再 O(1) 删除或插入这是双向链表的标准用法。4.5 原地反转的完整实现按 3.3 节的思路写注意先存 next 再交换。def reverse(self): cur self.head while cur is not None: nxt cur.next cur.prev, cur.next cur.next, cur.prev cur nxt self.head, self.tail self.tail, self.head这段代码短但每一行都有讲究。从 head 哨兵开始遍历包括两个哨兵在内所有节点都交换 prev/next走完后整条链的方向就反了最后交换 head 和 tail 的引用让哨兵角色归位。cur is not None的终止条件是因为尾哨兵交换后它的 next 变成了原来的 prev指向倒数第二个节点继续走会绕回去所以用 None 判断——实际上尾哨兵原来的 next 是 None我们在__init__里没设 tail.next交换后它变成 prev 是 None走到尾哨兵时nxt cur.next拿到的是交换前的 next 即 None循环自然结束。这个细节建议你拿纸画一遍画完就彻底懂了。4.6 一段可直接跑的验证脚本写完不测等于没写。我习惯用一段脚本把所有边界情况过一遍断言全过才算收工。if __name__ __main__: d DoublyLinkedList() assert len(d) 0 d.push_back(1); d.push_back(2); d.push_front(0) assert list(d) [0, 1, 2] assert list(reversed(d)) [2, 1, 0] n d.find(1) d.insert_before(n, 99) assert list(d) [0, 99, 1, 2] d.remove(n) assert list(d) [0, 99, 2] assert d.pop_front() 0 assert d.pop_back() 2 assert list(d) [99] d.reverse() assert list(d) [99] d.push_back(100); d.push_front(50) d.reverse() assert list(d) [100, 99, 50] print(all passed)这段脚本覆盖了空链表、单节点、多节点、头插尾插、指定位置插入删除、正反遍历、反转前后一致性。跑出all passed那一刻才算真正完成。我建议你把这脚本留着以后改任何一行实现都重跑一遍回归测试的价值在数据结构这种“牵一发动全身”的代码里尤其明显。5. 常见问题与排查技巧实录5.1 断链、野指针、死循环三大高频故障实际写的时候报错往往不是语法错而是逻辑错表现为三种症状。我把它们和排查方法整理成表方便你对号入座。症状典型原因排查方法遍历时AttributeError: NoneType object has no attribute next某处 next 没接上走到了 None从头开始逐个打印节点找到第一个 next 为 None 的真实节点检查它的插入/删除代码遍历死循环停不下来反转时先交换再取 next或删除时漏改某个 prev加计数器走超过 size2 步就 break 并打印当前节点pop后链表长度对但内容错乱_unlink里两行赋值顺序写反或漏写一行用 3.1 节的四个断言逐项验证 a.next、b.prev 是否正确反转后只能正向不能反向忘了交换 head 和 tail 哨兵检查reverse最后一行是否做了哨兵互换这张表是我这些年 debug 链表攒下来的经验浓缩。特别说第一条NoneType报错几乎百分百是某次插入时新节点的 next 没指向正确位置导致链在这里断了。定位方法就是从 head 开始顺着 next 走边走边打印第一个断点就是案发现场。5.2 哨兵用错引发的隐蔽 bug哨兵方案虽然省事但有两个坑新手常踩。第一个是把哨兵当真实节点遍历比如find里写成while cur:而不是while cur is not self.tail结果尾哨兵的 val 是 None可能被误匹配或者继续往后走访问到 None 报错。第二个是删除时没保护哨兵误把 head 或 tail 传进_unlink直接把链表结构拆了而且这种错误往往不立即报错等到后续操作才暴露极难定位。所以我在_unlink里加了身份检查宁可多一行防御也不要事后花两小时找 bug。还有一个隐蔽点判断空链表用self.head.next is self.tail别用。如果你的 Node 哪天实现了__eq__按 val 比较两个 val 都是 None 的哨兵用会返回 True逻辑就错了。用is比较对象身份永远安全。这种“看起来吹毛求疵”的细节恰恰是代码从能跑到可靠的差距。5.3 性能上的几个实测心得双向链表理论复杂度好看但 Python 里实际跑起来有几个点值得注意。第一__slots__对大量节点的内存优化很明显我实测十万个节点能省下约三成内存如果你的场景节点数上万加上它。第二find是 O(n)如果你需要频繁按值查找双向链表不是好选择考虑配一个 dict 做索引把 find 降到 O(1)代价是插入删除时多维护一份映射。第三reverse虽然 O(n)但常数比想象中大因为每个节点要读写四个指针字段如果反转操作非常频繁可以考虑维护一个方向标志位逻辑上反转、物理上不动读的时候根据标志决定遍历方向——这是空间换时间的经典权衡我在做一个可双向游走的历史记录功能时就这么干过效果不错。5.4 什么场景该用、什么场景别用最后说选型。双向链表适合需要 O(1) 删除已知节点LRU 缓存、需要双向遍历浏览器历史、播放列表、插入删除频繁且位置已知。不适合需要随机访问用数组或 list、需要频繁按值查找配哈希表或直接用 dict、数据量小且操作简单list 完全够用别过度设计。我见过有人为了“显得专业”在只有几十条数据的配置列表上用双向链表结果代码复杂度翻倍收益为零。数据结构的价值在于匹配场景不在于高级与否。我个人在实际操作中的体会是双向链表这东西看十遍不如写一遍写一遍不如画一遍图再写一遍。指针操作的直觉是靠手和纸喂出来的光看代码永远差一层。你现在就可以打开编辑器把 4.1 到 4.5 的代码敲一遍跑通 4.6 的验证脚本然后故意把_insert_between里四行赋值的顺序打乱看看会报什么错、怎么排查——这种“故意制造 bug 再修”的练习比顺风顺水写十遍学到的都多。