我一直是一个简单使用的人:

List<String> names = new ArrayList<>();

我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。

LinkedList何时应用于ArrayList,反之亦然?


当前回答

除了上面的其他好参数之外,您应该注意到ArrayList实现了RandomAccess接口,而LinkedList实现了Queue。

因此,他们解决的问题略有不同,效率和行为有所不同(见他们的方法列表)。

其他回答

请参阅Java教程-列表实现。

ArrayList和LinkedList各有利弊。

与使用指向下一个节点的指针的LinkedList相比,ArrayList使用连续内存地址。因此,当您想在ArrayList中查找元素时,比使用LinkedList进行n次迭代更快。

另一方面,LinkedList中的插入和删除要容易得多,因为您只需更改指针,而ArrayList意味着对任何插入或删除都使用移位操作。

如果您的应用程序中有频繁的检索操作,请使用ArrayList。如果频繁插入和删除,请使用LinkedList。

是的,我知道,这是一个古老的问题,但我会投入我的两分钱:

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList,但这些算法非常非常罕见,并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。

有一个常见的用例LinkedList优于ArrayList:队列。但是,如果您的目标是性能,那么您也应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且能够提前分配所有内存),而不是LinkedList,或者使用CircularArray实现。(是的,它来自2001年,因此您需要对其进行一般化,但我得到的性能比与最近一篇JVM文章中引用的性能比相当)

Joshua Bloch,LinkedList的作者:

有人真的使用LinkedList吗?我写的,我从来没有用过。

链接:https://twitter.com/joshbloch/status/583813919019573248

很抱歉,我的答案没有其他答案那样信息丰富,但我认为这是最不言自明的答案。

您可以根据对该特定列表执行的操作的时间复杂性,使用一个而不是另一个。

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|