顺序表深度解析：从内存布局到扩容策略，一文读懂数组的工程真相

顺序表这个名词，乍一听特别像教科书里才会出现的术语，但它其实就是我们天天在碰的数组——用一段地址连续的存储单元，依次存放线性表的数据元素，让逻辑上相邻的元素在物理上也紧挨着。我之前带过几个刚入行的同学，一说数组谁都点头，可一被问到“为什么顺序表按下标取值是 O(1)”，大多数人张口就卡住；再被问到“头部插入为什么慢”，就开始背“因为要移动元素”，但到底移多少步、往哪个方向移动、扩容为什么是翻倍而不是加一，就说不清楚了。这篇就把顺序表从内存布局、增删代价、扩容策略到工程选型完整拆一遍。它既适合准备面试、想补数据结构基础的人，也适合在业务代码里反复调数组性能但总被复杂度打脸的开发者。

1. 连续存储的意义：顺序表凭什么按下标直达元素

1.1 一个公式讲清楚“随机访问”

顺序表最本质的特征就一句话：所有元素按顺序躺在同一块连续的内存里，并且每个元素占用的字节数固定。

假设一个 int 数组的首地址是base，每个 int 占 4 字节，那么第 i 个元素（从 0 开始算）的地址就是：

addr(i) = base + i * 4

如果算上每个元素的大小size，那就是：

addr(i) = base + i * size

这是一个乘法加一次加法，与表长 n 完全没有关系。不管数组里有 10 个元素还是有 100 万个元素，按下标取第 i 个元素，永远是查一个公式算地址，然后直接去那块内存里把数据读出来。这就是教科书上说的“随机存取”：访问任意位置的时间相同，且与表长无关。

很多新手会把“数组查找快”理解成“数组里有查找算法很快”，这其实是个误区。顺序表随机访问快，靠的不是查找算法，而是地址计算。你要找一个指定下标的值，不需要从头遍历，直接算地址就行。至于“在数组里找一个值等于多少的元素”，那仍然是 O(n) 的线性扫描，除非数组有序之后做二分查找。这两种“查找”的差别，面试里一旦被问就会立刻暴露基本功。

1.2 逻辑关系等于物理关系，这既是收益也是代价

线性表的逻辑结构是：每个元素都有前驱和后继，一个挨着一个。顺序表实现这种“挨着”的方式非常朴素——我在内存里真的让你挨着。元素 e1 前面是 e0，后面是 e2，物理地址上也是 e0 的地址加一单位就找到 e1。

用酒店房间做类比最合适：房间号是连续的，402 旁边一定是 403，你从前台拿到房号，不需要从 400 开始一间一间敲门，直接坐电梯到对应楼层就行。这就是“用物理相邻表达逻辑相邻”的收益。

代价也随之而来：如果队伍里要插进来一个人，后面所有人必须往后退一个位置；如果有人走了，后面所有人又得往前挪一步。顺序表的插入和删除之所以慢，本质就是在维护“物理相邻”这一约束。你想保持大家紧挨着，就必须有人付出移动的代价。

1.3 定长元素的隐含前提：stride 计算能成立的原因

前面那个地址公式有一个隐含前提：每个元素占用的字节数相同。如果元素是 int、double、固定大小结构体，那没问题。但如果元素是变长的，比如不同长度的字符串，直接顺序存储就会出问题——你不知道前一个元素结束后下一个元素从哪开始，地址公式就没法算了。

工程上解决的办法是：数组里存的不再是元素本体，而是指向元素的指针/引用。每个指针都是固定大小，所以地址公式照样成立；真正变长的字符串对象散落在堆的其他位置。Java 的 ArrayList、Python 的 list 底层都是这种“引用数组”的变体。C/C++ 的数组则更“裸”，它直接放元素本体，也因此对元素类型要求苛刻。

这也是理解顺序表的一个关键点：“连续”到底是谁连续，决定了这个数组的行为特征。存元素本体的数组，缓存友好性最好；存指针的数组，虽然指针连续，但指针指向的对象可能东一个西一个，遍历时照样有 cache miss 的风险。后面讲语言实现时，这点会更明显。

2. 增删的账单：移动元素到底要移几次

2.1 三种位置的移动开销

现在来看顺序表最让人头疼的部分：插入和删除。很多人背公式背得很熟，“平均 O(n)”，可真问“平均移动多少次”，就回答不出来了。

假设表长为 n。

尾部插入：直接把新元素放到length位置，length 加一，不需要移动任何现有元素，O(1)。

