数组 | 自在学

数组：从连续内存到动态表与堆

如果把数组只理解成“把一串值放在方括号里”，很多现象都会显得零散：为什么下标访问快，为什么中间插入慢，为什么动态数组偶尔会停顿，为什么一棵树能塞进一段连续内存，又为什么链表的指针也能用整数下标来模拟。

把这些问题串起来，只需要抓住一个事实：数组是一段按固定步长划分的连续存储空间。下标把逻辑位置映射为物理地址；容量决定已经申请了多少槽位；有效长度说明其中多少槽位属于当前数据结构。围绕这三个量，我们可以搭出栈、环形队列、对象池、堆和动态表。

数组把逻辑位置映射到连续内存槽位

这篇文章会从地址计算开始，逐步讨论数组承载的数据结构、扩缩容的摊还分析，以及数组表示和链式表示之间真正的取舍。示例默认使用从 0 开始的下标；讲到堆时，会同时给出从 1 开始和从 0 开始的公式。

下标为什么能直接找到元素

假设数组第一个元素的地址是 $B$ ，每个元素占 $w$ 个字节，下标从 $0$ 开始。第 $i$ 个元素的地址是：

\operatorname{addr}(A[i]) = B + i \times w

这里没有“从第一个元素走到第 $i$ 个元素”的过程。处理器只要完成一次乘法和一次加法，就能得到目标地址。因此，在通常的 RAM 计算模型里，读取或改写 A[i] 都记为 $O(1)$ 。

例如，起始地址为 0x1000，每个元素占 4 字节，那么 A[3] 的地址是：

0\text{x}1000 + 3 \times 4 = 0\text{x}100C

这个公式成立有两个前提。第一，每个槽位的宽度固定；第二，槽位连续排列。元素如果大小不一，程序通常不会把变长内容直接塞进同一个定长数组，而是存放指针、句柄或描述符，让数组中的每个槽位仍保持相同宽度。

下标访问是常数时间，不等于每次访问在真实机器上都耗时完全相同。越界检查、缓存命中、内存页和对齐方式都会影响实际延迟。复杂度表达的是访问所需步骤不随数组长度增长，而不是忽略硬件层次。

访问、搜索与移动不是一回事

知道下标时，访问是 $O(1)$ ；只知道值时，无序数组通常需要逐项比较，最坏是 $O(n)$ 。在位置 $i$ 插入新元素，为了保留原有顺序，需要把区间 A[i..n-1] 整体右移；删除后也要把后续元素左移。它们的移动量分别是 $n-i$ 和 $n-i-1$ ，最坏都是。

text

原数组： [甲, 乙, 丙, 丁, _]
在下标 1 插入 新：
右移：   [甲, 乙, 乙, 丙, 丁]
写入：   [甲, 新, 乙, 丙, 丁]

连续布局带来的另一项实际收益是局部性。顺序扫描 A[0]、A[1]、A[2]... 时，后一个元素通常就在前一个元素旁边，硬件可以成块预取。链式结构即使也是线性顺序，节点若散落在不同位置，遍历时也可能频繁等待新的内存块。

交互实验：地址计算器

调整起始地址、元素宽度和下标，观察目标槽位与地址如何变化。

小测

某数组起始地址为 0x2000，每个元素占 8 字节，A[5] 的地址是多少？

保持顺序地在长度为 n 的数组开头插入一个元素，最坏时间复杂度是 ____。

有效长度与容量要分开管理

一段已申请的数组空间，未必每个槽位都属于当前数据结构。我们通常维护两个量：

capacity：这块存储区一共有多少个槽位；
size：当前真正存了多少个有效元素。

它们始终满足：

0 \leq size \leq capacity

这个区分让一个数组可以承载不同的逻辑结构。数组本身只提供槽位，额外的状态变量定义“哪些槽位有效”和“下一次操作发生在哪里”。

同一段数组通过边界变量承载栈与环形队列

栈只需要一个顶部边界

用数组实现栈时，设 top 表示有效元素个数，也就是下一个可写位置。有效区间是 A[0..top-1]。压栈把值写入 A[top] 后递增 top；出栈先递减 top，再读取 A[top]。

text

PUSH(A, x)
    若 top == capacity：报告上溢或先扩容
    A[top] = x
    top = top + 1
 
