Appearance
顺序表（数组）
为什么需要顺序表
顺序表是最基础的线性数据结构。它用一段连续的存储空间来存放数据元素，通过下标可以直接访问任意位置的元素。
在日常编程中，数组就是顺序表的典型实现。理解顺序表的底层原理，是掌握后续所有复杂数据结构的基础。408 考研中，顺序表是线性表章节的起点，也是理解链表优缺点的参照物。
核心思想
顺序表的核心特点：
- 逻辑顺序与物理顺序一致：第 i 个元素存储在第 i 个物理位置
- 随机访问：通过起始地址 + 偏移量，O(1) 时间访问任意元素
- 静态分配 vs 动态分配：静态数组大小固定，动态数组可扩容（但需要复制数据）
数据元素在内存中的存储方式：
地址: LOC(a₁) LOC(a₁)+d LOC(a₁)+2d ... LOC(a₁)+(n-1)d
元素: a₁ a₂ a₃ ... aₙ其中 d 是每个元素占用的存储空间大小。
插入操作流程图
交互可视化
通过下方的交互动画，你可以逐步观察顺序表各操作的执行过程：
操作详解
插入操作
在位置 i 插入新元素时，需要将第 i 个及之后的所有元素依次后移一位，腾出位置。
关键步骤：
- 判断插入位置是否合法（1 ≤ i ≤ n+1）
- 判断存储空间是否已满
- 从最后一个元素开始，依次后移到第 i 个元素
- 将新元素放入位置 i
- 表长加 1
删除操作
删除位置 i 的元素时，需要将第 i+1 个及之后的所有元素依次前移一位，填补空位。
关键步骤：
- 判断删除位置是否合法（1 ≤ i ≤ n）
- 取出被删除的元素（可能需要返回）
- 从第 i+1 个元素开始，依次前移
- 表长减 1
按值查找
从第一个元素开始，逐个比较，直到找到目标值或遍历完整个表。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按位查找 | O(1) | 随机访问，直接计算地址 |
| 按值查找 | O(n) | 最坏需遍历整个表 |
| 插入 | O(n) | 平均移动 n/2 个元素 |
| 删除 | O(n) | 平均移动 (n-1)/2 个元素 |
空间复杂度：O(1)，插入和删除操作只需常数级辅助空间。
考研高频考点
- ⭐ 插入和删除的平均移动次数计算（选择题/填空题高频）
- ⭐ 顺序表 vs 链表的优缺点对比（简答题必考）
- ⭐ 随机访问特性及其原因（概念题）
- 动态扩容的时间开销分析（偶尔考）
- 顺序表的存储密度（= 1，对比链表）