数据结构与算法 / 系统课时
静态数组
静态数组
静态数组用一段固定长度的连续空间保存同类型元素。本课将从内存布局出发,解释下标为何能实现常数时间访问,并通过一个固定容量数组类演示插入、删除、容量限制和下标边界。
学习目标
- 能够区分数组的容量
capacity与有效元素数量size。 - 能够解释索引访问、插入和删除的时间复杂度来源。
- 能够正确处理越界、满容量和元素搬移问题。
内存布局与索引访问
静态数组在创建时就确定容量,元素按固定宽度连续排列。若首元素地址为 base,每个元素占用 w 个字节,则下标 i 的地址可直接计算为:
在固定宽度、可随机访问的数组模型中,读取或写入合法下标是 。Java 规范保证数组长度固定与下标检查,程序不直接计算对象地址。引用数组的槽位保存引用,所指对象不要求彼此相邻。连续遍历通常有利于局部性,实际布局和缓存由实现决定。

数组对象通常同时维护两个量:
| 名称 | 含义 | 合法范围 |
|---|---|---|
capacity |
底层数组可容纳的最大元素数 | 创建后固定 |
size |
当前有效元素数量 | 0..capacity |
| 访问下标 | 已存在元素的位置 | 0..size - 1 |
| 插入下标 | 新元素可插入的位置 | 0..size |
直接访问任意有效元素为 。在中间插入时,需要把插入点及其后的元素向右搬移;删除时,需要把删除点之后的元素向左搬移。因此头部或中间插入、删除的最坏时间复杂度为 ,尾部插入和删除在无需扩容时可达到 。
插入、删除与边界规则
本例先检查插入下标,再检查容量。有效长度为 n 时,在 i 处插入需要向右搬 n−i 个槽位,删除 i 则向左搬 n−i−1 个槽位。成功后才更新 size。必须从后向前搬移,否则较早写入的新位置会覆盖尚未复制的旧元素。
删除操作应先保存待删除值,再从前向后搬移后续元素,最后清理原末尾位置并减少 size。对于基本类型数组,清理尾部主要用于保持状态易于观察;对于对象数组,清空引用还能避免无意延长对象生命周期。
边界判断需要区分访问与插入。访问下标等于 size 时越界,但插入下标等于 size 表示在尾部追加,是合法操作。数组已满时继续插入必须明确失败,不能静默覆盖已有元素。
完整实现与验证
下面的 Java 17 示例实现一个固定容量的整数数组。它不自动扩容,便于观察静态数组的核心行为。
import java.util.Arrays;
public class StaticArrayDemo {
private static final class FixedIntArray {
private final int[] elements;
private int size;
private FixedIntArray(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("容量必须大于 0");
}
this.elements = new int[capacity];
}
private int size() {
return size;
}
private int capacity() {
return elements.length;
}
private int get(int index) {
checkElementIndex(index);
return elements[index];
}
private void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("非法插入下标: " + index);
}
if (size == elements.length) {
throw new IllegalStateException("数组已满");
}
// 从后向前搬移,避免覆盖仍需复制的元素。
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = value;
size++;
}
private int delete(int index) {
checkElementIndex(index);
int removed = elements[index];
// 删除点之后的元素依次左移。
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
elements[size - 1] = 0;
size--;
return removed;
}
private int[] toArray() {
return Arrays.copyOf(elements, size);
}
private void checkElementIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("非法访问下标: " + index);
}
}
}
public static void main(String[] args) {
FixedIntArray array = new FixedIntArray(6);
array.insert(0, 10);
array.insert(1, 20);
array.insert(2, 30);
System.out.println("初始: " + Arrays.toString(array.toArray()));
System.out.println("下标 1 的元素: " + array.get(1));
array.insert(1, 15);
System.out.println("在下标 1 插入 15: " + Arrays.toString(array.toArray()));
int removed = array.delete(2);
System.out.println("删除下标 2 的元素: " + removed);
System.out.println("删除后: " + Arrays.toString(array.toArray()));
System.out.println(
"size = " + array.size() + ", capacity = " + array.capacity()
);
}
}运行命令:
javac -encoding UTF-8 StaticArrayDemo.java
java StaticArrayDemo预期输出
初始: [10, 20, 30]
下标 1 的元素: 20
在下标 1 插入 15: [10, 15, 20, 30]
删除下标 2 的元素: 20
删除后: [10, 15, 30]
size = 3, capacity = 6常见错误包括把 capacity 当成有效元素数量、在插入时从前向后搬移、允许 get(size)、数组满后继续写入,以及删除后忘记更新 size。验证时覆盖空状态、单元素、头尾搬移、非法下标和满容量。检查失败前后 size 与已有元素一致。这个包装类要求容量为正,但 Java 本身允许零长度数组。toArray 创建有效区间的副本,时间与额外数组空间都随 size 增长。
本课总结
- 静态数组依靠连续内存和地址计算实现 索引访问。
capacity表示固定容量,size表示当前有效元素数量,两者不能混用。- 中间插入和删除需要搬移元素,最坏时间复杂度为 。
下一课预告
后续将继续学习动态数组如何通过扩容突破固定容量限制,并分析偶发复制成本为何能够被多次低成本追加操作摊平。