POP(A)
    若 top == 0：报告下溢
    top = top - 1
    返回 A[top]

只要不触发扩容，这两个操作都只读写常数个位置，所以是 $O(1)$ 。弹出后，旧值即使仍留在槽位里，也已经不属于栈；判断有效性的依据是 top，不是内存中是否还能看到某个比特模式。

环形队列把数组首尾接起来

普通队列从尾部入队、从头部出队。如果每次出队都把后续元素整体前移，代价会变成 $O(n)$ 。环形队列改用 head 和 tail 两个下标：head 指向队首，tail 指向下一个写入位置；下标到达数组末尾后，通过取模回到开头。

next(i) = (i + 1) \bmod capacity

一种简洁的判定方案是始终保留一个空槽位：

head == tail 表示队列为空；
next(tail) == head 表示队列已满；
实际最多存 capacity - 1 个元素。

保留空槽位并非唯一方案。也可以额外维护元素个数 size，这样能用满全部槽位，但状态更新多一个变量。选择哪种实现不影响入队和出队的 $O(1)$ 时间界。

两个栈还能共享一段空间

如果两个栈的容量需求会波动，可以让一个栈从数组左端向右增长，另一个从右端向左增长。只有当两个顶部相邻时才真正没有空间。这比提前把数组硬切成两半更灵活，也展示了一个常见设计方法：连续存储区可以共享，边界必须清楚且不能交叉。

数组越界并不是“取到了一个错误元素”这么简单。在缺少自动边界检查的环境里，越界读写可能触碰别的对象或控制信息。实现任何数组结构时，都应先写清空、满和合法下标条件。

小测

数组栈执行一次 POP 后，必须把原顶部槽位清零，POP 才能算 O(1)。

使用长度为 8、保留一个空槽位的环形队列时，下列说法哪些正确？

下标也可以充当指针

链式结构的核心不是某种特殊语法，而是“一个对象能指出另一个对象的位置”。如果语言没有显式指针，或者我们想把对象放进自己管理的内存池，完全可以用数组下标充当位置标识。

多数组表示：同一下标拼成一个对象

假设双向链表节点有 key、next、prev 三个字段。我们可以准备三个等长数组：

text

下标       0    1    2    3    4    5
key       甲    丁    ·    乙    ·    丙
next       3    -1    ·    5    ·    1
prev      -1     5    ·    0    ·    3

下标 3 同时选择 key[3]、next[3]、prev[3]，这三个槽位合起来就是一个逻辑对象。next[3] = 5 表示当前节点的后继位于第 5 号对象槽。-1 或一个不可能成为合法下标的整数可以表示“无指向”。

这种布局常被称为按字段分开存放。只扫描某一个字段时，它有很好的连续性；代价是读取一个完整对象时需要访问多个数组。

单数组表示：起始下标加字段偏移

也可以让每个对象占据连续的固定宽度。例如每个节点占三个槽位，偏移 0、1、2 分别保存 key、next、prev。若对象起始下标为 p，字段地址就是：

key(p)=A[p],\quad next(p)=A[p+1],\quad prev(p)=A[p+2]

这里的 p 就像对象的地址，字段偏移就像对象内部的布局。固定宽度对象很容易管理；若对象长度不同，就还要记录长度、对齐并处理碎片，分配器会复杂得多。

数组下标模拟指针、对象字段与空闲链表

空闲链表让分配与归还保持常数时间

容量为 $m$ 的对象池里，当前有 $n$ 个槽位在使用，其余 $m-n$ 个槽位可以串成一条“空闲链表”。变量 freeHead 保存第一个空闲槽位的下标，空闲槽位复用 next 字段指向下一个空闲槽位。

text

ALLOCATE()
    若 freeHead == NIL：报告空间耗尽
    x = freeHead
    freeHead = next[x]
    返回 x
 
FREE(x)
    next[x] = freeHead
    freeHead = x

这条空闲链表像一个栈：最后归还的槽位最先再次分配。分配和释放都只修改头部，因此是 $O(1)$ 。同一组数组可以同时交织保存多条链表和一条空闲链表，只要每个槽位在任一时刻只属于一个集合。

如果为了分页或缓存效率而压紧所有在用对象，就必须搬移对象并修正指向它们的下标。只要数组外部还保存着旧下标，搬移就会让这些句柄失效。工程实现常用“稳定句柄表”再间接一层，或明确规定压紧期间不得保留外部位置。

