ArrayList和LinkedList哪个运行得更快？[副本]

Question

List li = new LinkedList();

for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1-start1;

System.out.println("Time taken by LinkedList = "+diff1);

List al = new ArrayList();
for (int i = 0; i < 100; i++) {
    al.add(i);
}

Answer 1

如果必须执行大量插入和不太频繁的查找，请使用LinkedList。如果执行的查找多于插入，请使用ArrayList。

原因如下--ArrayList由具有初始容量的数组支持。因此，如果您一直在列表中插入项，它将不得不重新调整其数组容量以容纳新插入的项，如果执行索引-spcific插入，它可能还必须转移现有的项。另一方面，LinkedList由链表支持，在链表中创建项总是在一个恒定的时间内执行--创建一个项并将其分配到列表的末尾。这里没有重新调整。

现在，要从ArrayList中获取一个项，总是需要一定的时间，因为它可以很容易地在一定的时间内索引支持数组。但是，从LinkedList中获取项可能会导致您遍历整个链表以查找项节点。因此，在本例中，它的执行不如ArrayList。

List<Integer> li = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
    li.add(i);
}

long start1 = System.nanoTime();
li.get(57);

long end1 = System.nanoTime();
long diff1 = end1 - start1;

System.out.println("Time taken by LinkedList = "+diff1);

List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
    al.add(i);
}