Java ArrayList 或 LinkedList 哪个运行得更快？

Which one runs faster, ArrayList or LinkedList?

提问by Anjan Baradwaj

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

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!

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

回答by MD Sayem Ahmed

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

如果您必须执行大量插入和不那么频繁的查找，请使用LinkedList. 使用ArrayList，如果你表现得比插入多个查找。

The reason is as follows - ArrayListis 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, LinkedListis 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由链表支持，其中创建项目总是在恒定时间内执行 - 创建一个项目并将其分配到列表的末尾。这里没有重新调整。

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 LinkedListmay cause you to traverse the entire linked list to find the item node. As a result, it performs less than ArrayListin this case.

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

From the above discussion, you can see that when you have more inserts to do, LinkedListwill always outperform ArrayListbecause the latter has an internal resize costassociated with inserts while the former doesn't. On the other hand, if you have infrequent inserts and frequent lookups, ArrayListwill always outperform LinkedListbecause 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.

从上面的讨论中，您可以看到，当您有更多的插入要做时，它LinkedList总是会表现出色，ArrayList因为后者具有与插入相关的内部调整大小成本，而前者则没有。另一方面，如果你有不频繁的插入和频繁的查找，ArrayList总是会表现得LinkedList更好，因为对于后者你可能必须遍历整个链表结构才能找到所需的项目，而前者将能够通过数组快速找到你的项目在恒定时间内索引。

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.

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

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 -

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

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

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

有关详细说明，请参阅Effective Java，第 23 条：不要在新代码中使用原始类型。

EDIT

编辑

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 ArrayListoutperforms LinkedListin terms of performance, because the former will use memcpyto 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 ArrayListalso outperforms LinkedList. The only case LinkedListoutperforms ArrayListis if you only inserts at the end of your list, and there are lots of these inserts.

从意见的讨论中，它应该是显而易见的你，如果你需要在列表中的中间或在随机位置插入元素，则ArrayList优于LinkedList在性能方面，因为前者会使用memcpy到的元件转移非常快，后者必须遍历到所需的索引才能正确插入新元素，这会更慢。所以对于随机插入ArrayList也优于LinkedList. 唯一LinkedList优于的情况ArrayList是，如果您只在列表末尾插入，并且有很多这样的插入。

回答by Subhrajyoti Majumder

ArrayListis backed by array and LinkedListbacked Node's linked with refernece.

ArrayList由数组LinkedList支持，支持节点与引用链接。

So operation on ArrayListis actaully evalute operation on array. The add operation runs in amortized constant time, that is, adding n elements requires O(n)time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedListimplementation.

所以操作ArrayList实际上是对数组进行评估操作。add 操作在分摊常数时间内运行，即添加 n 个元素需要O(n)时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实施的常数系数相比，常数系数较低。

and on LinkedListall of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

并且在LinkedList所有操作上都按照双向链表的预期执行。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引的为准。

read more on documentation -

阅读更多关于文档 -

• ArrayList
• LinkedList

• 数组列表
• 链表

回答by upog

LinkedListwill involve creation of new node when adding each element, while it is not in array list.

LinkedList添加每个元素时将涉及创建新节点，而它不在数组列表中。

If you know initial size then pass it to ArrayListwhile creating, It avoids reconstruction of array like new ArrayList(100);

如果您知道初始大小，然后ArrayList在创建时将其传递给它，它可以避免像new ArrayList(100);

回答by Vijay

Array List will be always faster than Linked list in terms of read. ArrayList is basically array implementation and the memory allocated for an array is sequentially so read is faster. But when you using list which requires insertion or delete in between the list then Linked List is faster . Because it just had to add the links in between nodes. In these two cases array list will be slower.Usage can be :

在读取方面，数组列表总是比链表快。ArrayList 基本上是数组实现，为数组分配的内存是顺序的，因此读取速度更快。但是当您使用需要在列表之间插入或删除的列表时，链接列表会更快。因为它只需要在节点之间添加链接。在这两种情况下，数组列表会变慢。用法可以是：

ArrayList - Faster read operation, insertion,deletion between the list is slower. Linked List - Read operation slow compared to Array List but insertion,deletion between the list is faster.

ArrayList - 更快的读取操作，列表之间的插入、删除更慢。链表 - 读取操作比数组列表慢，但列表之间的插入、删除速度更快。