数据结构与算法 / 系统课时
数组的插入与删除
数组的插入与删除
数组保持有效元素连续排列,因此中间插入和删除不能只修改一个位置。本课使用固定容量顺序表,完成边界检查、元素搬移、长度维护和结果验证。
学习目标
- 区分底层容量
capacity与有效长度size。 - 掌握插入右移、删除左移的正确方向和下标范围。
- 能分析不同位置操作的搬移次数与时间复杂度。
容量、长度与合法下标
底层数组的 length 表示可容纳的最大元素数,size 表示当前有效元素数,并始终满足 0 <= size <= capacity。读取和删除只能访问 0 <= index < size,插入还允许 index == size,因为该位置表示尾部追加。
插入前还要确认 size < capacity。若数组已满,右移第一个元素时就可能写入 elements[size] 并发生越界。
搬移方向决定数据是否安全
在下标 index 插入元素时,应从最后一个有效元素开始向右搬移。若从前向后复制,刚写入的新值会覆盖尚未保存的数据。
删除时则从目标位置开始向左搬移,用后一个元素依次填补前一个空位。删除完成后减少 size;若底层保存对象,还应把原尾部位置设为 null,避免继续持有无效引用。

插入需要搬移 size - index 个元素,删除需要搬移 size - index - 1 个元素。头部和中间操作最坏为 ;容量足够时,尾部插入和尾部删除不需搬移,可为 。
主示例:固定容量顺序表
下面的 Java 17 示例把插入、删除和边界检查封装在一个类中。toString 只展示有效区间,避免把底层数组的默认值误认为业务数据。
import java.util.Arrays;
public class ArrayInsertDeleteDemo {
public static void main(String[] args) {
FixedIntList list = new FixedIntList(8);
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.insert(2, 25);
System.out.println("插入后: " + list);
int removed = list.remove(1);
System.out.println("删除元素: " + removed);
System.out.println("删除后: " + list);
System.out.println("size=" + list.size());
}
static final class FixedIntList {
private final int[] elements;
private int size;
FixedIntList(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("容量必须大于 0");
}
elements = new int[capacity];
}
void add(int value) {
insert(size, value);
}
void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("插入位置越界");
}
if (size == elements.length) {
throw new IllegalStateException("数组已满");
}
// 从后向前右移,避免覆盖尚未搬移的数据。
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = value;
size++;
}
int remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("删除位置越界");
}
int removed = elements[index];
// 从前向后左移,保持有效区间连续。
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
elements[size - 1] = 0;
size--;
return removed;
}
int size() {
return size;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
}
}编译并运行:
javac ArrayInsertDeleteDemo.java
java ArrayInsertDeleteDemo预期输出:
插入后: [10, 20, 25, 30, 40, 50]
删除元素: 20
删除后: [10, 25, 30, 40, 50]
size=5边界与常见错误
插入判断写成 index >= size 会错误地禁止尾部追加,正确上界是 index > size。删除循环若写成 i < size,最后一次会读取 elements[size],可能越界。
另一个常见错误是忘记更新 size。数据虽然已经移动,但后续读取、插入和打印仍会使用错误的有效范围。对象数组删除后未清空尾部引用,则可能延长对象生命周期。