头部插入：原来所有 n 个元素都得向后挪一格，最坏移动 n 次，O(n)。

中间插入：假设在第 i 个位置（0 ≤ i ≤ n）插入，需要把从下标 i 到 n-1 的 n-i 个元素整体后移。如果每个位置等概率出现，插入位置一共有 n+1 种，移动次数的期望值是：

(0 + 1 + 2 + ... + n) / (n + 1) ≈ n / 2

也就是说，平均插入一次要移动一半的元素，所以平均时间复杂度 O(n)。

删除同理。删除最后一个元素 O(1)；删除头部元素，后面 n-1 个元素全部前移，O(n)；删除中间某个位置，平均移动(n - 1) / 2次。

这里我想特别强调一句：顺序表插入删除的慢，慢在“移动”这个动作本身，而不是在“找位置”上。你能直接算出要插入的下标，地址就在那，但插入之后所有后续元素都不敢原地不动，必须给新人腾地方。相比之下，链表插入不需要移动任何现有节点，但是要先从头遍历找到前驱节点，这个找的过程也是 O(n)。两种结构默认慢的点完全不同。

2.2 移动方向决定成败：为什么后移必须从尾部开始

很多人写代码时忽略一个细节：批量移动元素，方向搞反了就直接出事。

头部插入一个元素时，要把现有元素整体后移。正确做法是从最后一个元素开始，逐个向后复制：

for (int j = length; j > pos; j--) { arr[j] = arr[j - 1]; } arr[pos] = newValue; length++;

为什么必须从后往前？因为如果从前往后移动，arr[j] = arr[j-1]会先把arr[j-1]的值覆盖到arr[j]，接着下一步又把arr[j]里已经被覆盖过的旧值继续往后传，结果整片数据全部被同一个值污染，移动还没完成，原始数据就丢了。

删除元素时往前提数据，方向正好反过来，必须从被删除位置的后一个元素开始，逐个往前复制：

for (int j = pos; j < length - 1; j++) { arr[j] = arr[j + 1]; } length--;

这个方向反了同样会出问题。这些看起来是“抄都抄得对”的代码，但我在代码评审里真的见过有人把后移写成从前往后，然后 debug 了一下午。

在 C/C++ 里，如果移动的是几千个元素的数组，逐元素 for 循环其实很浪费，用memmove一次性搬一整块内存要快得多。注意这里必须用memmove而不是memcpy：memcpy不保证源和目的区域重叠时的行为，而插入删除导致的移动，源和目的天然就是重叠的。memmove会自己判断并选择安全的复制方向，这是标准库函数存在的意义。

2.3 批量删除的一个实用技巧：倒着删

做数据清洗时经常要“过滤掉满足条件的元素”。最笨的写法是正着遍历、遇到符合条件的就删一个，结果每次删除都是 O(n)，万一删了 m 个，总代价就是 O(mn)，数据量一大立刻卡死。

更省的办法是从尾部往头部遍历，边遍历边决定要不要删。倒着删的好处是：删除某个位置时，只会移动它后面的元素，而后面那些元素你已经遍历过了，删完不影响前面还没判断的元素下标。

当然，更“正统”的做法是原地过滤：用一个慢指针指向“下一个可写位置”，遍历整个数组，把需要保留的元素一个个搬到前面去，最后截断长度。这样一趟下来 O(n)，不仅代码简单，而且不需要频繁移动大块数据。C++ 里的std::remove/erase组合干的就是这件事，Python 里则建议直接用列表推导式重建新列表，都比“边遍历边 pop”高效得多。

3. 容量管理的小算盘：扩容倍数、缩容时机与内存碎片

3.1 为什么必须翻倍扩容，而不是一次只加一

顺序表有个尴尬的问题：你一开始不知道最终要存多少元素。如果申请一块固定大小的数组，满了以后怎么办？答案只能重新申请一块更大的连续内存，把旧数据整体复制过去，再释放旧内存。这个过程就是扩容。

那问题来了：每次满了，是一次多申请一个格子，还是一次翻倍？

假设初始容量 1，每次容量用完就固定多申请 1 个位置。插入第 n 个元素时，前 n-1 个元素全都要复制一遍。算下来前 n 次插入的总复制次数是：

1 + 2 + 3 + ... + n ≈ n² / 2

均摊到每次插入，代价是 O(n)。也就是说，总共做 n 次插入，总体成本居然是平方级别，完全不能接受。

