顺序表与动态数组：最常见的线性表起点

如果说线性结构是很多数据结构学习的起点，那么顺序表几乎就是这个起点里的“第一站”。因为它背后的思路既直观又高频：把一组逻辑上有先后顺序的元素，按照连续的存储位置放在一起。你平时在大多数编程语言里最早接触到的数组、列表，本质上很多都和顺序表这类思想直接相关。

顺序表之所以重要，不只是因为它简单，而是因为它把很多后续都会反复出现的概念都提前暴露了出来：连续存储、随机访问、插入删除的搬移代价、容量限制、扩容策略、时间换空间与均摊分析。这些东西一旦在顺序表里理解透，后面学链表、栈、队列、堆甚至哈希表底层实现时，都会更容易建立比较视角。

从抽象数据类型的角度看，顺序表可以理解成线性表的一种典型实现方式；从工程视角看，动态数组又是顺序表在现代编程语言和运行时里最常见、最实用的落地形态。所以这一篇会把两件事一起讲清楚：什么是顺序表，以及为什么动态数组会成为现实世界里最常见的选择。

一、什么是顺序表

顺序表可以先用一句很直白的话理解：

用一段连续的存储空间，按顺序保存一组线性关系的数据元素。

这里有两个关键词非常重要。

1. 线性关系

也就是元素之间是一对一的前后关系。

例如：

第一个元素后面是第二个元素；
第二个元素前面是第一个，后面是第三个；
除了首尾元素，中间元素通常都同时有前驱和后继。

这种“排成一列”的逻辑关系，就是线性表最核心的特征。

2. 连续存储

顺序表和很多其他结构的最大区别之一，就是它要求元素在内存中按连续位置存放。

这意味着：

第一个元素在某个起始地址；
第二个元素紧挨着第一个；
第 i 个元素的位置通常可以由起始地址加偏移量直接算出来。

也正因为如此，顺序表天然具备一个非常强的能力：随机访问。

二、为什么顺序表访问会很快

顺序表最典型的优势，就是可以根据下标直接定位元素。

例如，一个整型数组里每个元素占固定字节数，如果知道：

起始地址；
每个元素的大小；
下标 i；

那么第 i 个元素的位置就能直接算出来。

这意味着访问某个位置的元素，不需要从头一个个找过去，而是可以一步定位。这也是为什么顺序表按下标访问通常是 O(1)。

这种能力在很多场景里都非常重要：

根据下标快速读写；
二分查找依赖随机访问能力；
排序算法里频繁交换和比较元素时，顺序存储也很自然；
需要高局部性访问时，连续内存通常对缓存也更友好。

所以顺序表的第一大优势，可以概括成一句话：

想按位置快速访问元素时，顺序表通常是最自然、最高效的选择。

三、顺序表通常支持哪些操作

如果从线性表 ADT 的角度看，顺序表通常需要支持这些基本操作：

获取指定位置元素；
修改指定位置元素；
在某个位置插入新元素；
删除某个位置元素；
查找某个值是否存在；
获取当前长度；
判断是否为空。

这些操作从逻辑上看都不复杂，但一旦落到连续存储上，它们的代价会很不一样。

这也是学顺序表真正关键的地方：

有些操作特别适合它；
有些操作虽然也能做，但代价明显更高。

四、顺序表的核心优势在哪里

1. 随机访问快

这是顺序表最核心的优势。按下标访问元素通常是 O(1)。

2. 存储开销相对紧凑

因为元素是连续排列的，不像链表那样每个节点还要额外存指针，所以在很多情况下，顺序表会更节省结构性开销。

3. 更适合 CPU 缓存友好访问

连续内存通常有更好的局部性。遍历顺序表时，硬件缓存往往能更高效地预取相邻元素。这是它在工程里很重要、但初学时不一定马上意识到的一个优势。

4. 很适合实现很多常见算法

例如：

