数组

数组用“位置可以算出来”代替“沿链接寻找位置”。下标 $i$ 不是从头走 $i$ 步的指令，而是参与一次地址计算的数。等宽槽位让所有位置遵循相同公式，因此尾部元素并不比头部元素更难定位。

这也解释了访问与插入的差别。把第 $i$ 个位置的内容改掉，只需使用原槽位；在它前面增加一个位置，却会改变整个后缀的下标。容量足够时，在长度 $n$ 的序列位置 $i$ 插入要搬动 $n-i$ 个原元素，再写入新值，成本为 $\mathrm{\Theta }(n-i+1)$。尾部插入因此便宜，头部插入则必须移动整个序列；“随机访问为常数时间”没有对这些更新作出承诺。

位置和值是两件事 ​

对于 $A=[7,2,9,4,6,1]$，$A[3]=4$，而不是 $3$。执行写入 $A[3]\leftarrow 8$ 后，结果是 $[7,2,9,8,6,1]$，长度仍为 $6$，其余五个位置保持不变。这里下标从零开始；最后一个位置是 $n-1$，$A[n]$ 已超出定义域。

若改为在下标 $2$ 前插入 $8$，结果应是 $[7,2,8,9,4,6,1]$。容量足够时，连续数组仍须把原后缀 $[9,4,6,1]$ 右移：先复制 $A[5]$ 到 $A[6]$，再依次执行 $A[4]\to A[5]$、$A[3]\to A[4]$、$A[2]\to A[3]$，最后写 $A[2]=8$ 并增加长度。

倒序搬迁保持一个清晰的不变量：已经处理的右侧后缀位于最终位置，尚未处理的左侧原值仍完好。如果改为从左向右，第一次 $A[3]=A[2]$ 就覆盖了下一步还要读取的旧 $A[3]=4$。删除一个位置时依赖方向反过来，应从左向右把后缀向前搬。移动方向来自旧值的读取依赖，而不是记忆一条与操作无关的规则。

二维表如何落到一维内存 ​

设二维数组有 $m$ 行、$n$ 列，以行优先方式存储，则

例如 $2\times 3$ 数组的 $(1,2)$ 位置前面有一整行三个槽位，再加本行两个槽位，偏移为 $5s$。列优先表示则是 $b+(jm+i)s$。两个公式表示同一个二维索引集合，但相邻内存位置的方向不同；逐行还是逐列扫描，会因此影响局部性。

数组视图还可能带步长。例如从一个一维数组抽取下标 $0,2,4,\dots$，第 $j$ 个视图元素的地址是 $b+2js$。它仍支持公式定位，却不在底层占据连续相邻的槽位。视图若共享存储，修改其中元素还可能同时改变原数组；这必须由接口明确说明。

循环数组依赖分析理路循环数组依赖分析Loop dependence analysis · Array dependence analysis · 循环携带依赖把有限循环展开为带坐标的赋值实例，按真实存储位置建立三类冲突边，并证明保持这些边足以保持任意初始整数内存。把这项地址约定用于代码变换：先将每次赋值实例的逻辑访问化为对象与槽位，再区分先写后读、先读后写、先写后写三类冲突。不同视图名不能当作互不别名的证据；共享视图会新增约束，使原本合法的循环交换变成数值错误。

等宽的是槽位，不一定是对象内容 ​

字符串数组可以在每个等宽槽位中保存一个引用。读取第 $i$ 个引用仍可为常数时间，但复制或比较整个字符串的成本取决于字符串长度。类似地，任意精度整数的加法不是因为存放在数组里，就自动变成一个单位成本操作。

抽象模型也不替具体语言规定越界行为。检查后报错、返回带失败标记的结果以及不提供安全访问，都属于不同契约。数学表达 $A:[0,n)\to V$ 只说明哪些下标有定义，并没有为 $A[n]$ 指定一个合法值。

长度与容量 ​

动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。另外维护容量 $C\ge n$。前 $n$ 个槽位属于逻辑序列，剩余槽位是预留空间。尾部追加在容量未满时只写入一个槽位；容量满时，通常分配更大区块并复制旧元素。

若容量按倍数增长，从空数组开始连续追加 $N$ 次，扩容复制量由几何和控制。例如翻倍时总复制量小于 $2N$，加上 $N$ 次新元素写入，总代价为 $O(N)$。因此追加的摊还成本为 $O(1)$，但触发扩容的某一次操作仍可能花费 $\mathrm{\Theta }(n)$。中间插入的后缀移动没有被这个论证消除。

数组正确性通常分为两层：抽象层规定读取、写入、长度及失败行为；表示层证明每个合法下标映到正确槽位，并且不破坏其他槽位。带容量的实现还需保持 $0\le n\le C$，视图实现则需保持偏移和步长对应的地址范围。这是抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。与表示不变量的一次具体配合。

与链表理路链表Linked list通过节点引用保存序列的存储结构；明确前驱、尾指针、节点身份与局部插删的复杂度条件。相比，数组擅长按位置访问和连续扫描；链表在已经持有合适节点引用时，可以通过局部链接修改完成部分插入删除。链表的“局部修改快”不包括找到第 $i$ 个节点的时间，数组的“访问快”也不包括自动维护任意有序位置的时间。

二叉堆理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。进一步利用规则形状，把节点关系编码为下标关系；前缀和理路前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。利用顺序扫描，把区间聚合转化为少数位置的读取。两者节省工作的方式不同，但都建立在位置语义明确、访问契约可靠的基础上。