数组可能是我们写代码时最早接触的数据结构。

从 int[] 到 ArrayList，从 Go 的切片到底层数组，再到数据库里的连续页结构，很多地方都能看到它的影子。

它看起来特别简单：开一段空间，挨个放数据，再用下标取出来。

但数组的“简单”并不是没有原理，而是把复杂度集中到了内存布局上。

为什么数组按下标读取这么快？

为什么中间插入一个元素会变慢？

为什么数组扩容时要重新申请空间、复制数据？

这篇我们把 Array 数组拆开看看，顺便用几张字符图把它在内存里的样子画出来。

数组到底是什么

数组是一种线性表数据结构。

它使用一组连续的内存空间，存储一组相同类型的数据。

这句话里有两个重点：连续内存、相同类型。

先看它在内存里的大概样子：

数组起始地址 = 1000
每个 int 占用 = 4 字节

地址       1000       1004       1008       1012       1016
           ┌────────┬────────┬────────┬────────┬────────┐
下标       │   0    │   1    │   2    │   3    │   4    │
           ├────────┼────────┼────────┼────────┼────────┤
数据       │   18   │   25   │   31   │   42   │   56   │
           └────────┴────────┴────────┴────────┴────────┘
​

每个元素紧挨着下一个元素，地址之间的间隔也完全一样。

这就是数组可以快速定位的基础。

线性表是什么

线性表可以理解成一列排好队的数据。

每个元素最多只有前驱和后继两个方向，数据之间是一对一的线性关系。

数组是线性表，链表、队列、栈也都是线性表。

区别在于，它们保存数据的方式不一样：

数组：连续摆放
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘

链表：节点分散，用指针串起来
┌──────┐    ┌──────┐    ┌──────┐
│ 10   │───>│ 20   │───>│ 30   │───> nil
└──────┘    └──────┘    └──────┘
​

数组靠地址计算找元素，链表靠指针一步步走过去。

所以数组擅长随机读取，链表擅长局部插入和删除，后面所有的优缺点都从这里开始。

数组为什么查得快

数组最核心的能力，是根据下标随机访问。

所谓随机访问，不是说访问顺序随机，而是说：不管要访问第一个元素、第五个元素，还是第一百万个元素，都可以直接算出它的地址，不需要从头挨个找。

寻址公式

数组第 index 个元素的地址，可以用下面这个公式计算：

Array[index] 地址
= 数组起始地址 + index × 单个元素占用空间
​

拿前面的数组举例：

数组起始地址：1000
int 占用空间：4 字节

Array[0] = 1000 + 0 × 4 = 1000
Array[1] = 1000 + 1 × 4 = 1004
Array[3] = 1000 + 3 × 4 = 1012
​

不管数组里有多少元素，计算 Array[3] 都只需要一次乘法和一次加法。

所以数组按下标访问的时间复杂度是 O(1)。

这也是为什么数组下标通常从 0 开始。

下标从 0 开始时，地址公式直接就是“起始地址 + 下标 × 类型大小”，不需要再额外减 1。

当然，现在编译器会帮我们优化，这一次减法本身并不是什么大成本。

但从设计上看，0 下标和连续内存确实是天然匹配的。

为什么要求相同类型

寻址公式能成立，还有一个前提：每个元素占用的空间长度必须固定。

如果每个元素长度都一样，程序只需要知道下标，就能算出偏移量。

如果数组里一会儿放 4 字节的整数，一会儿放 20 字节的对象，地址就不能简单按固定步长计算了。

这也是传统数组通常要求元素类型一致的原因。

所谓泛型数组，很多时候并不是让不同大小的对象直接挤在同一块内存里，而是让数组保存统一大小的引用或指针。

引用数组：每个格子保存一个地址，地址长度固定

┌────────┬────────┬────────┬────────┐
│  ref A │  ref B │  ref C │  ref D │
└───┬────┴───┬────┴───┬────┴───┬────┘
    │        │        │        │
    ▼        ▼        ▼        ▼
  对象A    对象B    对象C    对象D
​

Java 里的 List、JavaScript 里的数组等高级容器，内部实现比“连续放几个整数”复杂得多，但底层仍然会尽量利用连续存储或连续的引用表来换取访问效率。

数组为什么改得慢

数组的读取很快，但插入和删除就没有那么轻松了。

原因也很直白：数组元素是连续排队的，中间突然插入或删除一个元素，后面的人都得挪位置。

中间插入

假设数组里有 10、20、40、50，现在想在下标 2 的位置插入 30。

原来的布局是：

下标       0      1      2      3
数据      10     20     40     50
​

为了给 30 腾出位置，40 和 50 都要向后移动一格：

第一步：后面的元素整体右移

下标       0      1      2      3      4
数据      10     20     40     50      空
                         ───>   ───>

第二步：把新数据放进空位

下标       0      1      2      3      4
数据      10     20     30     40     50
​

如果插入位置越靠前，需要移动的元素就越多。

平均下来，中间插入的时间复杂度是 O(n)。

