java ArrayList vs LinkedList - 插入时间
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12074441/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
ArrayList v.s. LinkedList - inserting time
提问by user1249569
When I run (respectively):
当我运行时（分别）：
package containers;
import java.util.*;
public static void main(String[] args) {
List<Integer> arLst = new ArrayList<Integer>();
List<Integer> lnLst = new LinkedList<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
arLst.add(i);
}
System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
lnLst.add(i);
}
System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}
I get roughly the same executing time. I know that Adding time should be faster for LinkedList. I wonder why.. (It makes sense that both for middle insertinon and last elemnt - since arrays know in O(1) where to insert, unlike LinkedList that has to go through the whole list, as I recall).
我得到大致相同的执行时间。我知道 LinkedList 的添加时间应该更快。我想知道为什么..（对于中间插入元素和最后元素都是有道理的 - 因为数组知道在 O(1) 中插入的位置，不像我记得的 LinkedList 必须遍历整个列表）。
回答by Peter Lawrey
Both lists know where the end of the list is so insertion time is almost the same. I would have expected LinkedList to be slightly slower as it creates a node for every element and uses more memory.
两个列表都知道列表的末尾在哪里，因此插入时间几乎相同。我原以为 LinkedList 会稍微慢一点，因为它为每个元素创建一个节点并使用更多内存。
I get
我得到
TIntArrayList - 141 ms
ArrayList<Integer> - 810 ms
LinkedList<Integer> - 5190 ms.
TIntArrayList doesn't create an object for each element using the cache more efficiently.
TIntArrayList 不会更有效地使用缓存为每个元素创建一个对象。
回答by Mathias Schwarz
Both your lists are ArrayLists... If you change on of them to LinkedListyou won't notice a big difference either. Building an ArrayListthe way you do has amortized complexity of O(1) per insertion.
您的两个列表都是ArrayList...如果您将它们更改为 ，LinkedList您也不会注意到有很大的不同。ArrayList以您的方式构建每个插入的分摊复杂度为 O(1)。
回答by Oscar Perez
Your code differs from your explanation. However, here is the answer to your question:
您的代码与您的解释不同。但是，这是您问题的答案：
回答by gkuzmin
Ammm.... Maybe this:
嗯……也许是这样：
List<Integer> lnLst = new ArrayList<>();
should look like this:
应该是这样的：
List<Integer> lnLst = new LinkedList<>();
And I can not understand what are you trying to measure. I think that you want to measure addperfromance and then your code should look like this:
我不明白你想衡量什么。我认为您想衡量add性能，然后您的代码应如下所示：
public static void main(String[] args) {
List<Integer> arLst = new ArrayList<Integer>();
List<Integer> lnLst = new LinkedList<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
arLst.add(i);
}
System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
lnLst.add(i);
}
System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}
回答by Chris Dargis
...since arrays know in O(1) where to insert, unlike LinkedList that has to go through the whole list, as I recall).
...因为数组知道在 O(1) 中插入的位置，不像 LinkedList 必须遍历整个列表，我记得）。
This isn't correct. Arrays (not ArrayLists) do not have a constant insert time, Java's ArrayList technicallydoesn't either (The add operation runs in amortized constant timefor an ArrayList).
这不正确。数组（不是 ArrayLists）没有固定的插入时间，Java 的 ArrayList 从技术上讲也没有（添加操作在ArrayList 的分摊固定时间内运行）。
Further, inserting an element into a linked list is O(1):
此外，将元素插入链表是O(1)：
In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list.
LinkedList 类除了实现 List 接口外，还提供了统一命名的方法来获取、删除和插入列表开头和结尾的元素。
If you are inserting into a sorted list, the complexity becomes O(N).
如果您插入一个排序列表，则复杂度变为O(N)。
