数组
数组把相同类型的元素槽位按下标排列，适合随机访问和顺序扫描。本文区分固定长度数组与基于数组的动态容器；对象数组连续存放的是引用槽位，对象本身未必相邻。
1. 面试核心
先记住这几条，再读正文- 按下标访问为 O(1)，按值查找在无序数组中为 O(n)。
- 保持顺序的中间插入、删除需要移动后续元素，最坏 O(n)。
- 动态数组按倍数扩容时，尾部追加摊还 O(1)，单次扩容仍是 O(n)。
2. 下标与连续槽位
固定大小元素可以用“起始地址 + 下标 × 槽位大小”定位，因此访问第 100 个元素不必先经过前 99 个。顺序遍历也便于利用 CPU 缓存，但这不保证引用所指对象的访问同样连续。
int[] values = {4, 7, 9};
values[1] = 8;
System.out.println(values[1]); // 8
写入替换了下标 1 的值，数组长度仍为 3。Java 下标从 0 开始，访问下标 3 会抛出越界异常。数组中的“空闲槽位”和业务值 0 需要分开记录，不能用数值 0 判断元素是否存在。
3. 插入与扩容
在 [4, 8, 9] 的下标 1 插入 6 并保持顺序，需要先让 8、9 后移，再写入 6。若容量已满，还要先分配新数组。删除中间元素同样需要把后缀前移。
假设动态容器容量每次翻倍，增长到 n 个元素前搬迁量约为 1 + 2 + 4 + …，总量为 O(n)，所以 n 次尾部追加的总成本为 O(n)。若每次只增加一个槽位，反复复制可能累计到 O(n²)。具体容器的增长比例由实现决定。
4. 使用边界
随机访问、固定大小表格和批量扫描适合数组。频繁中间插入时，先估算移动成本；不要仅凭这个需求就改用链表，因为定位链表插入点也可能需要 O(n)。
如果不要求保留顺序，可以把末尾元素覆盖到待删位置，实现 O(1) 删除，但外部保存的下标含义会改变。可变容量、顺序保证和下标稳定性是三个不同要求。
5 · 面试题卡片
5.1 数组中间删除为什么通常是 O(n)，在什么条件下可以降到 O(1)？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：保序删除的移动成本、已知下标的前提，以及放弃顺序后的替换方法。
参考回答
保序删除需要把后续元素前移，最坏移动 n−1 个元素。若允许改变顺序，且已知待删下标，可以用末尾元素覆盖该位置，再减少有效长度；这只做常数次操作。若还需按值搜索待删元素，查找本身仍可能是 O(n)。