数据结构第 2 章：线性表——顺序表与链表的取舍
线性表是这门课第一个真正要写代码的结构。它的逻辑关系简单到一句话就能说完（一对一、有唯一首尾），但同一个逻辑结构用两种存储方式实现后，性能差异巨大——这一章真正要学的是"什么时候选哪个"，而不是"两个都会写"。
一、线性表的定义
n 个数据元素的有限序列，n ≥ 0。除第一个元素外每个元素有且仅有一个直接前驱，除最后一个外有且仅有一个直接后继。
注意三个关键词：有限（元素个数确定）、序列（有顺序，元素有位置）、同类型（每个元素属于同一数据对象）。
二、顺序表：地址连续带来的能力与代价
顺序表用一组地址连续的存储单元依次存放元素，逻辑相邻即物理相邻。
设每个元素占 L 个存储单元，首地址为 LOC(a₁)，则第 i 个元素的地址是：
LOC(aᵢ) = LOC(a₁) + (i − 1) × L
这个公式意味着随机存取：给下标就能算出地址，取任意元素都是 O(1)。这是顺序表独有的能力，链表做不到。
代价在插入和删除。在第 i 个位置插入，需要把第 i 到第 n 个元素整体后移一位，平均移动 n/2 次，时间复杂度 O(n)；删除同理，平均移动 (n−1)/2 次，也是 O(n)。
按值查找仍要逐个比较，O(n)。按位查找 O(1)。
三、单链表：用指针换取灵活性
每个结点由数据域和指针域构成，指针指向下一个结点。物理位置不必相邻。
几个必考点：
- 头指针 vs 头结点：头指针是必须有的，指向第一个结点；头结点是额外加在第一个元素之前的空结点，可以让"在表头插入/删除"和"在中间操作"的逻辑统一，不必特判。引入头结点不是必须的，但能少写很多 if。
- 按位查找 O(n)：链表不能算地址，只能从头顺着 next 走。
- 插入删除 O(1)——前提是已经拿到了前驱结点。如果只知道位置 i，找前驱本身就要 O(n)，所以"链表插入比顺序表快"这句话要带条件说。
- 已知结点指针 p 要在其前插入：单链表做不到 O(1)（找不到前驱），常用技巧是"在 p 之后插入再交换数据"，但这只是逻辑上等价，结点地址变了。
四、头插法与尾插法：一句代码决定顺序
用头插法建表，读入序列会被逆序存储；用尾插法（必须维护尾指针）则保持原序。这是上机题和选择题的高频细节。
带尾指针的循环单链表还有一个实用性质：尾指针的 next 就是头结点，因此在这种结构上"在表头插入"和"在表尾插入"都只要 O(1)。
五、双向链表：用空间换操作便利
每个结点多一个 prior 指针。好处是找前驱变成 O(1)，插入删除的指针修改是对称的，但要注意顺序：在 p 之前插入 s 时，必须先让 s.prior 指向 p.prior、p.prior.next 指向 s，最后再处理 s.next 与 p.prior，顺序错了会断链。
双向循环链表是最常用的变体，判空条件是 head->next == head。
六、顺序表与链表的对比（这张表要背）
| 维度 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 地址连续，逻辑相邻即物理相邻 | 地址任意，用指针连接 |
| 随机存取 | 支持，按位查找 O(1) | 不支持，按位查找 O(n) |
| 插入删除 | 需移动元素，平均 O(n) | 已知前驱时 O(1) |
| 空间 | 需预分配，可能浪费或溢出 | 动态分配，但每结点多花指针空间 |
| 存储密度 | 高（=1） | 低（<1） |
| 适用场景 | 表长稳定、频繁按位访问 | 频繁插入删除、表长变化大 |
选型口诀：查得多用顺序，改得多用链表；表长已知且稳定用顺序，长度不可预测用链表。
七、一元多项式加法
这是链表的经典应用：每个结点存系数和指数，两个多项式按指数递减有序。相加就是一次归并——比较当前结点指数，相等则系数相加（和为 0 就删掉该结点），不等则把指数大的接到结果链表上。时间复杂度 O(m+n)。
这个例子的价值在于：它演示了"用链表组织非数值数据 + 归并式处理"，后面第 7 章的归并排序是同一个思路。
易错点清单
- 说"链表插入比顺序表快"时，必须补上前提：已定位到前驱。
- 头结点不是头指针；有头结点时，空表判据是
head->next == NULL，没有头结点时是head == NULL。 - 顺序表插入的平均移动次数是 n/2，删除是 (n−1)/2，别记反。
- 双向链表插入四步指针的顺序不能乱。
这一章在整门课里的位置
第 2 章是后面所有"链式结构"的原型：第 3 章的链栈与链队列、第 5 章的二叉链表、第 6 章的邻接表，本质都是单链表加一个语义。这一章的指针操作不熟，后面每一章都会卡在同一个地方。反过来，本章的顺序表又是第 7 章"直接插入排序、希尔排序"的实现载体——排序讲的其实是"在顺序表上如何移动元素更少"。
补充：三段必须能默写的代码骨架
链表的题几乎都是这三段的变体，骨架记不住就永远写不对。
1. 头插法建表（结果与输入逆序）
s = (Node*)malloc(sizeof(Node));
s->data = x;
s->next = head->next; // 先接后面
head->next = s; // 再接前面
2. 尾插法建表（保持原序，必须维护尾指针 r）
s = (Node*)malloc(sizeof(Node));
s->data = x;
r->next = s; // 挂到尾部
r = s; // 尾指针后移
r->next = NULL; // 收尾置空，否则会出现野指针
3. 删除第 i 个结点（必须先找前驱）
p = head; j = 0;
while (p && j < i-1) { p = p->next; j++; } // 找第 i-1 个
if (!p || !p->next) return ERROR; // 越界
q = p->next; p->next = q->next; // 摘链
free(q); // 释放
三段的共同点是顺序不能换：先接后、再接前；先找前驱、再摘链、最后释放。顺序错了要么断链，要么内存泄漏。
本篇是《数据结构与算法（93 讲）》第 2 章的知识点摘要。完整板书与 C 代码见 课程页；上一章 绪论，下一章 栈与队列。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 数据结构与算法（93讲） 93 讲