如果用翻倍策略：初始容量 1，扩容到 2、4、8、16……插入到容量 k 的过程中，总共复制的元素量大约是：

1 + 2 + 4 + ... + k ≈ 2k

也就是线性级别。均摊到每次插入，每个插入的代价是 O(1)。这就是教科书上“动态数组摊销复杂度 O(1)”的来源。

用大白话说：固定增长是“每次扩容都白干一遍前面的活，而且越干越多”；翻倍增长是“虽然偶尔一次扩容很贵，但贵完这一回，能撑很久，贵的那几次平均下来就不算贵了”。

3.2 2 倍、1.5 倍还是 1.125 倍

既然倍数增长好，那倍数是多少？常见的选择有 2 倍和 1.5 倍。

2 倍扩容的优点是扩容次数少，缺点是空间浪费严重：扩容后刚翻倍的那块区域可能有一半是空的。1.5 倍扩容更省空间，但扩容次数更多。还有一种观点涉及内存分配器的实际行为：在特定地址空间里，按 1.5 倍增长，新申请的内存块可能更容易“借”到之前释放的相邻空间，从而避免复制，但这和底层分配器实现强相关，不能一概而论。

工程里的真实选择五花八门：C++ 标准库的 vector 具体倍数未指定，常见的实现是 2 倍左右；Java 的 ArrayList 源码里写得很清楚，oldCapacity + (oldCapacity >> 1)，也就是 1.5 倍；Python 的 list 早期版本是 4、8、16 这样的 2 倍幂，后来改成更复杂的混合策略，从源码能看到容量会按 4、8、16、24、32、40、52、64……这样增长，小容量时接近 1.5 倍，大容量时增长率更小。

我不建议大家死记某个语言是几倍，关键是理解两件事：

• 必须按比例扩容，否则均摊复杂度会退化；
• 扩容倍数本质上是在“扩容频率”和“空间浪费”之间做权衡。实际项目中预留容量时，我给自己的经验是宁可多预留给 20%～30% 的余量，也不要每次贴着容量边界走。

凡是频繁含push_back/add节奏的代码，都应该利用语言提供的预分配接口，比如 C++ 的vector::reserve、Java 的ArrayList构造函数指定初始容量。否则元素数量一旦从几百变几十万，你会亲眼看到程序在扩容那几步里反复卡顿。

3.3 缩容不是免费的：防止扩容缩容“震荡”

有扩容就有缩容。问题是，缩容这个操作在工程里往往比扩容更敏感。

删除元素删到只剩容量的一小半时，要不要把底层数组缩成更小的一块？如果缩得太积极，又会在容量阈值附近反复横跳：刚缩完，下一次插入又触发扩容，扩容完，再删除又触发缩容。这种“扩容-缩容-扩容-缩容”的震荡在某些场景下会造成毁灭性的性能抖动，比喻一下就是：电梯门刚要关就有人按开门，门开开关关，永远上不去。

所以标准库的策略普遍偏保守。Java 的 ArrayList 默认不会自动缩容，容量只会越用越大，除非你手动调用trimToSize()。C++ 的 vector 也没有自动缩容，容量只增不减，想让容量收回，得用swap技巧：构造一个容量更小的临时 vector 和它交换，让临时的容纳大容量的旧 vector 被析构释放。Python 的 list 在某些 pop 操作后确实会缩小底层数组，但它的缩容阈值同样留了足够余量，防止震荡。

说一个实际经验：写服务端代码处理大量数据时，内存紧张往往不是因为单个数组太大，而是很多数组都“虚胖”了——删掉大量元素，容量却不减，整体占用居高不下。排查内存问题时，除了看堆上有没有泄漏，还得看这些动态数组的capacity是不是远大于size。如果确认是容量虚高，再考虑缩容；如果只是偶尔几千条数据，我不建议折腾缩容，留点容量反而对高频写入友好。

4. 语言实现里的三种性格：C++/Java/Python 的顺序表差别

4.1 C++ 的 vector：容量与大小分离的连续数组

C++ 标准库的std::vector是顺序表在工程中最典型的代表。它有两个关键概念：size（当前有多少个有效元素）和capacity（当前底层数组最多能容纳多少而不扩容）。push_back在容量充足时是 O(1)，容量不足就触发扩容机制，均摊复杂度仍为 O(1)。

vector 有个巨大的特点：它存储的是元素本体。如果你vector<MyStruct>，那所有MyStruct实例真的就是一块紧挨着的连续内存。正因如此，vector 对缓存非常友好，也正因如此，插入/删除元素时复制的是完整结构体，如果结构体很大，一次插入可能比链表慢得多。

