在Java中高效地在给定索引处向ArrayList中添加元素

Question

我需要在索引i处将一个类型为Person的元素（我的自定义类）插入ArrayList中。

我知道可以使用add(int index, E element)。

但是是否有更有效的方法来做到这一点，因为在我的列表中，平均需要1.5毫秒（收集1000个插入数据然后求平均值）？

- learner

---

相比于ArrayList，LinkedList更适合用于列表的插入/删除操作。 - Guillaume Polet

@GuillaumePolet，您说插入不需要在LinkedList中复制数据是正确的；但是查找索引n将是一个O(n)操作，因为您必须遍历整个列表。我怀疑System.arraycopy可能具有更快的常数因子，因此仍然更快。 - Boris the Spider

@b.pradeep ArrayList 已经在内部使用了 System.arraycopy - 没有理由让你自己使用它。 - Boris the Spider

看起来你只提供了部分需求。你需要进行二分查找来找到插入点吗？那么这是一个已排序的列表吗？那么我认为你需要使用不同的数据结构。考虑使用TreeSet。 - Steve McLeod

@BoristheSpider，ArrayList 的 indexOf 实现也是 O(n)。请参考这个答案进行全面比较。我的陈述只涉及添加/删除操作。 - Guillaume Polet

Answer 1

如果您的任务更多涉及插入/删除操作，您可以随时使用java.util.LinkedList。

• ArrayList有限制的大小。每次添加一个元素，Java都会确保它能够适合-因此它会增加ArrayList的大小。如果ArrayList增长得更快，就会发生大量的数组复制。
• LinkedList只是将元素添加到正确的位置(链接周围的节点)，而不是增加并复制整个ArrayList。
• LinkedList的缺点在于查找元素时。由于它没有索引，必须从列表的开头到末尾遍历以查找项。

对于LinkedList:

• get为O(n)
• add为O(1)
• remove为O(n)
• Iterator.remove为O(1)

对于ArrayList:

• get为O(1)
• add为O(1)摊销，但最坏情况下为O(n)，因为必须调整数组大小并复制
• remove为O(n)

- darijan

---

我需要先进行二分查找来找到索引，然后再插入数据。但我无法使用Linkedlist，因为我需要在TableView中插入数据，而TableView使用的是ArrayList作为底层模型（ObservableList<S>）。 - learner

你能更具体地说明一下TableView吗？ - darijan

这是这个答案的副本（原答案更加详细），链接在此：https://dev59.com/Y3RC5IYBdhLWcg3wW_tk - Guillaume Polet

@GuillaumePolet +1 我在提问之前已经查看了那个答案。 - learner

Answer 2

这个插入操作的时间复杂度是O(n)，因为它必须将所有元素下移，最坏情况下会将每个元素都下移。（修正后的Java表示它是O(n)，因为他们使用了一个数学公式来进行插入）

如果你想要快速插入，可以将其添加到ArrayList的末尾或使用HashMap，因为它是常数时间。

在HashMap中插入：

HashMap peopleMap = new Hashmap.....

peopleMap.put(person.name, person); //(或者你想要跟踪的任何内容)

这将把键设置为人名，值设置为person。

你也可以尝试使用带有键（你想要跟踪的任何内容）和值（人员在持有人数组中的索引）的HashMap。插入是O(i)，查找是O(i)，你还可以对其进行排序（我将把这留给读者作为练习）。

如果整个目的是为了排序，那么为了简单起见，你可以将其插入到优先队列中（nLogn），然后将所有内容弹出到数组中，这将给你一个排序后的数组。

- William Falcon

---

怎么可能是O(n^2)？我需要移动整个数组，我会从末尾开始。我猜这就是System.arraycopy的工作原理，它非常快速。 - learner

put(index, value); 其中 index 是键。 - Andrea Ligios

@waf，但这实际上取决于实现方式，如果你所说的总是正确的，那么插入排序将是O(n^3)，不是吗？ - learner

刚刚阅读了Java实现的细节，由于它们用于插入的某个公式，它是O(n)。 - William Falcon

Answer 3

如果你使用“using”关键字

arryListInstance.add(positionIndex, Object);

在筛选现有对象1个位置后，该对象将被添加。因此，这个操作的平均情况为O(n)。

而简单添加

arryListInstance.add(positionIndex, Object);

将对象添加到arrayListInstance的末尾。在最好的情况下，此操作的时间复杂度为O(1)，但在最坏的情况下，当达到最大容量时，它变为O(n)：因为内部会创建一个新的ArrayList实例，并将所有内容复制到其中。

您面临这个问题是因为两个原因中的其中一个，第一个可以避免：

1. 你没有为 ArrayList 对象定义足够的初始容量。因此，在每个 arrayListInstance.add(positionIndex, object) 之前，都会创建一个新的 arrayListInstance，使用增加容量，然后将原始列表中的现有元素复制，最后执行add。如果您知道要通过此列表处理多少数据，并相应地定义初始容量（与可能元素的数量相同），则可以避免这种情况。如果您无法预测初始容量，则最好分批处理数据。
2. 除了最后一个位置外的每个插入都会导致现有元素的移动。这是不可避免的。因此，如果 positionIndex 不是 arrayList 的最后一个索引，则 arrayListInstance.add(positionIndex, object) 将以 O(n) 时间执行。即使你使用 LinkedList，也无法实现常数时间添加操作，该操作将元素添加到列表中除最后一个元素之外的索引处。

- Vaibhav Raj

---

你在两种情况下都使用了相同的添加，因此被投了反对票。第二个添加不是“简单”的添加。 - Jerry Destremps

应该使用 arryListInstance.add(Object);。 - anhtuannd