数组
复习
- 输入规模与增长速度：关注算法代价随规模的增长趋势
- 时间与空间的交换：用空间常常能换时间
- 抽象数据类型：先规定能做什么，再决定怎么做
TL;DR
- 数组在内存中连续存放，每个元素大小相同
- 连续带来了随机访问：按下标一步定位
- 代价是插入和删除往往要移动大量元素
- “查询快、增删慢”，是数组最典型的取舍
正文
前面几章都在讲“怎样衡量”，现在可以开始认识具体的数据结构了。最基础、也最常见的一个，就是数组（array）。
一排编号的格子
想象一排连续排列的储物格，每个格子一样大，并且从 0 开始编号。数组就长这样：它在内存中占据一段连续的空间，元素一个挨一个地放着。
因为每个元素大小相同、位置又连续，只要知道两件事，就能算出任何一个元素的地址：
元素地址 = 起始地址 + 下标 × 单个元素大小
注意，这是一步就能算出来的，不需要从头找起。所以数组按下标访问任意元素，代价都是固定的——这就是随机访问（random access）。它很快，是数组最大的优点。
快在哪，慢在哪
可也正因为“连续”，数组在中间插入或删除元素时就很麻烦。
比如要在第 3 个位置插入一个新元素。为了给它腾出位置，从第 3 个开始的所有元素，都得整体往后挪一格。删除则相反，要把后面的元素往前挪。数据一多，挪动量就很大，代价是 O(n)。
于是数组的性格非常鲜明：
- 按下标访问：
O(1)，极快 - 在中间插入或删除：
O(n)，较慢
这又一次印证了那句老话：没有一种结构能让所有操作都最优。 数组用“连续”换来了随机访问，也为此付出了“增删要挪动”的代价。
另外，普通数组的容量是固定的：创建时就定好了能放多少个。那如果一开始不知道要放多少数据，怎么办？下一章来解决。
思考题 1
数组为什么能按下标“一步”访问任意元素？
思考题 2
在数组中间插入一个元素，为什么代价是
O(n)？
小结
知识点
- 数组在内存中连续存放，元素等大
- 连续使随机访问成为可能，代价
O(1) - 中间插入与删除需移动元素，代价
O(n) - 普通数组容量固定
参考资料
- Wikipedia(zh)：数组：连续存储的同类元素序列
- Wikipedia(zh)：随机存取：可直接访问任意位置的数据访问方式
思考题答案（仅供参考）
思考题 1
因为元素连续且等大，地址可以用“起始地址 + 下标 × 元素大小”一步算出，不必逐个查找，所以任意下标都能直接定位，代价固定。
思考题 2
因为要维持“连续”这个性质，插入位置之后的所有元素都必须整体后移一格，腾出空位。移动的元素数量与规模成正比，所以是 O(n)。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