13.1.2 顺序表与链表

顺序表和链表都是线性表。课程反复强调：差异不在线性逻辑，而在物理存储。顺序表把元素放在连续空间中，链表把元素放在节点中，再用指针把节点串起来。

顺序表：用空间连续换随机访问

顺序表可以看成数组。创建时通常要先申请一段连续空间，例如下标 0 到 7 的 8 个位置。因为每个元素长度固定，第 $i$ 个元素地址可以直接算出来：

$$Loc(a_i)=Loc(a_0)+i\times L$$

如果下标从 1 开始：

$$Loc(a_i)=Loc(a_1)+(i-1)\times L$$

操作	代价	原因
读取第 $i$ 个元素	$O(1)$	地址可直接计算
按值查找	$O(n)$	需要逐个比较
插入	平均 $O(n)$	插入位置之后的元素要后移
删除	平均 $O(n)$	删除位置之后的元素要前移

链表：用指针开销换插删灵活

链表的节点由数据域和指针域组成。它不要求物理地址连续，头指针能找到第一个节点，后续节点靠 next 指针连接。

flowchart LR
  Head["head"] --> A["data|next"]
  A --> B["data|next"]
  B --> C["data|next"]
  C --> Null["NULL"]

链表读取第 $i$ 个节点不能直接跳过去，必须从头指针开始沿 next 走。因此按序读取和查找都是 $O(n)$。

单链表删除：必须处理前驱

课程里用 p 指向前驱节点，q 指向待删除节点。删除 q 的核心语句是：

p->next = q->next;
free(q);

真正的难点不是这句赋值，而是“是否已经知道前驱节点”。如果只知道要删除的节点，单链表往往还要从头遍历找到它的前驱。

单链表插入：顺序不能反

若要把新节点 s 插入到 p 后面，正确顺序是：

s->next = p->next;
p->next = s;

如果先写 p->next = s，原来 p 后面的节点地址就丢了，链断掉。链表插入删除题非常喜欢考这种指针修改顺序。

双链表：多一个前驱指针

双链表节点同时有 prior 和 next，所以可以双向移动。

插入 q 到 p 后面：

q->prior = p;
q->next = p->next;
p->next->prior = q;
p->next = q;

删除 p：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

双链表修改的指针更多，但如果已知节点，删除时更容易找到前驱。

顺序表与链表对比

比较项	顺序表	链表
存储空间	连续，通常预先分配	可离散分配
存储密度	只存数据，密度接近 1	节点含指针域，密度小于 1
容量变化	受预分配空间限制	更灵活
随机访问	支持，$O(1)$	不支持，$O(n)$
插入删除	要移动元素，平均 $O(n)$	已知位置时改指针，$O(1)$
适合场景	频繁读取、很少插删	频繁插删、规模变化大

为什么会被替代或组合使用

顺序表没有被链表“淘汰”，链表也没有替代顺序表。二者服务于不同瓶颈：

需求变化	更合适的结构	原因
CPU 缓存友好、随机访问多	顺序表	连续内存访问快
频繁在中间插入删除	链表	不需要大规模移动元素
既要随机访问又要动态扩容	动态数组	牺牲偶发扩容成本换整体效率
需要稳定引用和频繁节点调整	链表	节点位置不随移动改变

本节例题

单选

单链表中，已知 `p` 为待删除节点 `q` 的前驱，删除 `q` 的关键指针修改是：

Ap = q->nextBq->next = pCp->next = q->nextDq = p->next

自查清单

1. 能否解释顺序表为什么能随机访问？
2. 能否写出单链表插入节点时两条语句的正确顺序？
3. 能否说明双链表删除为什么需要修改两个方向的指针？
4. 能否根据“查找多”或“插删多”选择合适结构？