我需要在索引 i 处的 ArrayList 中插入 Person 类型的元素（我自己定义的类）
我知道我可以使用add(int index, E element).
但是有没有任何有效的方法可以做到这一点，因为在我的列表中平均需要大约 1.5 毫秒（收集超过 1000 次插入然后平均的数据）。
问问题
12715 次
3 回答
10
如果您的任务是更密集的插入/删除，您始终可以使用java.util.LinkedList。
- ArrayList 的大小有限。每次添加元素时，Java 都会确保它能够适应 - 因此它会增长 ArrayList。如果 ArrayList 增长得更快，就会发生大量的数组复制。
- LinkedList 只是将元素添加到正确的位置（链接周围的节点），而不需要增长和复制整个 ArrayList。
- LinkedList 的缺点是在您搜索元素时。由于它没有索引，它必须从列表的开头遍历到结尾才能找到一个项目。
对于LinkedList：
- 得到是 O(n)
- 添加是 O(1)
- 删除是 O(n)
- Iterator.remove 是 O(1)
对于ArrayList：
- 得到是 O(1)
- add 是 O(1) 摊销，但 O(n) 最坏情况，因为必须调整数组大小和复制
- 删除是 O(n)
于 2013-06-17T11:32:43.360 回答
0
这种插入发生在 O(n) 中，因为它必须向下移动所有元素，最坏的情况是它会将每个元素向下移动。（更正的 java 说它是 O(n) 因为他们使用数学公式来插入）
如果您想要快速插入，请将其添加到数组列表的末尾或使用恒定时间的哈希图。
插入hashmap：HashMap peopleMap = new Hashmap.....
peopleMap.put(person.name, person); //（或任何你想跟踪的）
这会将键设置为人员姓名，并将值设置为人员。
您还可以尝试使用带有键的哈希图（您要跟踪的 ehatver）并评估此人在持有人数组中的索引。插入是 O(i)，查找 O(i)，您也可以对其进行排序（我将把它作为练习留给读者）
如果这样做的全部目的是排序，那么为简单起见，您可以插入优先队列（nLogn），然后将所有内容弹出到数组中，这将为您提供排序数组
于 2013-06-17T11:20:57.703 回答
-1
如果您添加使用
arryListInstance.add(positionIndex, Object);
该对象将在将现有对象筛选 1 个位置后添加。因此，此操作的平均情况变为O(n)。
虽然简单的添加
arryListInstance.add(positionIndex, Object);
将对象添加到 arrayListInstance 的末尾。在最好的情况下，这个操作是O(1)，但在最坏的情况下，当达到最大容量时它变成O(n)：因为内部创建了一个新的 ArrayList 实例并且所有内容都复制到那里。
您面临这个问题是因为可以避免第一个原因的两个原因之一：
- 您没有为 ArrayList 对象定义足够的初始容量。因此，在每个arrayListInstance.add(positionIndex, object)之前，正在创建一个具有增加容量的新 arrayListInstance，然后复制原始列表中的现有元素，最后执行添加。如果您确切知道要通过此列表处理多少数据并相应地定义初始容量（与可能的元素数量相同），则可以避免这种情况。如果您无法预测初始容量，那么最好批量处理数据。
- 在除最后一个位置之外的任何位置的每次插入后都会筛选现有元素。这是不可避免的。因此，如果positionIndex不是 arrayList 的最后一个索引， arrayListInstance.add(positionIndex, object)将在O(n)时间内执行。即使您使用LinkedList您也无法实现恒定时间添加操作，该操作将元素添加到列表中除最后一个元素之后的索引处。
于 2013-06-17T11:45:36.253 回答