第3章现象表：比较顺序表和链表
3.7 比较顺序表和链表
顺序表和链表都是表示线性表的存储结构，本节从不同角度对二者进行比较。
1. 存储结构
- 顺序表存储结构
#define MAXSIZE 100
typedef struct{ElemType *elem; //存储空间的基地址int length; //当前长度
}SqList; //顺序表的结构类型为 SqList
- 单链表存储结构
typedef struct LNode{ElemType data; //结点的数据域struct LNode * next; //结点的指针域
}LNode, *LinkList; //LinkList 为指向结构体 LNode 的指针类型
- 双向链表存储结构
typedef struct DuLNode{ElemType data; //数据域struct DuLNode *prior; //直接前驱struct DuLNode *next; //直接后继
}DuLNode, *DuLinkList;
2. 空间性能比较
（1）存储空间的分配
-
顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象
-
链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。
当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。
（2）存储密度的大小
-
存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即：
存储密度=数据元素本身占用的存储量结点结构占用的存储量 \text{存储密度}=\frac{\text{数据元素本身占用的存储量}}{\text{结点结构占用的存储量}} 存储密度=结点结构占用的存储量数据元素本身占用的存储量
存储密度越大，存储空间的利用率就越高。 -
链表的每个结点除了设置数据域用来存储数据元素之外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针。
-
顺序表的存储密度为 1（不考虑顺序表的空闲区）。
-
链表的存储密度小于 1。例如单链表，若结点的数据为整数，指针所占用的空间和整型量相同，则单链表的存储密度为 0.5 。
当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
| 角度 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续内存空间 | 离散内存空间（节点通过指针连接） |
| 存储密度 | 高（仅存储数据） | 低（需额外存储指针） |
| 动态扩容 | 需重新分配内存（可能复制数据） | 动态申请节点，无需整体扩容 |
3. 时间性能比较
（1）存取元素的效率
-
顺序表是用数组实现的，它是一种随机存取结构，指定任意一个位置序号 iii ，都可以在 O(1)O(1)O(1) 时间内直接存取该位置上的元素，即取值操作的效率高。
-
链表是一种顺序存取结构，按位置访问链表中第 iii 个元素时，只能从表头开始依次向后遍历链表，直到找到第 iii 个位置上的元素，时间复杂度为 O(n)O(n)O(n) ，即取值操作的效率低。
若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时宜采用顺序表作为存储结构。
| 角度 | 顺序表 | 链表 |
|---|---|---|
| 随机访问 | O(1)O(1)O(1)（直接通过下标访问） | O(n)O(n)O(n)（需从头遍历） |
| 顺序访问 | O(n)O(n)O(n) | O(n)O(n)O(n) |
（2）插入和删除操作的效率
- 对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为 O(1)O(1)O(1)。
- 对于顺序表，进行插入或删除时，需要移动表中的结点，时间复杂度为 O(n)O(n)O(n)。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。
对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。
| 角度 | 顺序表 | 链表 |
|---|---|---|
| 头部插入/删除 | O(n)O(n)O(n)（需移动所有元素） | O(1)O(1)O(1)（修改指针） |
| 尾部插入/删除 | O(1)O(1)O(1)（若空间足够） | O(1)O(1)O(1)（需维护尾指针） |
| 中间插入/删除 | O(n)O(n)O(n)（需移动部分元素） | O(n)O(n)O(n)（需先遍历到位置） |
4. 适用场景
| 场景 | 顺序表 | 链表 |
|---|---|---|
| 频繁查询 | ✔️（随机访问快） | ❌（需遍历） |
| 频繁增删 | ❌（移动元素开销大） | ✔️（指针修改快） |
| 数据规模固定 | ✔️（无需扩容） | ❌（指针额外开销） |
| 数据规模变化大 | ❌（扩容成本高） | ✔️（动态增长） |
| 缓存友好性 | ✔️（局部性好） | ❌（指针跳转不连续） |
说明：
- 顺序表适用：
- 数据量固定或变化小。
- 需要高效随机访问（如数组、矩阵运算）。
- 链表适用：
- 数据频繁增删（如队列、栈、动态列表）。
- 数据规模变化大（如内存池管理）。