环形数组技巧及实现
raw/articles/2026/05/环形数组技巧及实现
一句话总结
环形数组通过求模（余数）运算在逻辑上实现数组环形化，可将头尾增删元素的时间复杂度优化至 $O(1)$，核心是通过 start 和 end 两个指针维护有效元素区间。
核心原理
- 逻辑环形：数组本身是线性连续内存，通过
%求模运算实现索引循环（如i = (i + 1) % arr.length可无限遍历数组） - 双指针维护：
start指向第一个有效元素（闭区间），end指向最后一个有效元素的下一个位置（开区间），形成左闭右开区间[start, end) - 边界处理：指针移动超出数组边界时，通过求模运算自动回绕到数组另一端，无需数据搬移
时间复杂度优势
| 操作 | 普通数组 | 环形数组 |
|---|---|---|
| 头部增删 | $O(N)$（需搬移元素） | $O(1)$（仅移动 start 指针） |
| 尾部增删 | $O(1)$（ amortized） | $O(1)$ |
| 随机访问 | $O(1)$ | $O(1)$（需通过 start 计算真实索引） |
| 指定索引增删 | $O(N)$（需搬移元素） | $O(N)$（与普通数组一致） |
关键实现细节（Java）
- 区间设计：采用左闭右开区间
[start, end)，初始化start = end = 0时区间无元素，符合直觉 - 指针移动规则：
- 头部添加：
start = (start - 1 + size) % size（先左移再赋值） - 头部删除：先置空再
start = (start + 1) % size - 尾部添加：先赋值再
end = (end + 1) % size - 尾部删除：先左移
end再置空
- 头部添加：
- 自动扩缩容：
- 满时扩容为 2 倍（
size * 2） - 元素数降至容量 1/4 时缩容为 1/2（
size / 2），避免频繁扩缩容
- 满时扩容为 2 倍（
- 泛型支持：Java 中通过
(T[]) new Object[size]绕过泛型数组创建限制
局限性讨论
- 标准库动态数组（如 Java
ArrayList）未采用环形数组，因指定索引的增删操作仍需要 $O(N)$ 数据搬移，与普通数组无差异 - 环形数组更适合频繁头尾操作的场景（如队列实现），通用场景下优势不明显
相关概念
相关实体
- labuladong：算法学习平台作者