Java数组元素右移插入方法

理解数组插入中的常见陷阱

在固定大小的数组中，若要在指定索引 r 处插入一个新元素 o，通常需要将从 r 位置开始的所有现有元素向右移动一位，为新元素腾出空间。然而，一个常见的错误是采用向前遍历的方式进行元素右移，这会导致意料之外的数据重复。

考虑以下不正确的实现方式：

public class MyArray {
    private Object[] arrayVetor;
    private int size; // 假设有一个跟踪实际元素数量的字段

    public MyArray(int capacity) {
        arrayVetor = new Object[capacity];
        size = 0;
    }

    // 假设此方法在数组有足够空间且r在有效范围内时调用
    public void insertAtRank(int r, Object o) {
        // 错误的右移逻辑
        for (int i = r + 1; i < arrayVetor.length; i++) {
            arrayVetor[i] = arrayVetor[i - 1];
        }
        this.arrayVetor[r] = o;
        // size++; // 如果需要，更新实际元素数量
    }

    // 辅助方法，用于打印数组内容
    public void printArray() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arrayVetor.length; i++) {
            sb.append(arrayVetor[i]);
            if (i < arrayVetor.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

当我们使用上述 insertAtRank 方法进行一系列操作时，例如：

MyArray arrayVetor = new MyArray(10); // 假设数组容量为10
arrayVetor.insertAtRank(0, "1"); // 数组: [1, null, null, ...]
arrayVetor.insertAtRank(1, "2"); // 数组: [1, 2, null, ...]
arrayVetor.insertAtRank(2, "3"); // 数组: [1, 2, 3, null, ...]
arrayVetor.insertAtRank(3, "4"); // 数组: [1, 2, 3, 4, null, ...]
arrayVetor.insertAtRank(2, "5"); // 尝试在索引2插入"5"
arrayVetor.printArray();

预期的结果可能是 [1, 2, 5, 3, 4, null, null, null, null, null]。然而，实际输出却是 [1, 2, 5, 3, 3, 3, 3, 3, 3, 3]。

错误分析：

问题出在循环 for(int i = r + 1; i < arrayVetor.length; i++) { arrayVetor[i] = arrayVetor[i - 1]; }。当 r 为 2，且 arrayVetor 为 [1, 2, 3, 4, null, ...] 时：

1. i = r + 1 = 3：arrayVetor[3] = arrayVetor[2]。此时 arrayVetor 变为 [1, 2, 3, 3, null, ...]。
2. i = 4：arrayVetor[4] = arrayVetor[3]。注意，此时 arrayVetor[3] 已经是 3 了，所以 arrayVetor[4] 也变成了 3。arrayVetor 变为 [1, 2, 3, 3, 3, ...]。
3. 此过程将持续到数组末尾，导致 arrayVetor[2]（即值 3）被复制到其后的所有位置，从而覆盖了原本位于 arrayVetor[3] 的值 4。

简而言之，向前遍历会导致一个元素的值在尚未被移动到其最终位置之前，就被其左侧的元素所覆盖，进而导致左侧元素的值被重复复制。

正确实现元素右移：反向遍历法

为了正确地实现元素右移，我们应该从数组的末尾开始，逐步向前遍历到目标插入位置 r 的右侧一位 (r + 1)。这样，每个元素在被其左侧元素覆盖之前，都能先将其自身的值复制到其右侧的新位置。

原理阐述：

假设要在索引 r 插入新元素。我们需要将 arrayVetor[arrayVetor.length - 2] 移动到 arrayVetor[arrayVetor.length - 1]，将 arrayVetor[arrayVetor.length - 3] 移动到 arrayVetor[arrayVetor.length - 2]，依此类推，直到将 arrayVetor[r] 移动到 arrayVetor[r + 1]。通过从右向左移动，可以确保原始值在被覆盖之前总能被正确地复制。

正确代码示例：

public class MyArray {
    private Object[] arrayVetor;
    private int size; // 跟踪实际元素数量

    public MyArray(int capacity) {
        arrayVetor = new Object[capacity];
        size = 0;
    }

    /**
     * 在指定位置r插入元素o，并将后续元素右移。
     * @param r 插入位置的索引。
     * @param o 要插入的元素。
     * @throws IndexOutOfBoundsException 如果r超出有效范围。
     * @throws IllegalStateException 如果数组已满。
     */
    public void insertAtRank(int r, Object o) {
        if (r < 0 || r > size) { // r可以等于size，表示在末尾添加
            throw new IndexOutOfBoundsException("Invalid index: " + r);
        }
        if (size == arrayVetor.length) {
            throw new IllegalStateException("Array is full, cannot insert new element.");
        }

        // 正确的右移逻辑：从后向前遍历
        for (int i = size; i > r; i--) { // 注意：i从当前size开始，移动到r+1
            arrayVetor[i] = arrayVetor[i - 1];
        }
        this.arrayVetor[r] = o;
        size++; // 插入成功后，实际元素数量增加
    }

    // 辅助方法，用于打印数组内容（仅打印实际有效元素）
    public void printArray() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) { // 只遍历到size
            sb.append(arrayVetor[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        System.out.println(sb.toString());
    }

    // 辅助方法，用于打印整个底层数组（包括null部分）
    public void printFullArray() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arrayVetor.length; i++) {
            sb.append(arrayVetor[i]);
            if (i < arrayVetor.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

示例与预期结果

使用上述修正后的 MyArray 类进行操作：

MyArray arrayVetor = new MyArray(10); // 假设数组容量为10

System.out.println("--- 初始插入 ---");
arrayVetor.insertAtRank(0, "1"); // size=1, array: [1, null, ...]
arrayVetor.printFullArray();
arrayVetor.insertAtRank(1, "2"); // size=2, array: [1, 2, null, ...]
arrayVetor.printFullArray();
arrayVetor.insertAtRank(2, "3"); // size=3, array: [1, 2, 3, null, ...]
arrayVetor.printFullArray();
arrayVetor.insertAtRank(3, "4"); // size=4, array: [1, 2, 3, 4, null, ...]
arrayVetor.printFullArray();

System.out.println("\n--- 在索引2插入'5' ---");
arrayVetor.insertAtRank(2, "5"); // size=5
arrayVetor.printFullArray();
// 预期输出: [1, 2, 5, 3, 4, null, null, null, null, null]

输出结果：

--- 初始插入 ---
[1, null, null, null, null, null, null, null, null, null]
[1, 2, null, null, null, null, null, null, null, null]
[1, 2, 3, null, null, null, null, null, null, null]
[1, 2, 3, 4, null, null, null, null, null, null]

--- 在索引2插入'5' ---
[1, 2, 5, 3, 4, null, null, null, null, null]

可以看到，通过反向遍历，元素 3 和 4 被正确地向右移动，为 5 腾出了位置，并且没有出现重复克隆。

注意事项与优化

1. 数组容量管理： 上述实现假设数组有足够的空间。在实际应用中，如果 size == arrayVetor.length，则数组已满，无法直接插入。通常需要抛出异常或实现动态扩容机制（创建一个更大的新数组，并将旧数组内容复制过去）。

2. 性能考量： 每次在数组中间插入元素都需要移动 O(n) 个元素（其中 n 是插入点之后元素的数量），这在处理大量数据时可能导致性能瓶颈。

3. 替代方案：

   • System.arraycopy()： Java提供了 System.arraycopy() 方法，它是一个本地方法，通常比手动循环更高效。可以使用它来批量移动元素。

     // 使用 System.arraycopy() 的 insertAtRank 方法
     public void insertAtRankOptimized(int r, Object o) {
         if (r < 0 || r > size) {
             throw new IndexOutOfBoundsException("Invalid index: " + r);
         }
         if (size == arrayVetor.length) {
             throw new IllegalStateException("Array is full, cannot insert new element.");
         }
     
         // 将从r位置开始的size - r个元素向右移动一位
         System.arraycopy(arrayVetor, r, arrayVetor, r + 1, size - r);
     
         this.arrayVetor[r] = o;
         size++;
     }

   • java.util.ArrayList： 如果需要频繁地在任意位置插入或删除元素，并且不希望手动管理数组大小和元素移动，ArrayList 是更好的选择。它在底层实现了动态数组，并自动处理元素的移动和扩容，尽管其内部也可能使用类似 System.arraycopy() 的机制。

总结

在Java固定大小数组中，向指定位置插入元素并实现后续元素右移时，务必采用从数组末尾向指定插入位置反向遍历的方式。这种方法能够确保每个元素在被覆盖之前，其值已经被正确地复制到新的位置，从而避免数据重复和丢失。对于性能敏感的应用，可以考虑使用 System.arraycopy() 进行优化，或者直接使用 java.util.ArrayList 等动态数据结构来简化开发和提高效率。