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

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

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

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


当前回答

以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号:

阵列列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite阵列列表

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些,您必须决定选择什么。:)

其他回答

ArrayList和LinkedList各有利弊。

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

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

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

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

ArrayList是您想要的。LinkedList几乎总是一个(性能)bug。

为什么LinkedList很糟糕:

它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。

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

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

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

到目前为止,除了人们普遍认为LinkedList比ArrayList“多得多”之外,似乎没有人解决这些列表中每一个的内存占用问题,所以我做了一些数字处理,以证明这两个列表对于N个空引用所占的空间。

由于引用在其相对系统上是32位或64位(即使为空),因此我为32位和64位LinkedList和ArrayList包含了4组数据。

注意:ArrayList行显示的大小是用于修剪列表的-实际上,ArrayList中的后备数组的容量通常大于其当前元素计数。

注2:(感谢BeeOnRope)由于压缩Oops现在是默认值,从JDK6中期开始,以下64位机器的值将基本上与32位机器的对应值相匹配,当然,除非您特意关闭它。



结果清楚地表明,LinkedList比ArrayList多得多,尤其是元素数非常高的情况。如果内存是一个因素,请避开LinkedList。

我使用的公式如下,如果我做错了什么,请告诉我,我会改正的对于32位或64位系统,b’是4或8,而n’是元素的数量。注意mods的原因是因为java中的所有对象都将占用8字节的倍数空间,而不管是否全部使用。

阵列列表:

ArrayList对象头+大小整数+modCount整数+数组引用+(数组项目头+b*n)+MOD

链接列表:

LinkedList对象标头+大小整数+modCount整数+对标头的引用+对页脚的引用+(节点对象开销+对上一元素的引用+下一元素的参考+对元素的引用)*n)+MOD(节点对象,8)*n+MOD, 8)