Summary

数组是最基础、也最被低估的数据结构。它的两个标签——连续存储和 O(1) 随机访问——不仅决定了它自己的性能,还撑起了几乎所有更复杂的结构(栈、队列、堆、哈希表的桶、邻接矩阵),以及一整套只有数组才玩得转的算法套路(双指针、前缀和、差分、滑动窗口)。真正吃透数组,是吃透后面一切的前提。

逻辑结构 vs 物理结构

讨论任何数据结构,都要分清两个层面:

  • 逻辑结构:数据在"概念上"如何组织。数组的逻辑结构是——有限个类型相同的元素,按顺序排成一列,每个元素有唯一编号(下标 index,从 0 开始)。
  • 物理结构:数据在"内存里"如何存放。数组的物理结构是——顺序存储,即所有元素挨着放在一整块连续的内存里。

数组的所有性能特征,都是这个"连续 + 等大"的物理结构直接推导出来的。记住这句话,下面全是它的推论。

数组在内存里到底长什么样

假设有一个 [5]int32,每个 int32 占 4 字节,它在内存里是这样的:

下标:      0        1        2        3        4
        ┌────────┬────────┬────────┬────────┬────────┐
内存:    │ 4 字节 │ 4 字节  │ 4 字节  │ 4 字节  │ 4 字节 │
        └────────┴────────┴────────┴────────┴────────┘
地址:   1000     1004     1008     1012     1016
        ↑
      首地址 base

因为元素等大、内存连续,访问第 i 个元素时,CPU 不需要一个个数过去,而是直接用一个乘加算出地址:

element_address = base_address + i * element_size

访问下标 2:1000 + 2 * 4 = 1008,一步到位。这个"一步算出地址"就是 O(1) 随机访问的本质,也是数组区别于链表最核心的优势——链表的节点散落各处,想找第 i 个只能从头走 i 步。