数组Array

连续存储元素，通过下标直接访问。

核心约束: 元素位置可由起始地址、元素宽度和下标计算。
适用问题: 顺序扫描、紧凑存储、频繁按位置访问。
边界与取舍: 扩容和中间移动可能昂贵；动态数组追加通常为摊还 $O(1)$ 。

下标 i 直接定位元素：地址 = 起始地址 + i × 元素宽度。

常见操作#

n 为元素数；元素宽度固定，单次复制或比较按常数成本计算。

操作	时间复杂度	条件与说明
按下标读取 / 覆盖	$O(1)$	下标有效，元素连续存储。
按值查找	$O(n)$	未排序数组顺序查找的最坏情况；有序数组可用二分查找。
尾部追加	摊还 $O(1)$ ；单次最坏 $O(n)$	动态数组按几何比例扩容；固定数组没有自动扩容操作。
中间插入 / 删除	$O(n)$	保持原顺序时需要移动后续元素；删除末尾通常为 $O(1)$ 。
遍历 / 从 n 个元素构建	$O(n)$	逐个访问或复制元素，不包含元素内部的深复制。

时间与空间#

时间复杂度: 访问 $O(1)$ ；移动元素 $O(n)$
存储空间: $O(n)$

动态数组空间按容量计算；容量与元素数保持常数比例时为 $O(n)$ 。扩容时新旧缓冲区可能短暂共存。

工程中的应用#

7 个案例 · 附源码

nginx·HTTP upstream 配置解析release-1.26.3

用动态数组收集上游服务器配置

nginx 解析 upstream 块时，用 ngx_array_t 连续保存服务器条目；每遇到一条 server 指令便追加一个元素。

附源码片段 · 通信与流量

Linux Kernel·IIO 软件采样缓冲 / kfifov6.12

用环形 FIFO 暂存传感器采样

Linux IIO 的 kfifo 缓冲在采样进入内核与用户态读取之间暂存数据，按先进先出顺序交付采样记录。

队列环形缓冲区数组

附源码片段 · 内存管理

Linux Kernel·BPF verifier / 控制流图检查v6.12

用显式栈遍历 BPF 控制流

Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。

栈深度优先搜索图数组

附源码片段 · 图处理与编译

Git·Index / 暂存区内存索引v2.46.0

在有序索引数组中按文件名定位条目

Git 把内存中的 index 条目指针保存在有序、可增长的数组中，按路径和合并 stage 二分查找位置。

数组二分查找

附源码片段 · 索引与查找

Redis·SDS 动态字符串7.2.0

用显式长度保存包含零字节的字符串

Redis SDS 把字节长度与可用容量放进头部，追加按长度复制，正文允许包含零字节。

数组显式状态与不变量字符串

附源码片段 · 内存管理

CPython·list 动态数组v3.12.0

用预留容量和缩容阈值避免列表反复搬迁

CPython 的 list 把对象指针连续存储，在扩容时适当预留空间，并在占用低于一半前避免缩容。

附源码片段 · 内存管理

CPython·list.sort / sortedv3.13.0

让列表排序利用输入中已有的顺序

CPython 的列表排序识别已有序段，补齐短段，再按 Powersort 策略稳定归并，兼顾局部有序输入与通用排序。

归并排序插入排序二分查找数组

附源码片段 · 检索与计算

基础原理参考资料

Java 21 · ArrayList明确区分下标访问、追加的摊还成本与移动元素的线性成本。