但如果是在数组尾部追加，只要尾部还有空闲位置，就不用移动其他数据，接近 O(1)。

所以“数组插入慢”不能一概而论，尾部追加和中间插入是两个完全不同的场景。

中间删除

删除和插入正好相反。

假设要删除下标 2 的 30，后面的 40 和 50 就要向前挪：

删除前：
下标       0      1      2      3      4
数据      10     20     30     40     50

删除 30 后，后面的元素左移：

下标       0      1      2      3
数据      10     20     40     50
                    <──    <──
​

同样，删除头部元素需要移动大量数据，删除尾部元素通常只需要减少一个长度记录。

如果业务只关心“删除某个元素”，不要求保留原有顺序，有一种常见优化：把最后一个元素搬到被删除的位置，再缩短数组。

删除下标 1 的 20，不要求保持顺序

删除前：  [10, 20, 30, 40, 50]
把末尾 50 搬到下标 1：
删除后：  [10, 50, 30, 40]
​

这样可以把删除优化到接近 O(1)，代价是元素顺序变了。

算法题和一些无序集合场景里经常这么干，工程代码里要先确认业务是否允许顺序变化。

数组扩容要搬家

原生数组通常是定长的。

申请了一块连续内存后，后面能不能继续放元素，取决于它后面是否还有一段连续的空闲空间。

问题是，后面的空间不一定空着，就算有空闲，也不一定刚好够用。

因此动态数组扩容通常不是在原地“变长”，而是重新找一块更大的连续空间，再把旧数据复制过去。

旧数组容量 = 4

旧空间：
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘

新增元素时容量不够，申请新空间：

新空间：
┌────┬────┬────┬────┬────┬────┬────┬────┐
│    │    │    │    │    │    │    │    │
└────┴────┴────┴────┴────┴────┴────┴────┘

复制旧数据，再写入新元素：
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │    │    │    │
└────┴────┴────┴────┴────┴────┴────┴────┘
​

扩容大致有三个步骤：

1. 判断当前容量是否足够
2. 申请一块更大的连续内存
3. 复制旧数组，并把新元素放进去

单次扩容会复制很多数据，时间复杂度是 O(n)。

但动态数组一般不会每次只增加一个位置，而是按一定比例扩容，比如扩成原来的 1.5 倍或 2 倍。

这样虽然偶尔会遇到一次搬家，但从很多次追加的平均结果看，尾部追加仍然可以做到摊销 O(1)。

为什么不能每次只加一个

假设数组每次容量不够就只增加一个位置。

添加第 1 个元素复制 0 个，添加第 2 个复制 1 个，添加第 3 个复制 2 个……

添加 n 个元素，总复制次数大约是：

0 + 1 + 2 + 3 + ... + (n - 1)
= n × (n - 1) / 2
= O(n²)
​

如果按倍数扩容，复制次数会少很多。

空间多申请一点，换来后续更多次不用搬家，这就是动态数组的典型空间换时间。

当然，扩容比例也不是越大越好。

扩得太小，频繁搬家；扩得太大，浪费内存。

具体比例要看语言实现和业务场景，我们平时直接使用标准库容器就好，别轻易自己造一个“更聪明”的动态数组。

数组和链表怎么选

数组和链表经常被放在一起比较。

它们没有绝对的好坏，主要看访问模式。

操作场景	数组	链表
按下标读取	O(1)，很快	O(n)，需要遍历
头部插入	O(n)，需要移动	O(1)，改指针即可
尾部追加	有空闲时接近 O(1)	保存尾指针时 O(1)
中间插入	O(n)，需要移动元素	找到位置后改指针
内存局部性	好，连续访问更友好	差，节点可能分散
扩容	可能需要复制	通常不用整体搬迁

实际项目里，数组往往比想象中更常用。

因为现代 CPU 有缓存机制，连续访问数组时，附近的数据很可能已经被提前加载进缓存，遍历效率通常很好。

链表虽然插入时少搬数据，但它的节点分散在内存中，访问每个节点都可能带来指针跳转，未必真的比数组快。

所以不要只看某一个操作的理论复杂度，还要看数据规模、访问顺序、缓存命中和实际压测结果。

小结

数组的核心就三件事：

• 一段连续的内存空间
• 一组大小一致的数据或引用
• 通过下标和地址公式实现快速随机访问

它的优点是：

• 下标访问快，时间复杂度 O(1)
• 连续内存带来良好的缓存局部性
• 遍历简单，额外指针开销小

它的缺点也很明确：

• 中间插入和删除需要移动后续元素
• 固定数组不能直接扩容
• 动态数组扩容时需要申请新空间并复制数据

一句话总结：数组查得快，改得慢，扩容还要搬家。

如果业务主要是按下标读取、顺序遍历和尾部追加，数组通常是很稳的选择。

如果业务大量在头部或中间插入删除，再考虑链表、队列、双端队列或者其他更适合的结构。

数据结构没有万能答案，先看数据怎么访问，再决定怎么存。