线性表是由有限个同类型元素组成的有序序列。除首尾元素外，每个元素都有唯一前驱和唯一后继。数组、链表、栈和队列都与这种线性关系密切相关。
学习目标
完成本章后，你应该能够：
- 用 ADT 描述线性表的数据对象和基本操作；
- 解释顺序存储与链式存储的核心差异；
- 实现查找、插入、删除和遍历的基本版本；
- 分析主要操作的时间与空间复杂度；
- 根据访问模式选择合适的实现。
核心概念
- 逻辑结构：元素之间呈一对一的线性关系。
- 顺序存储：元素存放在连续空间，通过下标定位。
- 链式存储：节点可分散存放，通过链接域表达关系。
- 操作契约：每个操作都应说明输入、结果、边界与失败方式。
两种实现的复杂度概览
以下结论以常见动态顺序表和已知头节点的单链表为例：
| 操作 | 顺序表 | 单链表 |
|---|---|---|
| 按下标访问 | O(1) | O(n) |
| 按值查找 | O(n) | O(n) |
| 表头插入/删除 | O(n) | O(1) |
| 已知节点后的插入 | 不适用 | O(1) |
| 表尾追加 | 摊还 O(1) | O(n)，维护尾指针可为 O(1) |
复杂度不是唯一标准。缓存局部性、额外指针空间、扩容策略和接口语义同样会影响选择。
本章内容
建议先用前两篇冻结操作契约并理解连续存储，再沿第 3 篇观察链表从裸节点到双向循环哨兵的演进，用第 4 篇的决策表完成选型，在第 5 篇把结论连接到标准库与工程约束，最后用第 6 篇把数组中的下标、双指针和元素搬移迁移为链表中的游标、不变量与节点重连。
配套 Project Lab
- Lab 01-P-01：线性表双实现与工作负载评测器：在同一套
IntList契约下实现动态顺序表与双向循环链表，用可复现工作负载比较元素搬移、节点跳转、扩容、链接改写、空间估算和实际耗时。
建议在完成 1.4「比较与权衡」后进入该项目。Project 会把本章的 ADT、边界语义、复杂度、不变量和工程选型串成一个闭环；其余选择题与单点编码 Lab 可从侧栏按需选做。
章节小结
线性表先定义“能做什么”，再选择“如何存”。顺序表擅长随机访问，链表擅长在已知位置附近修改结构；具体方案应由操作频率和约束决定。
练习
- 为通讯录设计一组最小线性表操作。
- 为什么“链表插入一定是
O(1)”不够准确？ - 如果读取远多于插入删除，你会优先考虑哪种存储方式？为什么？
- 设计三个可以暴露越界错误的测试用例。