小测

在 key、next、prev 三个等长数组表示节点时，下标 x 的含义是什么？

对象池使用空闲链表后，分配一个空闲槽位和归还一个槽位都可以是 O(1)。

完全二叉树可以压进一维数组

完全二叉树除最后一层外都填满，最后一层从左到右连续填充。这样的形状没有“中间缺洞”，所以按层从左到右编号后，父子关系可以直接从下标计算出来，不需要为每个节点保存左右指针。

完全二叉树与堆数组的下标对应关系

两套常用下标公式

若根节点放在 A[1]，节点 i 的父节点、左孩子和右孩子是：

parent(i)=\left\lfloor\frac{i}{2}\right\rfloor,\quad left(i)=2i,\quad right(i)=2i+1

若根节点放在 A[0]，更常见于实际编程，则公式变为：

parent(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,\quad left(i)=2i+1,\quad right(i)=2i+2

数组的物理长度和当前堆大小仍要分开。length 或 capacity 描述底层数组，heapSize 只描述 A[0..heapSize-1] 中属于堆的元素。堆排序时，尾部会逐渐变成已排序区，数组没有缩短，但 heapSize 会持续减小。

堆序只约束父子，不保证整体有序

最大堆要求每个非根节点都不大于父节点，所以根一定是全局最大值；任意子树的根也是该子树最大值。最小堆方向相反。兄弟之间、不同子树之间没有排序要求，因此最大堆数组通常不是降序数组。

当某个节点比孩子小，最大堆的“下沉”操作比较它与两个孩子，把三者中最大的换到父位置，再沿被交换的孩子继续。每次下降一层，完全二叉树高度为 $\Theta(\log n)$ ，所以单次下沉最坏是 $O(\log n)$ 。

text

SIFT_DOWN(A, i, heapSize)
    循环：
        largest = i
        l = 2i + 1
        r = 2i + 2
        若 l < heapSize 且 A[l] > A[largest]：largest = l
        若 r < heapSize 且 A[r] > A[largest]：largest = r
        若 largest == i：结束
        交换 A[i] 与 A[largest]
        i = largest

自底向上建堆为什么是线性时间

从最后一个非叶节点开始，逆序对每个内部节点执行下沉，就能把任意数组变成堆。粗略地把每次下沉都按 $O(\log n)$ 计算，会得到 $O(n\log n)$ ，但这不是紧确上界。大多数节点离叶子很近：约一半节点本来就是叶子，无需下沉；约四分之一最多下沉一层；约八分之一最多下沉两层。

总工作量可以写成：

O\left(n\sum_{h=0}^{\infty}\frac{h}{2^h}\right)=O(n)

因此，自底向上建堆是 $O(n)$ 。这也是分析数组形状时一个很有用的提醒：不能只用“操作次数乘最坏单次代价”，还要看不同位置实际能走多远。

堆顶读取是 $O(1)$ ；删除堆顶后把最后元素移到根，再下沉恢复堆序，耗时 $O(\log n)$ ；插入则先写到数组末尾，再沿父节点上浮，也是 $O(\log n)$ 。如果堆元素还对应外部对象，交换数组元素时也要同步更新对象保存的堆下标，否则旧句柄会指错位置。

交互实验：树形位置与数组下标

选择任意节点，观察它的父节点和孩子；切换最大堆、最小堆，可检查同一组数据是否满足对应堆序。

小测

采用从 0 开始的堆数组，下标 i 的孩子下标可能是哪些表达式？

自底向上建堆需要对 O(n) 个节点下沉，每次下沉最坏 O(log n)，所以建堆的紧确上界一定是 O(n log n)。

动态表把偶发搬迁摊到连续操作中

固定数组要求提前知道容量，但很多程序无法预知最终元素数。动态表在底层仍使用连续数组，只是在空间满时申请更大的数组，把旧元素搬过去，再释放旧数组。

我们用 num 表示元素个数，size 表示槽位总数，非空表的装载因子是：

\alpha(T)=\frac{T.num}{T.size}

只考虑插入时，一种常见策略是满载后把容量翻倍。初始为空，第一次插入申请一个槽位；以后当 num == size 时申请 2 × size 个槽位。

text

TABLE_INSERT(T, x)
    若 T.size == 0：
        申请 1 个槽位
        T.size = 1
    若 T.num == T.size：
        申请容量为 2 × T.size 的新数组
        把旧数组中的 T.num 个元素搬到新数组
        释放旧数组，并让 T 指向新数组
        T.size = 2 × T.size
    把 x 写入下一个空槽位
    T.num = T.num + 1

容量翻倍时元素搬迁与装载因子的变化

单次代价与摊还代价要分别回答

若当前还有空位，插入只需写一次，实际代价记为 1。若第 $i$ 次插入遇到满表，要搬移已有的 $i-1$ 个元素，再写入新元素，实际代价是 $i$ 。所以某一次插入的最坏代价确实是 $O(n)$ 。

但扩容只发生在已有元素数为 1、2、4、8... 时。连续执行 $n$ 次插入，普通写入总共 $n$ 次，历次搬移量构成几何级数：

1+2+4+\cdots+2^{\lfloor \log_2 n \rfloor}<2n

因此总成本小于 $3n$ ，每次插入的摊还成本至多是常数。这里没有假设输入随机，也没有计算“运气好时的平均值”；结论覆盖任意长度为 $n$ 的连续插入序列。

三种视角会得到同一个结论

聚合视角直接把 $n$ 次操作的总成本控制在 $O(n)$ ，再除以 $n$ 。

记账视角可以想象每次插入收取 3 个单位：1 个支付当前写入，1 个留给新元素未来的搬迁，另 1 个补给扩容后已经存在的元素。到下一次满载时，累积余额足以支付整表搬迁。这里的“余额”只是证明工具，不需要作为字段写进程序。

势能视角把整张表的预付工作集中记录。只插入且容量翻倍时，可以定义：

\Phi(T)=2T.num-T.size

扩容刚完成时，表约为半满，势能回到 0；临近下一次扩容时，势能增长到足以支付搬移。设实际成本为 $c_i$ ，第 $i$ 次操作的摊还成本是：

\hat{c_i}=c_i+\Phi_i-\Phi_{i-1}

无论本次是否扩容，代入后都可以把摊还成本界定为常数 3。势能从便宜操作中累积，在昂贵操作中下降，恰好解释了“偶发的线性搬迁为什么不破坏长期常数成本”。

交互实验：观察扩容、收缩与搬移次数

点击插入或删除，槽位颜色会显示当前元素数；日志会区分普通操作、扩容和收缩。你也可以连续执行一批操作，比较单次尖峰与累计平均成本。

小测

容量按 1、2、4、8……翻倍时，连续插入 n 个元素的总搬移次数属于哪个数量级？

动态数组尾部插入的摊还 O(1) 意味着每一次插入的实际成本都为 O(1)。

收缩需要与扩容留出缓冲区

只扩不缩会让一个曾经很大的动态表在删除大量元素后继续占用过多空间。收缩的基本动作与扩容相同：申请更小的连续数组，把保留的元素搬过去，释放旧数组。真正难点不是“会不会缩”，而是“什么时候缩”。

在半满处来回切换会产生抖动

设扩容规则是满时翻倍。如果又规定“删除后低于二分之一就减半”，那么表刚从容量 $m$ 扩到 $2m$ 时，装载因子约为 $1/2$ 。接下来少量删除就会触发收缩，少量插入又会触发扩容。操作序列在阈值附近来回摆动，每次却要搬移 $\Theta(m)$ 个元素，摊还成本可能退化为线性。

这类问题叫阈值抖动。解决方式是滞回：触发两个相反动作的阈值不要重合。一个稳妥规则是：

插入前满载，即 $\alpha=1$ 时，把容量翻倍；
删除后低于四分之一，即 $\alpha<1/4$ 时，把容量减半；
扩容或收缩完成后，装载因子回到约 $1/2$ 。

从 $1/2$ 走到 $1$ 需要许多次插入，从 $1/2$ 走到 $1/4$ 也需要许多次删除。这些便宜操作为下一次搬迁留出了足够距离。非空表的装载因子不会长期低于常数 $1/4$ ，所以闲置空间也只会是总空间的常数倍。

扩容与收缩阈值分离以避免来回抖动

分段势能同时解释两个方向

把半满看成最稳定状态，势能设为 0；装载因子向满载或四分之一偏离时，势能都增加。可以使用下面的分段函数：

\Phi(T)= \begin{cases} 2T.num-T.size, & \alpha(T)\geq 1/2 \\ T.size/2-T.num, & \alpha(T)<1/2 \end{cases}

它始终非负。在 $\alpha=1/2$ 时势能为 0；在 $\alpha=1$ 和 $\alpha=1/4$ 时，势能都增长到与当前元素数同阶，足以支付一次搬迁。把它代入摊还成本公式，可以得到：插入的摊还成本有常数上界，删除的摊还成本也有常数上界，所以任意 $n$ 次插入、删除的总实际时间是 $O(n)$ 。

扩容倍数和收缩阈值并非只能取 2 与 1/4。设计的关键是保持几何增长，并让扩容、收缩阈值之间存在固定间隔。具体参数还会影响内存浪费、复制频率和延迟尖峰。

空间与延迟仍需要工程判断

摊还分析控制总工作量，却不会消除某一次长搬迁。如果系统要求严格的单次延迟上界，可以采用分段数组、增量迁移或预留容量等策略。它们放弃或弱化“始终只有一块连续数组”的简单性，换取更平滑的响应时间。

缩容也不一定要在每次删除后立即发生。短时间内很可能重新增长的缓存、编辑缓冲区或请求队列，保留一部分容量通常更划算。shrink_to_fit 一类操作若存在，也往往只是请求，是否真的重新分配要看具体实现。

小测

满载时扩容翻倍后，哪种收缩规则最容易在少量交替插入和删除下产生抖动？

采用满载翻倍、低于四分之一减半的策略时，下列说法哪些正确？

数组与链式表示应按操作模式选择

“数组访问快、链表插入快”只是一个过度压缩的结论。真正选择表示方式时，要把已知位置、查找成本、元素移动、内存布局和句柄稳定性放在一起看。

数组与链式表示在访问、移动、局部性和句柄稳定性上的权衡

维度	数组表示	链式表示
按位置访问	由地址公式直接定位， $O(1)$	通常要沿指针走到目标， $O(n)$
已知位置后的局部插删	为保持顺序可能搬移后缀，最坏 $O(n)$	已持有目标节点或相邻节点时，改指针可为 $O(1)$
按值查找	无序时通常 $O(n)$ ；有序时可二分

表中“链表删除 $O(1)$ ”有一个经常被漏掉的条件：你已经拿到待删节点的指针。若题目只给一个键，还得先搜索，最坏仍是 $O(n)$ 。同样，“数组尾插 $O(1)$ ”也要注明是容量足够时的实际成本，或动态扩容策略下的摊还成本。

数组可以承载链式语义

数组和链表并非互斥。前面的对象池已经展示了组合方式：对象物理上放在数组中，逻辑顺序由 next 下标决定。它保留集中分配和较好局部性，同时允许 $O(1)$ 地改链接。代价是池容量、空闲槽位和下标失效都要由实现者管理。

堆则走了另一条路：利用完全二叉树的形状约束，连 next 下标都不保存，直接用算术推导父子位置。结构越规则，数组越能消除指针元数据；结构越不规则、节点越常独立移动，显式链接越自然。

用问题清单做决定

遇到新场景时，可以依次问：

是否频繁按下标读取，或需要二分查找？如果是，数组通常占优。
元素是否经常在中间插删？这些操作发生前，程序是否已经持有目标位置？
是否需要稳定地址或稳定句柄？数组搬迁能否通过间接句柄解决？
顺序扫描是否是主要热点？连续布局带来的缓存收益可能比复杂度符号更明显。
元素数量变化有多剧烈？是否接受偶发搬迁，还是必须限制单次延迟？
空间更看重紧凑，还是更看重避免重新分配？

最后把操作频率代入，而不是只比较某一个操作的最坏复杂度。一个读取远多于修改的集合，通常值得为连续存储付出偶发移动；一个不断拆接节点且需要稳定引用的结构，链式表示可能更合适。若工作负载同时需要两类能力，可以使用分块数组、索引池或稳定句柄，把物理布局与逻辑关系分开。

小测

链表删除一个给定键的元素总是 O(1)，因为删除只需修改相邻指针。

下列哪些场景通常更适合优先考虑数组或基于数组的表示？