二分查找；
归并排序、快速排序中的数组操作；
双指针问题；
前缀和、差分等结构的底层容器。

所以顺序表不只是“一个基础结构”，它实际上是很多高频算法问题的天然承载体。

五、顺序表的核心劣势在哪里

顺序表的优势非常明显，但它也不是全能结构。

1. 中间插入可能很贵

如果要在中间位置插入一个元素，为了保证连续性，插入位置之后的所有元素都可能需要整体后移。

例如在第 k 个位置插入：

第 k 到末尾的元素都要往后挪；
元素越多，搬移成本越高。

所以中间插入的时间复杂度通常是 O(n)。

2. 中间删除也可能很贵

删除一个元素后，为了补齐空位，后面的元素通常也要整体前移，因此中间删除通常也是 O(n)。

3. 固定容量时不够灵活

如果用静态数组实现顺序表，就会遇到一个问题：

预留太小，装不下；
预留太大，又可能浪费空间。

4. 必须依赖连续空间

连续存储虽然带来了随机访问优势，但也带来了一个前提：要能申请到足够大的连续内存。这在更底层的系统场景里并不总是轻松的事。

所以顺序表的局限可以概括为：

访问很快，但结构调整代价不低；读写位置友好，但增删中间元素不够灵活。

六、静态顺序表和动态数组有什么区别

这两个概念很容易混在一起，但它们并不完全一样。

1. 静态顺序表

静态顺序表通常指：

一开始就分配固定容量；
长度可以变化，但不能超过容量上限；
如果满了，通常就无法继续插入。

这类实现适合教学和一些容量明确的场景，因为它简单、直观，也方便理解顺序表最基础的结构特征。

2. 动态数组

动态数组可以理解成：

对外仍然像顺序表一样按下标访问；
但内部支持容量自动扩展；
当空间不够时，会申请更大的连续空间并搬迁数据。

也就是说，动态数组本质上仍然是顺序存储，只不过比静态顺序表多了一层“自动扩容能力”。

这也是为什么现实开发里你更常见到动态数组，而不是手工管理固定长度数组。

七、动态数组为什么这么常见

因为它很好地平衡了两件事：

保留了顺序表按下标访问快、遍历方便的优势；
缓解了固定容量太死板的问题。

你可以把动态数组理解成一种“现实感更强的顺序表”。它的典型特点是：

平时像普通数组一样使用；
需要时自动长大；
大多数追加操作都很便宜；
偶尔扩容时会比较贵。

这就是前面复杂度分析里讲过的均摊分析会再次出现的地方。

八、动态数组的扩容过程大致是怎样的

一个典型的动态数组通常会维护两个核心量：

当前元素个数 size；
当前容量 capacity。

当执行尾部插入时，大致逻辑通常是：

1. 如果还有空位

直接把新元素放到末尾，size 加一。

2. 如果容量已满

就要：

申请一块更大的连续空间；
把旧元素复制过去；
释放旧空间；
再插入新元素。

很多实现会采用“按倍数扩容”的策略，例如扩成原来的 2 倍。这样做的目的是减少频繁扩容的次数。

如果每次只多扩一个位置，那几乎每插一个新元素都可能触发搬迁，代价会非常糟糕；但如果按倍数扩容，虽然某次扩容会比较贵，长期看每次尾插的均摊成本通常仍然是 O(1)。

九、顺序表各类操作的复杂度应该怎么理解

如果不考虑扩容，顺序表里最常见操作的复杂度通常可以这样理解：

1. 按下标访问：`O(1)`

因为可以直接通过偏移量计算位置。

2. 尾部追加

静态顺序表有空间时通常是 O(1)；
动态数组从均摊意义上通常也是 O(1)。

3. 中间插入：`O(n)`

因为可能需要搬移后续元素。

4. 中间删除：`O(n)`

因为可能需要整体前移。

5. 按值查找：`O(n)`

如果没有额外索引，通常需要顺序扫描。