用 vector 最大的坑是迭代器和指针失效。底层数组扩容时会整体搬去新内存，之前拿到的begin()迭代器、元素的裸指针全部失效。排查这类问题有过几次血泪，凡是长期持有 vector 内部地址的代码，都要慎之又慎。如果你需要稳定引用，可以改用存索引而不是存指针——比如 int 下标，只要不改变原有顺序，索引还是稳的。

4.2 Java 的 ArrayList：自动装箱里藏着的性能刺客

Java 的ArrayList底层是Object[] elementData。默认初始容量是 10，扩容是 1.5 倍。用法上它和 vector 很像，但有一个被大量程序员忽略的性能差异：ArrayList<Integer>里其实存的是 Integer 对象的引用，不是 int 本身。

为什么这个细节重要？因为整数从 int 变成 Integer 是装箱，涉及到对象分配。遍历一个ArrayList<Integer>，你不断“解引用”找到堆上的 Integer 对象，这跟遍历一个原始int[]的缓存友好度完全不是一回事。统计求和这种操作，用原始int[]可能比ArrayList<Integer>快好几倍。

另外要注意remove(0)。它在 ArrayList 上是一个 O(n) 操作，因为它要把后面所有元素往前移。很多人想写队列，用ArrayList当队列，add在尾部没问题，但频繁从头部拉数据，性能会越来越难看。队列类需求优先考虑ArrayDeque，它是循环数组实现，头尾增删都是 O(1)。

4.3 Python 的 list：对象指针构成的连续数组

Python 的 list 可能是被误解最深的数据结构。很多人以为它和 C 数组一样“把元素连续放在内存里”，实际上 CPython 的 list 底层是一个PyObject**数组，也就是一个连续存放“对象引用指针”的数组。

换句话说，list 能保证的是：每个元素的引用（指针）在内存里是紧挨着的。但元素本身——比如每个整数对象、每个字符串对象——依然分散在堆上。这带来两个结果：

第一，list 里可以放任意类型的对象，因为它存的只是指针； 第二，list 的遍历性能比不上真正连续存放原始类型的数组，而 Python 里想用“原始类型数组”，得靠array模块或numpy.ndarray这类专门的连续内存容器。

还有个高频误用是list.pop(0)和list.insert(0, x)。这两个操作都是典型的 O(n) 头尾移动。前面说过，队列入队出队应该用collections.deque，它是双向链表加块状数组的实现，两端增删都是 O(1)。

表格对比一下三种实现的性格差异：

5. 别再背八股选型：缓存局部性、真实耗时与工程真相

5.1 复杂度之外的第二张账单：CPU 缓存

教科书里讲复杂度，永远把 O(n) 当一回事。但实际工程里，数组遍历十个元素和链表遍历十个元素，复杂度一样，真实耗时可能差一个数量级。为什么？答案藏在 CPU 缓存里。

CPU 读内存不是按字节读的，而是按“缓存行”批量加载，通常一次 64 字节。数组遍历时，第一个元素命中一次缓存，后面对连续地址的访问大概率都在同一条已加载的缓存行里，不需要再去内存。链表就惨了，每个节点还带着一个“next 指针”，内存地址完全分散，几乎每跳一个节点都要去内存重新取，缓存的预取机制还很难提前猜到下一个节点在哪里。

在数据量大的场景下，这种差距会被放大。有个说法叫“现代计算机的性能瓶颈不是 CPU 算不过来，而是数据喂不上去”。顺序表恰恰是喂数据最舒服的结构：它天然满足空间局部性。所以工程上很多排序、查找、哈希表的开放寻址实现，都果断选择连续数组，而不是一个个散落的小对象。

5.2 什么时候顺序表明确不合适

顺序表不是万能的。我整理几个“明显该换”的场景：

• 高频在头部插入、头部删除，且数据量持续增长。比如一个不断从队头消费、队尾生产的日志队列，如果顺序表实现，每次消费都移动所有剩余元素，百万级别数据量必然扛不住。这时用环形队列或者块状数组更合理。

• 元素本体特别大，且频繁在中间插入删除。比如数组里存几十 KB 的大结构体，插一次要搬几百 KB 数据，代价远高过链表改一次指针。但注意，如果改成“数组存指针，指针指向大对象”，顺序表依然可行，代价是额外的一次指针跳转。

