ArrayList 或 LinkedList 哪个运行得更快? [英] Which one runs faster, ArrayList or LinkedList?

问题描述

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);
}

无论我在两个列表上执行什么操作，当我打印出花费的时间时，ArrayList 总是比 LinkedList 运行得更快.有人可以解释哪个在所用时间方面表现更好吗?也让我知道代码中是否有问题.谢谢！

What ever operations I perform on both the lists, when I print out the time taken, ArrayList always runs faster than LinkedList. Can somebody explain which performs better in terms of time taken? Also let me know if there is something wrong in the code. Thanks!

推荐答案

如果您必须执行大量插入和不那么频繁的查找，请使用 LinkedList.如果您执行的查找次数多于插入次数，请使用 ArrayList.

If you have to perform lots of inserts and not-so-frequent lookup, use a LinkedList. Use ArrayList if you perform more lookup than inserts.

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

The reason is as follows - ArrayList is backed by an array which has an initial capacity. So, if you keep inserting items into the list, at one point it will have to re-adjust its array capacity to accommodate newly inserted items, and it may also have to shift the existing items if you perform an index-spcific inserts. On the other hand, LinkedList is backed by a linked list, where creating an item always executes in a constant time - create an item and assign it to the end of the list. No re-adjustment occurs here.

现在要从 ArrayList 中获取一个项目，它总是需要一个恒定的时间，因为它可以很容易地在一个恒定的时间内索引后备数组.但是从 LinkedList 中获取一个 item 可能会导致你遍历整个链表来找到 item 节点.因此，在这种情况下，它的性能低于 ArrayList.

Now to fetch an item from the ArrayList, it will always take a constant amount of time since it can easily index the backing array in a constant time. But fetching an item from the LinkedList may cause you to traverse the entire linked list to find the item node. As a result, it performs less than ArrayList in this case.

从上面的讨论中，您可以看到，当您有更多的插入操作时，LinkedList 将始终优于 ArrayList，因为后者具有内部 resize 成本 与插入相关联，而前者没有.另一方面，如果您有不频繁的插入和频繁的查找，ArrayList 将始终优于 LinkedList，因为对于后者，您可能必须遍历整个链表结构才能找到需要的项目，而前者将能够通过数组索引在恒定时间内快速找到您的项目.

From the above discussion, you can see that when you have more inserts to do, LinkedList will always outperform ArrayList because the latter has an internal resize cost associated with inserts while the former doesn't. On the other hand, if you have infrequent inserts and frequent lookups, ArrayList will always outperform LinkedList because for the latter you may have to traverse the entire linked list structure to find the desired item, while the former will be able to quickly find your items with array indexing in constant times.

当您处理大量项目(例如，数千个项目)时，上述所有效果都将可见并影响应用程序的性能.对于较少的项目，性能差异不太明显.

All of the above effects will be visible and affect your application's performance when you are dealing with a lots of items (say, thousands of items). For a fewer items, the performance difference is not quite visible.

现在，关于您的代码，您有一些严重的问题.首先，您使用的是原始类型，这很糟糕，因为您失去了泛型必须提供的所有类型安全性.编写新代码时，应始终使用 Collection API 的通用版本.因此，按如下方式更改您的代码 -

Now, about your code, you have some serious problems with it. For starter, you are using a raw type, which is bad as you lose all the type safety that generics have to offer. You should always use the generic version of the Collection API when you write new code. So, change your code as follows -

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);
}

参见有效的Java，条款 23:不要在新代码中使用原始类型以获得详细说明.

编辑

从评论中的讨论来看，你应该很明显，如果你需要在列表的中间或随机位置插入元素，那么ArrayList优于LinkedList 在性能方面，因为前者会使用 memcpy 来移动元素，速度非常快，而后者必须遍历到所需的索引才能正确插入新元素，其中比较慢.所以对于随机插入，ArrayList 也优于 LinkedList.LinkedList 优于 ArrayList 的唯一情况是，如果您只在列表末尾插入，并且有很多这样的插入.

From the discussion in the comments, it should be obvious to you that if you need to insert elements in the middle of the list or at a random position, then ArrayList outperforms LinkedList in terms of performance, because the former will use memcpy to shift the elements which is extremely fast, and the latter will have to traverse up to the desired index to properly insert the new element, which is slower. So for random insertions ArrayList also outperforms LinkedList. The only case LinkedList outperforms ArrayList is if you only inserts at the end of your list, and there are lots of these inserts.

这篇关于ArrayList 或 LinkedList 哪个运行得更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！