“单链表和双链表”这个题目，几乎是每个学编程的人都会遇到的第二个数据结构（第一个当然是数组）。很多人在这一步开始吃力：不是看不懂定义，而是边界条件一多就崩，指针指来指去把自己绕晕。其实链表并没有那么玄，你把单链表想成一串手拉手站队的节点就明白了——每个节点既保存自己的数据，又记得下一个人是谁；双链表就是每个人再多记一条：上一个人是谁。差别只有这一个字段，但能力和成本完全是两个量级。
这篇文章我准备从数组的痛点讲起，把单链表和双链表的设计思路、核心操作、实现代码、选型逻辑和调试经验串起来讲透。适合正在学数据结构的学生、准备手写算法题的面试者，以及想单独把链表这块补强的开发。我会尽量用最直白的话，把这些账一笔一笔算清楚。
1. 单链表先解决的问题：数组的别扭在哪
1.1 数组的读写思维
数组在内存里是一段连续地址，比如int arr[10]，编译时就把 10 个格子紧挨着排好了。访问arr[5]为什么快？因为地址可以直接算出来：首地址 + 5 × 单个元素大小，所以数组随机访问是 O(1) 的。这是数组最大的优点，也是很多场景下链表“打不过”数组的原因。
但维护“顺序”这件事，数组做起来很痛。想在索引 2 的位置插入一个数，索引 2 以及后面的元素全部要往后挪一位，平均要搬 n/2 个元素，复杂度 O(n)。删除同理，后面元素全部要往前补位。数组越长，搬移成本越高，这是一个隐藏的定时炸弹。
你可以想象一个电影院的连排座位，所有人必须挨着坐。这时中间有人要坐下，后面所有人都得站起来顺移一个位子；有人要离开，后面所有人再去补位。这种“物理搬移”就是数组的宿命：连续存储带来随机访问快，同时带来插入删除慢。
1.2 链表的解决方式：把顺序交给指针
链表换个思路：根本不需要大家坐在一起，每个人随便站在哪，只要记住“我后面那个人是谁”就行。对应到数据结构，就是每个节点保存两部分：data 和 next 指针。data 是实际数据，next 指到下一个节点。这样插入删除只需要改指针关系，完全不用搬数据。
比如已经有 A → B → C 这条链，想在 B 和 C 之间插入 X，只需要：
- B.next 指向 X
- X.next 指向 C
三步就完了，跟链表长度完全没有关系，O(1)。当然前提是你已经找到了 B，而找到 B 需要从头走，那是 O(n)。所以在链表里，插入删除本身很快，慢的是查找。
这个“用指针关系代替物理相邻位置”的思路，是整个链表的核心。理解了这一点，后面单链表和双链表的差别、应用场景，基本都能顺着推出来。
1.3 单链表的一处先天不足
单链表每个节点只有一个 next，意味着指针只能朝一个方向走。听起来没什么，实际影响很大：
- 想删除某个已知节点，单链表必须从头遍历找到它的前驱节点，因为只有前驱的 next 指向它，改前驱的 next 才能把它从链上摘下来。
- 想反向遍历，单链表直接做不到。只能先把链表反转，再遍历一遍，或者借助栈临时存储。
- 想维护尾节点 tail 做 O(1) 尾删，也做不到。删掉 tail 之后，新的 tail 是谁？不知道，因为 tail 没有 prev 指向它的前驱。
这些“先天不足”不意味着单链表不好，而是说任何数据结构都有代价。单链表把空间和代码复杂度压到最低，必然要牺牲一些操作能力。接下来把单链表的常用操作一个个过一遍，你会更清楚这些限制具体会怎么影响写代码。
2. 单链表核心操作与实现要点
2.1 节点长什么样
无论用哪种语言，链表节点本质都是一样的。C 语言里通常是：
typedef struct Node { int data; struct Node *next; } Node;Python 里用类表达：
class Node: def __init__(self, data): self.data = data self.next = Nonenext在 Python 里是对象引用，本质跟 C 的指针是一个意思：它存放的是“下一个节点在哪”的信息。很多同学写 Python 链表没有指针感，其实引用就是指针，只是不需要手动管理内存而已。
2.2 头插法与尾插法
单链表最常见的两种建链方式，一个是插在头部，一个是接在尾部。
头插法把新节点放在 head 前面：
def insert_at_head(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node尾插法需要先找到最后一个节点：
def insert_at_tail(self, data): new_node = Node(data) if self.head is None: self.head = new_node return cur = self.head while cur.next is not None: cur = cur.next cur.next = new_node这两个操作有个关键区别：头插是 O(1)，尾插在没有维护 tail 指针时是 O(n)。而且头插会反转输入顺序，比如依次插入 1、2、3，最终链表是 3 → 2 → 1。这个特性有时候很有用，比如把一串逆序数据构建成链表，头插法顺手就完成了反转。
如果你经常需要尾插，可以考虑给单链表加一个 tail 指针，这样尾插也是 O(1)。但要注意，加了 tail 之后，删除尾节点会变得麻烦，因为你仍然不知道 tail 的前驱是谁。这就是单链表的一个经典权衡：维护额外指针可以加速某些操作，却会在另一些操作上付出代价。
2.3 删除节点：前驱是灵魂
单链表删除一个节点，最常规的写法是找到目标节点 cur，并且同时维护一个 prev 指向它的前驱，然后：
prev.next = cur.next这一步把前驱直接接到目标节点的后继，目标节点就从链上被跳过了。如果是删除头节点：
self.head = self.head.next要先处理这种特殊情况，否则 head 指针都不知道该指向哪。
为什么单链表删除必须找前驱？因为每个节点只存了“后面是谁”，没有“前面是谁”。你拿着当前节点，知道你后面是谁，但你无法从当前节点倒推出前面是谁。所以只能从头扫描，一边走一边记着上一个节点。这就是前面说的“先天不足”最直接的体现。
有个“偷梁换柱”的手法可以绕开前驱：把 next 节点的 data 复制到当前节点，然后删掉 next 节点。这在“只给你目标节点指针，不给你头节点”的面试题里很常用。代价是如果外部还有其他指针引用了那个被删的 next 节点，它的地址还在用，逻辑上会有影响。工程上要谨慎，面试答题可以秀一手。
2.4 反转链表：完全靠改方向完成
反转链表是单链表里最经典的高频题，也非常考验对指针操作顺序的理解。迭代写法是这样的：
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 一起往后挪。
为什么要先保存nxt？因为一旦执行cur.next = prev，原来 cur 指向下一个节点的那条链就断了。如果你没有提前把下一个节点记住，那后面的节点全丢了，链表直接断成两截。很多人第一次写反转链表就是栽在这里：顺序反了，链就没了。这里有一个通用原则：改任何指针之前，先想清楚“这个指针原来的值还有没有人需要”。需要，就先保存，再改。
3. 双链表：多一个指针到底值不值
3.1 从单向到双向，能力强在哪
双链表节点结构在单链表基础上加了一个 prev 指针：
typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;多这一个字段，直接带来的能力是：可以从任意节点往回走。如果你同时维护 head 和 tail，那么正着遍历、反着遍历都只需要 O(n)；头部插入、尾部插入都是 O(1)；删除任意已知节点，也是 O(1)。
这在单链表里想都不敢想。单链表删除已知节点需要找前驱，双链表不需要，因为节点自己就存了前驱。单链表无法直接反向遍历，双链表从 tail 顺着 prev 一路走就行。
代价也很明确：每个节点多一个指针的开销。假设指针占 8 字节，100 万个节点就多 8 MB。在内存敏感的嵌入式环境里，这个差别可能直接导致方案不可行。但在常规服务器、桌面开发里，这点内存通常可以接受。
3.2 删除给定节点：真正的 O(1)
给你一个已经找到的节点 node，在双链表里删除它：
node.prev.next = node.next node.next.prev = node.prev两行就够，前提是 node 不是头尾节点。实际代码需要判断边界：
if node.prev is not None: node.prev.next = node.next else: self.head = node.next if node.next is not None: node.next.prev = node.prev else: self.tail = node.prev这两个分支就是双链表删除的难点所在：头节点没有 prev，尾节点没有 next，需要单独更新 head 或 tail 指针。代码量比单链表多，但换来的是删除动作跟链表长度无关。在相关操作非常频繁的场景，这个优势会碾压单链表。
3.3 典型应用：缓存、历史记录、撤销
双链表在真实工程里最常见的例子就是 LRU 缓存淘汰算法。经典实现是哈希表 + 双向链表：哈希表负责 O(1) 找到节点，双向链表负责 O(1) 删除节点和把节点移动到头部。
为什么这里一定要用双链表？因为缓存命中某个节点后，要把它从当前位置摘下来，再放到头部，这个动作包含“删除已知节点”。单链表哈希表只存了指向节点的指针，没有前驱信息，删除时就没法 O(1)。双链表因为有 prev，一个节点自己就能完成摘除。这是所有讲解资料里都会提到的点，也确实是最能说明双链表价值的场景。
还有一些场景也很典型：
- 浏览器前进后退：双链表天然表示当前页面、上一页、下一页的关系。
- 编辑器撤销重做：每个状态是一个节点，prev 是上一个状态，next 是下一个状态。
- 内核与底层系统中，大量链表都是双向的，因为需要任意一处快速插入和删除。
这类场景的共同特征是：节点之间既有“往前”的关系，又有“往后”的关系，而且操作频繁、不能接受 O(n) 的查找前驱。
4. 单链表和双链表怎么选：一份实在的对比
4.1 关键维度对照
| 操作 / 维度 | 单链表 | 双链表 |
|---|---|---|
| 随机访问 | O(n) | O(n) |
| 头部插入 | O(1) | O(1) |
| 尾部插入（有 tail） | O(1) | O(1) |
| 删除已知节点 | 需先找前驱 O(n) 或偷梁换柱 | O(1) |
| 反向遍历 | 不可直接做 | O(n) 从尾到头 |
| 单节点内存 | data + 1 个指针 | data + 2 个指针 |
| 实现复杂度 | 较低 | 较高，边界分支多 |
| 缓存友好度 | 低（节点分散在堆里） | 更低（又多一个指针） |
| 异常处理难度 | 相对简单 | 头尾指针更新容易漏 |
看这张表，你会发现单链表和双链表在“查找”上都没优势，都是 O(n)。区别集中在“删除已知节点”和“反向遍历”这两件事上。如果你的业务需要频繁做这两件事，双链表的优势是压倒性的；如果基本不做，那单链表内存更省、代码更简单，没必要为了“高级”去用双链表。
4.2 工程与面试场景的选型建议
工程上我的习惯是：先看操作模式，再谈数据结构。如果只从头部插入、从头部删除，或者主要做栈式操作，单链表足够，双链表纯属浪费内存。如果数据量很大、对内存配额敏感，优先考虑单链表，甚至可以考虑用数组模拟链表来提升缓存友好度。
如果系统里需要频繁删除“任意已知位置”的节点，或者需要双向遍历，比如 LRU、消息队列、游戏实体管理，直接上双链表，别纠结那一个指针的开销。代码复杂度多出来的一点，未来省下的时间远不止那点。
面试场景有个不成文的规律：大多数链表手写题，比如反转、合并、找环、找中点，默认都是单链表。不是因为双链表难，而是题目想考你对指针跳转和边界条件的把握，单链表已经把难度放到恰到好处。双链表通常出现在“设计 LRU”这一类综合题里。“查重”时心里要有数：刷题阶段先把单链表练熟，再把双链表用于 LRU、删除节点等场景，不要一上来就双链表包打天下。
5. 手写实现：一套能跑的代码和边界清单
5.1 代码目标与测试思路
下面给出完整可直接运行的 Python 实现，覆盖单链表和双链表常用的操作：头插、尾插、删除、遍历，单链表额外加反转，双链表额外支持从尾遍历。代码追求清晰，不追求花哨，方便对照理解。
测试思路我建议这么来：先测一个空链表，再测长度为 1 的链表，最后测长度超过 1 的链表。空链表最容易忽略，但也是最容易出错的地方。
5.2 单链表完整实现
class Node: def __init__(self, data): self.data = data self.next = None class SinglyLinkedList: def __init__(self): self.head = None def is_empty(self): return self.head is None def insert_at_head(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def insert_at_tail(self, data): new_node = Node(data) if self.is_empty(): self.head = new_node return cur = self.head while cur.next is not None: cur = cur.next cur.next = new_node def delete(self, data): cur = self.head if cur is not None and cur.data == data: self.head = cur.next return True while cur is not None and cur.next is not None: if cur.next.data == data: cur.next = cur.next.next return True cur = cur.next return False 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 def to_list(self): result = [] cur = self.head while cur is not None: result.append(cur.data) cur = cur.next return result简单验证一下：
sll = SinglyLinkedList() sll.insert_at_head(2) sll.insert_at_head(1) sll.insert_at_tail(3) print(sll.to_list()) # [1, 2, 3] sll.delete(2) print(sll.to_list()) # [1, 3] sll.reverse() print(sll.to_list()) # [3, 1]insert_at_tail里有个细节想特别提醒：循环里用的是cur.next而不是cur。如果写成while cur is not None，那么循环结束时 cur 已经变成了 None，最后一行cur.next = new_node就会报错。很多初学者在这里卡住，其实只要想清楚‘我要的是最后一个节点，而不是 null’，就不会写错了。
5.3 双链表完整实现
class DNode: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.tail = None def insert_at_head(self, data): new_node = DNode(data) if self.head is None: self.head = self.tail = new_node return new_node.next = self.head self.head.prev = new_node self.head = new_node def insert_at_tail(self, data): new_node = DNode(data) if self.tail is None: self.head = self.tail = new_node return new_node.prev = self.tail self.tail.next = new_node self.tail = new_node def delete(self, data): cur = self.head while cur is not None and cur.data != data: cur = cur.next if cur is None: return False if cur.prev is not None: cur.prev.next = cur.next else: self.head = cur.next if cur.next is not None: cur.next.prev = cur.prev else: self.tail = cur.prev return True def traverse_from_head(self): result = [] cur = self.head while cur is not None: result.append(cur.data) cur = cur.next return result def traverse_from_tail(self): result = [] cur = self.tail while cur is not None: result.append(cur.data) cur = cur.prev return result验证：
dll = DoublyLinkedList() dll.insert_at_tail(1) dll.insert_at_tail(2) dll.insert_at_tail(3) print(dll.traverse_from_head()) # [1, 2, 3] print(dll.traverse_from_tail()) # [3, 2, 1] dll.delete(2) print(dll.traverse_from_head()) # [1, 3] print(dll.traverse_from_tail()) # [3, 1]双链表 delete 方法里那四个 if 分支是重点。删除的节点如果是头节点，head 要移到下一个；如果是尾节点，tail 要移到上一个。很多 bug 就是只改了链表方向指针，忘了更新 head 或 tail，导致后续操作一头撞到已经不属于链表的节点上。
5.4 边界条件清单
| 场景 | 必须检查的内容 |
|---|---|
| 空链表 | 插入 / 删除 / 遍历都不能崩溃，删除返回 False |
| 只有一个节点 | 删除后 head 和 tail 都应为 None |
| 删除头节点 | head 是否成功指向原第二个节点 |
| 删除尾节点 | tail 是否成功指向原倒数第二个节点 |
| 删除不存在的节点 | 返回 False，且链表结构不能有任何变化 |
| 反转单链表 | 空链表、单节点链表反转后仍是自身 |
这份清单建议每次写完链表代码都对一遍。按这个顺序测下来，90% 的隐藏问题都能暴露。
6. 常见问题与调试技巧实录
6.1 空指针解引用：新手第一杀手
链表报错里最经典的就是空指针解引用。C 语言直接崩溃，Python 会报AttributeError: 'NoneType' object has no attribute 'next'。
根因通常是在cur已经为 None 的情况下访问了cur.next。比如遍历找最后一个节点时，有些人会写成：
while cur.next is not None: cur = cur.next这种情况如果链表本身是空的，第一次循环就会炸。正确写法是先判断cur is not None，再用短路的写法：
while cur is not None and cur.next is not None: cur = cur.nextC 语言里同样要用while (cur && cur->next)这种顺序。判断条件的顺序非常重要，前者为假就不会执行后者，这就是常见的短路保护。养成“先检查节点是否存在，再访问它的字段”的习惯，能少调很多 BUG。
6.2 断链与循环：改指针的顺序问题
链表里修改指针关系的顺序有一句口诀：先接新链，再断旧链。插入操作最容易犯的错是：
# 错误示范 prev.next = new_node new_node.next = prev.next # 此时 prev.next 已经是 new_node，原后继丢了第二行里prev.next已经被改掉了，所以new_node.next指向了它自己，后面一段节点全断了。正确顺序是先让新节点指好后继，再更新前驱的 next：
new_node.next = prev.next prev.next = new_node删除操作也类似，要先把需要的指针保存下来，改完链再清理引用。程序员平时常说的“顺序错了，链就断了”，多半就是这个场景。我在实际写代码时，遇到指针操作都会先在纸上画一条链，标出每一步前后谁指向谁。画完再写，基本不会顺序错。
6.3 C 语言场景下的内存管理
Python 帮你管了内存，但 C 语言不是。用malloc创建节点，用完之后必须free，否则就是内存泄漏。
删除节点的常规顺序是：先改好链表指针，把目标节点从链上摘下来，再 free 这个节点的内存。如果先 free，再去改前后节点的指针，就出现了悬空指针，等于访问一块已经还给系统的内存，轻则随机崩溃，重则内存 corruption。
写 C 链表时还会遇到另一个问题：节点还在链上，却被重复 free 了。比如删除函数把 cur 摘下来后 free 了，调用者又持有一个指向 cur 的指针再去 free 一次，就是 double free。这种问题很难现场看出来，推荐在开发阶段用内存检测工具跑一遍，能够稳定定位。
6.4 调试链表的三个习惯
这些年调试链表代码，我总结出三个很实用的习惯：
第一，写一个打印函数。单链表输出str，双链表分别从头和尾各输出一遍。每次操作后都打出来看，不会凭空猜。代码写错了，打印结果往往一眼就看出问题。
第二，用小数据集合覆盖所有边界。固定用 3 个元素的链表测头插、尾插、删除头、删除尾、删除中间、删除不存在，一遍下来基本能把所有分支覆盖到。不要一上来就用几十个元素的链表，边界反而不容易看清楚。
第三，不会画图就白学链表。尤其是双链表，纸上画两个方向的箭头，比在脑子里盲推快一个数量级。任何讲链表的数据结构书都不会脱离图示，自己调试时更应该掏出纸笔。
说完最后一点体会
我自己的感觉是，链表题目最容易错的永远不是思路，而是边界条件和执行顺序。十次报错里七次是空指针，两次是断链，一次是忘了维护 head/tail。所以我现在写链表之前，一定会先在脑子里把空链表、单节点、头操作、尾操作、删除中间节点这些情况过一遍，再动手。这个习惯坚持下去，单链表和双链表就不会再成为障碍。遇到特别绕的题目，就在纸上画一条链，标好每一步，然后照着图写代码，一次到位的概率会高很多。
