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

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

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

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


当前回答

让我们将LinkedList和ArrayList与以下参数进行比较:

1.实施

ArrayList是列表接口的可调整大小的数组实现,而LinkedList是列表接口的双重链接列表实现。


2.性能

get(int索引)或搜索操作ArrayList get(int索引)操作在恒定时间内运行,即O(1)而LinkedList get(int索引)操作运行时间为O(n)。ArrayList比LinkedList更快的原因是ArrayList对其元素使用基于索引的系统,LinkedList不为其元素提供基于索引的访问,因为它从开始或结束(以较近者为准)迭代以检索指定元素索引处的节点。insert()或add(Object)操作与ArrayList相比,LinkedList中的插入通常很快。在LinkedList中,添加或插入是O(1)操作。在ArrayList中,如果数组已满(即最坏情况),则调整数组大小并将元素复制到新数组会产生额外的成本,这使得ArrayList的加法运算运行时为O(n),否则为O(1)。删除(int)操作LinkedList中的移除操作通常与ArrayList相同,即O(n)。在LinkedList中,有两个重载的移除方法。一个是remove(),没有任何参数,它会删除列表的头部,并在恒定时间O(1)内运行。LinkedList中的另一个重载remove方法是remove(int)或remove(Object),它删除作为参数传递的Object或int。此方法遍历LinkedList,直到找到Object并将其从原始列表中取消链接。因此,该方法运行时为O(n)。在ArrayList中,remove(int)方法涉及将元素从旧数组复制到新的更新数组,因此其运行时为O(n)。


3.反向迭代器

LinkedList可以使用descendingIterator()反向迭代,同时ArrayList中没有descendingIterator(),因此我们需要编写自己的代码以反向遍历ArrayList。


4.初始容量

如果构造函数没有重载,那么ArrayList将创建一个初始容量为10的空列表,而LinkedList只构建没有任何初始容量的空列表。


5.内存开销

与ArrayList相比,LinkedList中的内存开销更大,因为LinkedList的节点需要维护下一个和上一个节点的地址。虽然在ArrayList中,每个索引仅保存实际对象(数据)。


来源

其他回答

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

算法:Big Oh符号(存档)

ArrayList适用于一次写入、多次读取或追加,但不适用于从前面或中间添加/删除。

我应该何时使用LinkedList?大多数情况下使用堆栈时,或使用缓冲区时。我应该何时使用ArrayList?只有在使用索引时,否则您可以将HashTable与链接列表一起使用,那么您将得到:

哈希表+链接列表

通过密钥O(1)访问,通过键O(1)插入,通过键O(1)拆除在使用版本控制时,使用O(1)实现RemoveAll/SetAll有一个技巧

这似乎是一个很好的解决方案,在大多数情况下,你应该知道:HashTable占用了大量磁盘空间,所以当您需要管理1000000个元素列表时,它可能会变得很重要。这可能发生在服务器实现中,但在客户端中很少发生。

还可以看看红黑树

随机访问日志(n),插入日志(n),删除日志(n)

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

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

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

见原始答案下方作者的2021更新。


原答案(2011年)

作为一个在非常大规模的SOA web服务上做了大约十年操作性能工程的人,我更喜欢LinkedList而不是ArrayList的行为。虽然LinkedList的稳态吞吐量更差,因此可能会导致购买更多硬件,但ArrayList在压力下的行为可能会导致集群中的应用程序以近乎同步的方式扩展其阵列,而对于较大的阵列大小,可能会导致应用程序缺乏响应能力,在压力下停机,这是灾难性的行为。

类似地,您可以从默认的吞吐量固定垃圾收集器中获得更好的应用吞吐量,但一旦您获得了具有10GB堆的java应用程序,您就可以在完全GC期间锁定应用程序25秒,这会导致SOA应用程序超时和失败,如果太频繁,还会破坏SLA。尽管CMS收集器占用了更多的资源,并且没有实现相同的原始吞吐量,但它是一个更好的选择,因为它具有更可预测性和更小的延迟。

如果您所指的性能是吞吐量,并且可以忽略延迟,那么ArrayList只是性能的更好选择。根据我的工作经验,我不能忽视最坏情况下的延迟。

更新(2021 8月27日——10年后)

这个答案(也是我在SO问题上最受欢迎的答案)很可能是错误的(原因在下面的评论中概述)。我想补充一点,ArrayList将优化内存的顺序读取,并最小化缓存线和TLB未命中等。相比之下,当阵列增长超过边界时的复制开销可能无关紧要(可以通过高效的CPU操作完成)。考虑到硬件趋势,随着时间的推移,这个答案可能会变得更糟。LinkedList可能有意义的唯一情况是,如果您有数千个列表,其中任何一个都可能增长到GB大小,但在分配列表时无法做出正确的猜测,并且将它们全部设置为GB大小,则会炸毁堆。如果你发现了这样的问题,那么无论你的解决方案是什么,都需要重新设计(我不想轻率地建议重新设计旧代码,因为我自己维护了一堆又一堆的旧代码,但这是一个很好的例子,因为原始设计已经过时,确实需要扔掉)。尽管如此,我还是会把我几十年来的糟糕观点留在那里,让你读一读。简单、合乎逻辑,而且非常错误。

ArrayList是可随机访问的,而LinkedList扩展和删除元素非常便宜。在大多数情况下,ArrayList都可以。

除非您创建了大量列表并测量了瓶颈,否则您可能永远不需要担心差异。