理解数组插入中的常见陷阱
在固定大小的数组中，若要在指定索引 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]。
错误分析：
立即学习“Java免费学习笔记（深入）”；
问题出在循环 for(int i = r + 1; i
- i = r + 1 = 3：arrayVetor[3] = arrayVetor[2]。此时 arrayVetor 变为 [1, 2, 3, 3, null, ...]。
- i = 4：arrayVetor[4] = arrayVetor[3]。注意，此时 arrayVetor[3] 已经是 3 了，所以 arrayVetor[4] 也变成了 3。arrayVetor 变为 [1, 2, 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 腾出了位置，并且没有出现重复克隆。
注意事项与优化
数组容量管理： 上述实现假设数组有足够的空间。在实际应用中，如果 size == arrayVetor.length，则数组已满，无法直接插入。通常需要抛出异常或实现动态扩容机制（创建一个更大的新数组，并将旧数组内容复制过去）。
性能考量： 每次在数组中间插入元素都需要移动 O(n) 个元素（其中 n 是插入点之后元素的数量），这在处理大量数据时可能导致性能瓶颈。
-
替代方案：
-
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 等动态数据结构来简化开发和提高效率。
