主题
第二章 线性表、顺序表与链表
📖 ⏱️ 预计阅读时长 1 分钟 👑 会员专属
1. 线性表的基本思想
线性表是最基本、最常见的数据结构之一。它由有限个数据元素组成，除第一个元素外，每个元素都有唯一前驱；除最后一个元素外，每个元素都有唯一后继。
线性表强调的是“逻辑关系”，而顺序表和链表强调的是“实现方式”。因此，顺序表和链表都可以看作线性表的不同存储实现。
在线性表中，最典型的操作包括按位置访问、查找元素、插入元素和删除元素。正是这几类操作的代价差异，使得顺序表和链表形成了不同的使用场景。
2. 顺序表与数组
顺序表通常用一段地址连续的存储空间保存元素。在程序设计中，数组是顺序表最常见的实现形式。
2.1 主要特点
- 支持按下标随机访问，访问第
i个元素通常为O(1)。 - 存储密度高，不需要为指针额外分配空间。
- 中间位置插入或删除元素时，往往需要整体移动后续元素。
之所以能够实现按下标 O(1) 访问，是因为顺序表采用连续存储。对于长度固定的同类型元素，只要知道起始地址和每个元素所占字节数，就可以通过“起始地址 + 下标偏移”直接定位目标元素。这一性质是数组访问速度快的根本原因，而不是因为数组“语法更简单”。
2.2 适用场景
顺序表适合以下情况：
- 需要频繁按位置访问元素。
- 数据规模相对稳定，或者插入删除不频繁。
- 元素类型统一，适合连续存储。
2.3 时间复杂度
| 操作 | 顺序表复杂度 | 说明 |
|---|---|---|
| 随机访问 | O(1) | 直接通过下标定位 |
| 顺序查找 | O(n) | 无附加信息时需逐个比较 |
| 末尾插入 | O(1) 或摊还 O(1) | 动态数组扩容时需重新分配 |
| 中间插入 | O(n) | 需要移动元素 |
| 删除 | O(n) | 需要前移元素填补空位 |
2.4 优缺点分析
顺序表最大的优点是访问快、结构简单；最大的缺点是扩容与插入删除成本较高。因此，顺序表通常适用于“查得多、改得少”的情形。
在现代编程语言中，很多“动态数组”容器本质上仍属于顺序表，只是语言运行库自动帮我们处理扩容和容量管理问题。理解这一点，有助于认识到高级容器并没有改变数据结构本质，只是改善了使用方式。
还应进一步理解一个常被忽略的问题：为什么顺序表在工程实践中如此常见。除了理论上的随机访问优势之外，顺序表还具有很好的缓存局部性。也就是说，连续数据在 CPU 读取时更容易被一并加载到缓存中，因此在真实程序里，顺序表往往比理论复杂度相近的其他结构具有更好的实际性能。
上图可以把顺序表理解为一串连续的存储单元。正因为物理位置连续，所以才能通过“起始地址 + 偏移量”快速定位任意元素。
3. 链表
链表通过节点记录元素值和逻辑关系。节点在内存中不必连续，通过指针把这些节点连接起来。
3.1 单链表
单链表中的每个节点通常包含两部分：数据域和指针域。指针域指向下一个节点。
其优点在于：
- 插入删除灵活，不必整体移动元素。
- 不要求物理地址连续，适合动态申请空间。
其缺点在于：
- 不能像数组一样通过下标直接访问。
- 需要额外指针空间。
- 查找某个位置时通常仍需从头遍历。
链表之所以能在插入和删除上表现灵活，根本原因在于它不依赖元素在内存中的物理位置，而只依赖节点之间的逻辑连接关系。换言之，链表的“顺序”不是由地址决定的，而是由指针决定的。这一点与顺序表形成鲜明对比。
单链表的关键不在于节点里存了什么数据，而在于每个节点都知道“下一个节点在哪里”。链表的逻辑顺序因此不再依赖物理连续地址，而依赖指针指向关系。
3.2 双向链表
双向链表在每个节点中同时保存前驱指针和后继指针，因此可以向前或向后遍历，适合需要双向访问的场景，例如浏览器历史记录、LRU 缓存链等。
3.3 循环链表
循环链表使尾节点重新指向头节点，因此整体形成环状结构。它适合解决循环调度、约瑟夫问题等需要“首尾相接”处理的问题。
3.4 链表时间复杂度
| 操作 | 链表复杂度 | 说明 |
|---|---|---|
| 按位置访问 | O(n) | 需要沿指针逐步遍历 |
| 查找元素 | O(n) | 无序条件下通常线性查找 |
| 已知节点后插入 | O(1) | 修改少量指针即可 |
| 已知前驱后删除 | O(1) | 单链表需知道前驱节点 |
这里必须特别强调“已知前驱”这个条件。很多学生记住了链表插入删除快，却忽略了为了找到插入或删除位置，本身可能需要一次从头遍历。也正因此，链表并不是在所有增删场景下都比顺序表更好，而是更适合那些“目标位置已知”或“头尾操作频繁”的问题。
需要特别指出的是，“链表插入快”这一说法必须附带前提。若插入前必须先从头找到插入位置，则查找过程本身已经可能是 O(n)。因此，不能机械地认为链表在任何场景下都比数组更适合插入。
4. C 语言示例：单链表头插与遍历
c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *create_node(int value) {
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return NULL;
}
node->data = value;
node->next = NULL;
return node;
}
void push_front(Node **head, int value) {
Node *node = create_node(value);
if (node == NULL) {
return;
}
node->next = *head;
*head = node;
}
void print_list(Node *head) {
Node *cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main(void) {
Node *head = NULL;
push_front(&head, 30);
push_front(&head, 20);
push_front(&head, 10);
print_list(head); /* 输出：10 20 30 */
return 0;
}这个示例体现了链表最重要的特征：新增节点时不必整体搬移已有元素，只需修改有限个指针即可。
5. 顺序表与链表的比较
5.1 从访问角度看
顺序表最大的优势是随机访问。只要知道下标，就可以直接定位元素位置。链表则必须从头节点沿指针逐个走到目标位置。
5.2 从插入删除角度看
若在表中间插入或删除，顺序表通常需要整体搬移元素；链表只需要修改少量指针，因此在已知位置时更加灵活。
5.3 从空间角度看
顺序表额外空间开销小，但可能因为预留容量而造成空闲空间。链表可以按需申请空间，但每个节点都要额外保存指针。
5.4 从缓存友好性角度看
顺序表由于元素连续排列，通常更容易命中 CPU 缓存，因此在很多实际程序中，其性能优势不只是来自理论上的 O(1) 访问，还来自底层存储局部性。链表虽然在逻辑增删上更加灵活，但节点分散在内存中时，缓存命中率往往较低，这也是链表在工程实践中未必总是优于数组的重要原因。
5.5 为什么教材总把二者放在一起讲
这是因为顺序表和链表正好构成了“连续存储”与“链式连接”两种最典型的实现思路。后续很多更复杂的数据结构，其底层思想都可以追溯到这里。例如堆和动态数组本质上延续了顺序存储思想，而树、图、哈希桶链往往延续了链式组织思想。把这两类结构学扎实，后面的内容会更容易理解。
6. 本章小结
线性表是最基础的逻辑结构，而顺序表与链表则是它的两种典型实现。顺序表擅长访问，链表擅长灵活连接；顺序表依赖连续存储，链表依赖指针组织；顺序表在插入删除时可能搬移大量元素，链表则在定位目标时往往需要遍历。真正掌握本章的关键，不是会背定义，而是能根据操作需求判断应使用哪种实现。