单向链表

复习

• 引用与指针：保存数据的位置，让数据不必连续存放
• 数组：连续存储，随机访问快、增删慢
• 抽象数据类型：先规定能做什么

TL;DR

• 链表由节点组成，每个节点保存数据并指向下一个节点
• 插入与删除只需改指针，定位之后是 O(1)
• 代价是不能随机访问，查找要 O(n)
• 它与数组恰好互补

正文

　　数组“增删要挪动”的痛，根源在于元素必须连续。上一章我们备好了指针，现在就可以用它造出一个不要求连续的结构——链表（linked list）。

一节一节串起来

　　链表的成员叫节点（node）。每个节点大致包含两部分：

• 保存的数据
• 一个指向下一个节点的指针

　　整条链表从“头指针”开始，一个连一个，直到某个节点的指针为空，表示到头了。就像一列火车，每节车厢都知道自己后面挂着哪一节。

　　要遍历，就从头出发，顺着指针一节节走；要访问某个元素，也得从头找起，所以查找是 O(n)。

增删只需改指针

　　链表的优势体现在插入和删除上。

　　假设已经找到了要操作的位置。插入一个新节点，只需调整两处指针：让新节点指向原来的下一个，再让前一个节点指向新节点。删除则反过来，把前一个节点直接指向被删节点的下一个。整个过程不需要搬动任何其他元素，是 O(1)。

　　注意这里的“已经找到位置”这个前提——找位置本身仍要 O(n)。所以更准确的说法是：链表的插入删除，在定位之后是最廉价的。

与数组刚好互补

　　把两者放在一起看，特点正好相反：

　　数组用连续换随机访问，链表用指针换灵活增删。这就是为什么数据结构没有“最好”，只有“最适合当前操作”。

　　链表还能有一些变体：多存一个指针就能双向走，首尾相连就成环。这些进阶玩法，下一章再看。

思考题 1

　　链表在已定位位置插入为什么是 O(1)，而数组是 O(n)？

思考题 2

　　为什么链表的查找通常比数组慢？

小结

知识点

• 链表由带数据和指针的节点相连而成
• 定位后插入／删除为 O(1)
• 查找为 O(n)，不支持随机访问
• 链表与数组在操作代价上互补

参考资料

1. Wikipedia(zh)：链表：由节点通过指针相连的线性结构
2. Wikipedia(zh)：指针 (计算机科学)：链表中连接节点的关键

思考题答案（仅供参考）

思考题 1

　　因为链表节点之间靠指针相连，插入时只需修改几处指针，把新节点接进去，其他节点位置不动，所以定位后是 O(1)。而数组要维持连续，必须整体挪动插入点之后的元素，代价是 O(n)。

思考题 2

　　因为链表不支持随机访问，无法像数组那样一步跳到目标位置，只能从头顺着指针逐个走。最坏情况下要走完整个链表，所以查找是 O(n)。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