01. 线性表
顺序表：元素地址连续，支持随机访问
线性表是数据结构中最基础、最常用的结构之一，理解它有助于后续学习栈、队列、字符串等内容。
1. 基本概念
- 线性表：具有相同数据类型的 n 个数据元素的有限序列
- 特点：有唯一的第一个元素和最后一个元素，除首尾外每个元素有且仅有一个前驱和一个后继
2. 存储结构对比
| 存储方式 | 地址连续 | 支持随机访问 | 插入/删除效率 | 空间利用率 |
|---|---|---|---|---|
| 顺序表 | 是 | 是 | 低 | 低 |
| 链表 | 否 | 否 | 高 | 高 |
- 顺序表：用一组地址连续的存储单元依次存放线性表元素
- 链表：每个结点包含数据域和指针域，通过指针连接
3. 动画演示
顺序表：元素地址连续，支持随机访问
4. 易错点小贴士
顺序表插入/删除时，需整体移动元素，链表则只需修改指针，易混淆！
5. 线性表的典型应用
- 作为栈、队列、字符串等数据结构的基础
- 任务队列、浏览历史、购物车、文本编辑器的撤销/重做等
| 应用场景 | 推荐结构 |
|---|---|
| 需要频繁随机访问 | 顺序表 |
| 需要频繁插入删除 | 链表 |
练习题
- 简述线性表的定义和主要特点。
- 顺序表和链表各自的优缺点是什么？
- 单链表插入和删除操作的基本思想是什么？
- 如何实现线性表的遍历？
- 线性表有哪些典型应用？
参考答案
1. 定义与特点
线性表是 n 个数据元素的有序序列，有唯一首尾，元素一对一关系
2. 顺序表与链表优缺点
顺序表：查找快，插入/删除慢，空间利用率低；链表：插入/删除快，查找慢，空间利用率高
3. 单链表插入/删除
插入：新结点指向后继，前驱指向新结点；删除：前驱指向被删结点的后继
4. 遍历实现
顺序表：下标循环；链表：指针逐结点访问
5. 典型应用
栈、队列、字符串、查找、排序、合并等