哪个运行速度更快，是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获取项目可能会导致您遍历整个链接列表以找到项目节点.结果，在这种情况下，它的性能低于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 cost ，而前者没有.另一方面，如果您不经常插入和频繁查找，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项:请勿在新代码中使用原始类型进行详细说明.

See Effective Java, Item 23: Don't use raw types in new code for a detailed explanation.

编辑

根据评论中的讨论，对您来说显而易见的是，如果您需要在列表的中间或随机位置插入元素，则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屋！