• 需要长期持有“元素指针/引用”且不能被意外失效。vector 扩容后指针失效，链表没有这个问题。

剩下的大多数场景，顺序表都是更省心的选择。很多同学容易产生一种错觉：链表插入 O(1)，数组插入 O(n)，所以“要频繁插入的都用链表”。这个结论在真实场景里经常不成立。因为你插入前通常还要找到插入位置，链表找位置是 O(n)；找到以后，链表的节点又是分散内存，后续遍历同样慢。只有当你已经持有节点指针，并且确实只在某几个已知节点附近增删时，链表的 O(1) 才有意义。

5.3 我给选型用的决策清单

遇到“数组 or 链表”这个老问题时，与其背口诀，不如过一遍下面这组问题：

1. 你需要按下标立即访问某个位置的元素吗？需要，选顺序表。
2. 你的操作模式是遍历多、随机改少？选顺序表，缓存优势明显。
3. 你的增删集中在尾部吗？选顺序表，尾增删 O(1)。
4. 你的增删集中在头尾两端吗？考虑环形队列或 deque，而不是裸链表。
5. 你需要在任意位置反复插入删除，且已经持有位置引用？再考虑链表。
6. 元素体积超大，复制代价吓人？要么改为存指针，要么考虑链表。

这套清单做出来后，大多数“要不要换链表”的纠结就消失了。实际上在我看过的高性能后端模块里，写链表的地方远少于写数组的地方；反倒是那些“为了一点插入性能换链表、结果遍历性能崩掉”的案例更多。

6. 用顺序表时的几个血泪细节

6.1 Python list 当队列，卡在 pop(0)

之前帮人调一个模拟项目X，里面有个模块用list做临时任务队列：追加到尾部，然后不断从头部取任务处理。数据量一开始几千条没感觉，后面涨到一两万时，肉眼可见越来越卡。

原因不神秘：每条任务被消耗时会pop(0)，这一个操作就是 O(n)；所有元素都要往左挪一格。总共处理 n 条任务的代价是 O(n²)。改成collections.deque的popleft()之后，耗时可忽略。这是顺序表经典误用，也是我在性能排查里见过次数最多的问题之一。

6.2 几千次扩容风暴

另一个案例是某图像处理Demo，用std::vector不断push_back一批高分辨率图像的中间数据，每个元素又是几 MB 级的大结构体，数据量有几万个。没做 reserve 前，扩容把整个程序拖得一顿一顿，因为一旦扩容，所有旧元素都要搬动；后来初始化时就reserve(预估最大值 * 1.2)，扩容风暴直接消失。

有人会问，翻倍扩容摊还成本不是 O(1) 吗？理论没错，但那是长周期平均后的结论。工程里的“写放大”往往集中在少数几次扩容瞬间，用户感受到的是这几毫秒的卡顿，而不是平均数据。所以大对象集合强烈建议一次性预留容量，或者用分批写入避免反复整块搬移。

6.3 头插导致平方复杂度

还有一种典型错误：把一堆数据按某种优先级顺序不断插入到数组头部。比如要维护一个“最近优先”的列表，每次都insert(0, item)到最前面。看起来好像很直观，其实每插入一次就移动全部已有元素。插入 n 个元素的整体代价又是 O(n²)。

解决办法有很多：如果只需要最终顺序，可以先全部append到尾部，最后统一反转；如果每来一个元素都要立刻看到最新顺序，而且量很大，就要考虑别的结构。但无论如何，“数组头插”这四个字一出现，就该拉响性能警报。

再说一个通用的取舍建议：凡是频繁“删除数组中间若干元素”的场景，优先考虑“重建数组”策略而不是一个个删。比如在 Python 里，删除 list 中所有偶数，[x for x in arr if x % 2 != 0]一次遍历搞定；在 C++ 里，erase + remove也是高效惯例。直接写循环边遍历边erase反而容易漏元素，代码还不好看。

顺序表看着简单，可它的每一条性质都在和内存、缓存、复杂度这三个层次发生关系。熟练之后，看到list.pop(0)、看到大循环里vector::insert、看到无预分配的百万次push_back，下意识就能猜到性能问题在哪。这不只是会背“连续存储、随机存取、增删 O(n)”三句话的事，而是把“连续内存”这四个字背后那笔账算透了。以后再遇到和数组相关的性能问题，建议你都用这篇的思路推一遍：先算地址，再看移动，最后琢磨容量。这三笔账想明白，绝大多数顺序表的坑都能提前避开。