如何在数组中间添加元素？

Question

我正在尝试创建一个名为insertAt的方法，它接受三个参数（int index，int n，int value）。如果我在[12,42,8,934]的数组上调用list.insertAt(2,4,98)，它现在应该存储[12, 42, 98, 98, 98, 98, 8, 934]。

其中，int index是我开始放置值的位置，int n是值的数量，int value是我想要放置的实际值或数字。我正在ArrayIntList类中编写这个方法。

public class ArrayIntList {
    private int[] elementData; // list of integers
    private int size;          // current # of elements in the list 
}

我尝试使用下面的方法，但我仍然不知道缺少了什么。如果你们能帮我解决问题，我将非常感激！

public void insertAt(int index, int n, int value) {
    if (index < 0 || index > size || n < 0) {
        throw new IllegalArgumentException();
    }
    size = size + n;
    for (int i = 0; i < n; i++) {
        elementData[(size - 1) - i] = elementData[(size - n) + i];
        elementData[n + i] = value;
    }
}

- Niko

---

我建议您阅读https://ericlippert.com/2014/03/05/how-to-debug-small-programs/，以获取一些关于如何调试代码并找出问题的技巧。 - Code-Apprentice

正如其他人所说，您无法更改数组的长度。但是您可以使用List（https://docs.oracle.com/javase/7/docs/api/java/util/List.html）。在java.util中有几个List接口的实现，我不知道哪一个最好。 - David Knipe

Answer 1

在示例中，您拥有的数组仅包含4个值，但您尝试添加4个额外的值。这是不可能的，因为数组具有固定长度。因此，您必须创建一个新的长度为size + n的数组：

int[] newElements = new int[size + n];

然后，您需要将旧数组中从0到index的所有元素以及index到size的元素复制到新数组中：

System.arraycopy(elementData, 0, newElements, 0, index);
System.arraycopy(elementData, index, newElements, index + n, size - index);

然后，您需要将新元素n次插入数组中：

Arrays.fill(newElements, index, index + n, value);

最后，您需要将新数组重新分配给旧实例，并设置新大小：

elementData = newElements;
size += n;

我使用了一些JDK提供的辅助方法，比如System.arraycopy，它的签名如下：

void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

该方法将从srcPos到srcPos+length范围内的元素复制到destPos到destPost+length范围内的dest数组中。

Array.fill是一个带有以下签名的好用的辅助函数:

void fill(int[] a, int fromIndex, int toIndex, int val)

它使用值val填充从fromIndex到toIndex的数组a

- Lino

Answer 2

Lino的回答是正确的。此外，对于这种工作，您可能应该使用除简单数组之外的其他数据结构。

当您需要更多灵活性时，请使用Java集合框架。

List

List接口按顺序跟踪元素。

Java集合仅存储对象，而不是原始类型。因此，我们必须使用包装类。在您的情况下，使用Integer而不是int。在大多数情况下，Java的自动装箱功能将处理。

ArrayList

< p > List 的一个实现是 ArrayList。这个类由简单的数组支持。因此，在中间插入会导致Lino描述的繁琐过程。但至少该类正在工作，使用已经经过彻底测试的代码，而不是像你或我编写的代码。

List< Integer > integers = new ArrayList<>() ;
integers.add( 7 ) ;   // Add first element to the empty list.
integers.add( 42 ) ;  // Append to the end of the list.
integers.add( 1 , Integer.valueOf( 1999 ) ) ;   // Insert in the middle. Using zero-based index counting. So `1` means the second item.
integers.

在实践中，我会使用序号2，并将索引号减1。

integers.add( 2-1 , Integer.valueOf( 1999 ) ) ; // Insert. Do math to convert from ordinal number (2, the second position) to index number (1).

LinkedList ⬅ 更快！

更好的选择是使用实现了List接口的LinkedList类。数组在内存中将项紧密地打包在一起，而链表中的项分别浮动在内存中，每个项跟踪后续项的内存位置。

所以在中间插入的代价要小得多：只需将前一个项目更改为指向新项目，而新项目指向后继项目。无需重建列表或移动一堆项目。

通过调用LinkedList::add（index，element）来在 LinkedList 中插入，其中索引是从零开始的位置计数器，而元素是您要插入的对象。

请注意 List 上的{{link2：addAll（int index，Collection<？extends E> c）}}方法。生成多个数字的方法可以生成一个列表，然后将该列表插入目标列表。使用这种单个插入方法比多个插入快得多，因为遍历链表以查找插入位置是昂贵的。

// Make a list of values to be inserted into the main list.
int count = 3 ; 
List< Integer > inserts = new ArrayList<>( count );
for (int i = 0; i < count; i++) {
    inserts.add( 98 ) ;
}
// Insert into main list.
integers.add( 2-1 , inserts ) ;  // Do math to convert from ordinal number (2, the second position) to index number (1).

如何选择哪个List：

• 如果您需要频繁遍历或根据位置编号跳转到列表中的特定元素，则使用ArrayList。因为元素是连续的，所以按位置跳转非常便宜。
• 如果您需要频繁插入或删除元素，请使用LinkedList。因为元素彼此相连，插入/删除只影响一个元素，因此非常便宜。

还有许多其他可用的List实现，一些与Java捆绑在一起，其他则来自第三方。通常，ArrayList和LinkedList是主要的工作马，由大多数人在大多数工作中使用。

- Basil Bourque

---

非常好的回答，提到List是一个很好的补充，因为它通常可以让你的生活更轻松。我可以建议在您最新的代码片段中进行小改进，使用Collections.nCopies(n, value)就可以完成与您的for循环几乎相同的功能。 - Lino

Answer 3

你需要一个数组的副本，在插入索引之前复制第一个元素，添加新元素N次并添加最后一个元素。

public void insertAt(int index, int n, int value) {
if (index < 0 || index > size || n < 0) {
    throw new IllegalArgumentException();
}
size = size + n;

int[] elementDataTemp = new int[elementData.length + n];

// copy first elements
for (int i = 0; i < index; i++) {
    elementDataTemp[i] = elementData[i];
}

// add new elements
for (int i = 0; i < n; i++) {
    elementDataTemp[index + i] = value;
}

// copy last elements
for (int i = index; i < elementData.length; i++) {
    elementDataTemp[ n + i ] = elementData[i];
}

// save temp array
elementData = elementDataTemp;
}

- imperezivan

Answer 4

你可以用多种方式来实现这个：

1. 将 n - arrayLenght 个元素向上移动一个位置
2. 在 N 中插入新元素

- JpersaudCodezit