Lecture 6：顺序表和链表对比

6.1 存储结构对比

共同点

• 顺序表和链表在逻辑结构上都是线性结构。
• 它们都表示数据元素之间的一对一前后关系。
• 区别主要在存储结构：
  • 顺序表：顺序存储；
  • 链表：链式存储。

6.1.1 顺序表

定义：#顺序表

描述： 顺序表用一组物理地址连续的存储单元依次存储线性表中的数据元素。

优点

• 支持随机存取。
• 存储密度高。
• 按位查找效率高： $$ O(1) $$

缺点

• 需要大片连续空间。
• 分配空间不方便。
• 改变容量不方便。
• 插入、删除需要移动大量元素。

6.1.2 链表

定义：#链表

描述： 链表用指针表示元素之间的逻辑关系，结点在物理存储中不要求连续。

优点

• 离散的小空间分配方便。
• 改变容量方便。
• 定位到操作位置后，插入主要修改链接；删除还要释放被删结点，且单链表通常需要其前驱结点。

缺点

• 不支持随机存取。
• 需要额外指针空间。
• 存储密度低。

6.2 基本操作对比

6.2.1 创建

顺序表

• 需要预先分配大片连续空间。
• 如果分配空间过小，之后扩展容量不方便。
• 如果分配空间过大，会浪费内存资源。

链表

• 只需要先分配一个头结点。
• 也可以不要头结点，只声明一个头指针。
• 之后需要多少结点，就申请多少结点，扩展更方便。

对比

6.2.2 销毁

顺序表

• 如果使用静态数组，空间由系统自动回收。
• 如果使用动态分配数组，需要手动释放：

free(L.data);

链表

• 链表中每个结点通常是单独申请的。
• 销毁时需要依次释放每个结点：

free(p);

对比

6.2.3 增加和删除

顺序表

• 插入元素时，需要将插入位置及其之后的元素后移。
• 删除元素时，需要将删除位置之后的元素前移。
• 时间复杂度： $$ O(n) $$
• 时间开销主要来自移动元素。
• 如果数据元素很大，移动元素的时间代价会更高。

链表

• 插入在已知前驱结点后可通过链接调整完成；删除单链表结点通常还需已知其前驱并释放被删结点。
• 如果不知道操作位置，仍需先查找目标结点或其前驱结点。
• 时间复杂度通常也是： $$ O(n) $$
• 时间开销主要来自查找目标元素。

重要区别

• 顺序表的 $O(n)$ 主要花在“移动元素”。
• 链表的 $O(n)$ 主要花在“查找位置”。
• 对单链表，已知插入位置的前驱，或已知待删结点的前驱时，链接调整可在常数时间完成；仅知道待删结点而不知道前驱时，不能无条件断言删除为 $O(1)$： $$ O(1) $$

6.2.4 查找

顺序表

• 按位查找： $$ O(1) $$
• 按值查找： $$ O(n) $$
• 若表内元素有序，可以使用折半查找： $$ O(\log_2 n) $$

链表

• 按位查找需要从头结点开始遍历： $$ O(n) $$
• 按值查找也需要遍历： $$ O(n) $$
• 链表不能直接使用折半查找。
  • 因为折半查找要求能快速访问中间位置；
  • 链表无法 $O(1)$ 访问第 $i$ 个元素。

6.3 综合对比表

6.4 选择顺序表还是链表

题型：#顺序表链表选择

第一部分：解题方法

• 如果题目强调“按位访问、随机访问、查找第 $i$ 个元素”，优先考虑顺序表。
• 如果题目强调“频繁插入删除、容量变化大、不要求连续空间”，优先考虑链表。
• 如果题目强调“内存利用率、存储密度”，顺序表更优。
• 如果题目强调“动态扩展”，链表更优。

第二部分：典型例题

例题 1：需要频繁访问第 $i$ 个元素

• 选择顺序表。
• 原因： $$ \text{顺序表按位查找}=O(1) $$

例题 2：需要频繁在表中间插入删除

• 若已知插入删除位置的前驱结点，选择链表更合适。
• 原因： $$ \text{链表修改指针}=O(1) $$

例题 3：表长变化很大

• 选择链表。
• 原因：
  • 不要求连续空间；
  • 扩容方便。

第三部分：知识点复盘

• 顺序表不是所有操作都快，它主要快在随机访问。
• 链表不是所有插入删除都快，若要先查找位置，整体仍可能是 $O(n)$。
• 判断结构优劣时，一定要结合操作场景。

教材补充：线性表的典型应用

NOTE · 补充说明 “线性表的应用”不等于再背一种存储结构，重点是根据输入有序性、能否修改原表、是否允许额外空间，选择顺序表或链表并证明复杂度。

有序表合并与集合运算

设两个非递减表长度分别为 $m,n$：

• 合并为一个非递减表：双指针各扫描一次，时间 $O(m+n)$。顺序表通常需要 $O(m+n)$ 的结果空间；链表若允许破坏原表，可复用原结点，仅需 $O(1)$ 个辅助指针。
• 求交集：关键字相等时输出并同时前进；较小的一侧前进。若要求集合语义，还要跳过相等关键字的重复项。
• 求并集：较小者输出并前进，相等时只输出一次并同时前进；若题目按多重集合处理，则重复次数规则必须由题干确定。
• 求差集 $A-B$：当 $A[i]<B[j]$ 时保留 $A[i]$；相等时丢弃 $A[i]$；当 $A[i]>B[j]$ 时只移动 $B$。

这些线性算法成立的关键是两个输入已按同一关键字顺序排列。若输入无序，直接双指针会漏解；需先排序、使用散列表，或采用朴素的嵌套查找。

删除、筛选、去重与逆置

代码题必须先写清的边界

1. 表是否带头结点；L 指向头结点还是首元结点。
2. 位序采用 $1$ 开始，还是数组下标采用 $0$ 开始。
3. 是否允许修改、销毁或复用输入表；这直接决定能否原地算法。
4. 相等关键字按集合、多重集合还是稳定保留处理。
5. 顺序表结果是否有足够容量；链表删除后是否必须释放结点。
6. 空表、单元素表、全部删除、一个也不删除以及 $k$ 越界是否被正确处理。

完整可运行模板见顺序表代码与链表代码。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：线性表的链式实现 · 下一篇：栈基本概念
• 关联专题：顺序表代码

6.5 本节复盘

必须掌握

• 顺序表和链表逻辑结构相同，存储结构不同。
• 顺序表支持随机存取，链表不支持。
• 顺序表存储密度高，链表存储密度低。
• 顺序表插入删除通常移动元素；链表定位后主要调整链接，删除结点还需按其内存管理方式回收。
• 链表容量扩展方便，顺序表容量扩展不方便。

易错点

• 链表插入删除不是无条件 $O(1)$。
  • 对单链表，已知插入位置的前驱、或待删结点的前驱时，链接调整是 $O(1)$；
  • 若需要先查找位置，总体仍是 $O(n)$。
• 顺序表按值查找一般是 $O(n)$，只有有序时才可以考虑折半查找。
• 链表即使有序，也不能直接高效折半查找。

一句话总结

• 查找多、少增删 -> 顺序表。
• 增删多、容量变化大 -> 链表。