数据结构与算法 / 系统课时

数组的插入与删除

数组的插入与删除

数组保持有效元素连续排列,因此中间插入和删除不能只修改一个位置。本课使用固定容量顺序表,完成边界检查、元素搬移、长度维护和结果验证。

学习目标

  • 区分底层容量 capacity 与有效长度 size。
  • 掌握插入右移、删除左移的正确方向和下标范围。
  • 能分析不同位置操作的搬移次数与时间复杂度。

容量、长度与合法下标

底层数组的 length 表示可容纳的最大元素数,size 表示当前有效元素数,并始终满足 0 <= size <= capacity。读取和删除只能访问 0 <= index < size,插入还允许 index == size,因为该位置表示尾部追加。

插入前还要确认 size < capacity。若数组已满,右移第一个元素时就可能写入 elements[size] 并发生越界。

搬移方向决定数据是否安全

在下标 index 插入元素时,应从最后一个有效元素开始向右搬移。若从前向后复制,刚写入的新值会覆盖尚未保存的数据。

删除时则从目标位置开始向左搬移,用后一个元素依次填补前一个空位。删除完成后减少 size;若底层保存对象,还应把原尾部位置设为 null,避免继续持有无效引用。

数组插入与删除搬移方向

插入需要搬移 size - index 个元素,删除需要搬移 size - index - 1 个元素。头部和中间操作最坏为 O(n)O(n);容量足够时,尾部插入和尾部删除不需搬移,可为 O(1)O(1)。

主示例:固定容量顺序表

下面的 Java 17 示例把插入、删除和边界检查封装在一个类中。toString 只展示有效区间,避免把底层数组的默认值误认为业务数据。

java
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));
        }
    }
}

编译并运行:

bash
javac ArrayInsertDeleteDemo.java
java ArrayInsertDeleteDemo

预期输出:

text
插入后: [10, 20, 25, 30, 40, 50]
删除元素: 20
删除后: [10, 25, 30, 40, 50]
size=5

边界与常见错误

插入判断写成 index >= size 会错误地禁止尾部追加,正确上界是 index > size。删除循环若写成 i < size,最后一次会读取 elements[size],可能越界。

另一个常见错误是忘记更新 size。数据虽然已经移动,但后续读取、插入和打印仍会使用错误的有效范围。对象数组删除后未清空尾部引用,则可能延长对象生命周期。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

数组的插入与删除

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通