所以学顺序表时一定要建立一个清晰认识：

它快的是“按位置访问”，不是“所有操作都快”。

这点非常重要，因为后面比较顺序表和链表、哈希表、树时，本质上都是在比较不同操作的复杂度侧重点。

十、顺序表为什么适合作为线性结构的第一站

因为它几乎把很多基础概念一次性串了起来。

1. 它让你第一次真正比较“访问”和“修改”的代价差异

按下标访问很快，不代表插入删除也快。

2. 它让你开始理解“存储方式决定操作代价”

连续存储带来的是直接定位能力，同时也带来了结构调整成本。

3. 它让你看到复杂度分析不是抽象空话

O(1) 访问、O(n) 插入删除、扩容均摊 O(1)，这些复杂度都能在顺序表里很直观地感受到。

4. 它和现实语言容器联系非常紧密

很多语言里的列表、切片、动态数组类容器，背后都和顺序存储思想高度相关。你学完顺序表后，再看这些语言特性会更容易建立底层理解。

十一、顺序表在真实开发里常出现在哪里

虽然教材里的“顺序表”这个词看起来有点偏理论，但它在工程里其实非常常见。

例如：

编程语言里的数组、动态数组、切片类容器；
需要高频按下标访问的数据集合；
排序和查找算法的基础容器；
实现栈、堆、优先队列时的底层结构；
大量需要紧凑存储、顺序遍历的场景。

也就是说，顺序表不是“只存在于课本”的结构，而是很多现代编程实践里最常见的底层思路之一。

十二、学习顺序表时最容易踩的坑

1. 以为数组访问快，所以任何操作都快

这是一种很常见的误解。随机访问快，不等于中间增删也快。

2. 混淆“容量”和“长度”

尤其在动态数组里，capacity 和 size 往往不是一回事。容量表示最多能放多少，长度表示当前已经放了多少。

3. 忽略扩容成本

平时尾插看起来很便宜，但扩容时可能会一次性复制很多元素，所以要理解均摊分析，而不是只看单次最坏情况。

4. 忽略连续内存带来的限制

连续存储不是只有好处，它同时要求空间连续、插入删除搬移明显。

5. 不从“使用场景”看结构选择

结构没有绝对好坏，关键是看你的主要操作是什么。如果主要是随机访问和尾部追加，顺序表非常强；如果主要是频繁中间插入删除，它就未必最合适。

十三、顺序表和后面链表最大的对比点是什么

这一点你现在就可以先有一个预告式理解。

顺序表和链表后面之所以会成为一组经典对比，就是因为它们体现了两种不同的设计取舍：

顺序表强调连续存储和快速随机访问；
链表强调结构灵活和局部插入删除方便。

换句话说，后面学链表时，你会看到一个非常典型的对照组：

一个更适合查位置；
一个更适合调结构。

这种对比视角，正是数据结构学习最核心的收获之一。

总结

顺序表和动态数组的重要性，不只是因为它们常见，而是因为它们把线性结构里最基础、最核心的一组取舍非常清楚地展示了出来。真正值得先建立起来的，是这些核心认识：

顺序表是线性表的一种典型实现方式，核心特征是连续存储；
连续存储带来了按下标随机访问快的优势，通常是 O(1)；
中间插入和删除通常需要整体搬移元素，因此代价往往是 O(n)；
静态顺序表容量固定，而动态数组在顺序存储基础上增加了自动扩容能力；
动态数组的尾部追加在均摊意义上通常是 O(1)，这和扩容策略密切相关；
真正学会顺序表，不是只会写一段数组代码，而是能理解“连续存储带来了什么，又牺牲了什么”。

把这一篇理解透之后，后面再去学链表时，你会更容易看清楚两种结构之间最本质的差异：一个用连续空间换快速访问，一个用分散节点换结构灵活。而这种“没有绝对最好，只有取舍不同”的认识，正是数据结构学习真正开始深入的地方。

参考资源：