线性表
本章是后序内容的基础，可能会涉及到在选择题中的概念考察。除此外，需要能够手写代码实现基于数组或链表的相关操作。
学习思维导图：
## 线性表
### 线性表的基本概念
### 线性表的实现
- 顺序存储
- 链式存储
### 线性表的应用
选表示前先判断操作
线性表的逻辑特征是“除首尾外，每个元素恰有一个直接前驱和一个直接后继”；顺序表和链表只是表达这一关系的两种实现。选择实现时，先看题目最频繁的操作：
| 题目重点 | 更自然的表示 | 原因 |
|---|---|---|
| 按下标随机访问、元素数上界明确 | 顺序表 | 可由首地址和下标在常数时间定位 |
| 已知结点位置后频繁插入、删除 | 链表 | 改变链接即可，无需整体搬移元素 |
| 既要按位置访问又要频繁修改 | 需结合约束分析 | 不能只因“链表插删快”就忽略查找前驱的代价 |
无论采用哪种表示，算法题都要先约定位置编号、是否带头结点以及空表条件。插入和删除的边界分别包括首位置、尾位置、空表和满表；这些条件往往比主流程更容易失分。