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

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

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

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


当前回答

TL;DR由于现代计算机体系结构,ArrayList对于几乎所有可能的用例都将显著提高效率,因此除了一些非常独特和极端的情况外,应避免使用LinkedList。


理论上,LinkedList的add(E元素)有一个O(1)

此外,在列表中间添加元素应该非常有效。

实践非常不同,因为LinkedList是一个缓存敌对数据结构。从性能POV来看,LinkedList很少比缓存友好的ArrayList性能更好。

以下是在随机位置插入元素的基准测试结果。如您所见,数组列表效率更高,但理论上,每次在列表中间插入都需要“移动”数组后面的n个元素(值越低越好):

使用新一代硬件(更大、更高效的缓存),结果更为确凿:

LinkedList需要更多的时间来完成相同的任务。源源代码

这主要有两个原因:

主要是LinkedList的节点在内存中随机分布。RAM(“随机存取存储器”)不是真正随机的,需要将内存块提取到缓存中。此操作需要时间,并且当此类提取频繁发生时,缓存中的内存页需要一直被替换->缓存未命中->缓存效率不高。ArrayList元素存储在连续内存中——这正是现代CPU架构正在优化的目标。Secondary LinkedList需要保留/转发指针,这意味着与ArrayList相比,每个存储值的内存消耗是3倍。

顺便说一句,DynamicIntArray是一个自定义ArrayList实现,它保存Int(原始类型)而不是Object,因此所有数据都是相邻存储的,因此效率更高。

需要记住的一个关键因素是,获取存储块的成本比访问单个存储单元的成本更重要。这就是为什么读卡器1MB的顺序存储器比从不同内存块读取此数据量快x400倍的原因:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

来源:每个程序员都应该知道的延迟数

为了让这一点更加清晰,请检查在列表开头添加元素的基准。这是一个用例,从理论上讲,LinkedList应该非常出色,而ArrayList应该呈现出糟糕甚至更糟糕的用例结果:

注意:这是C++标准库的一个基准测试,但我以前的经验表明C++和Java的结果非常相似。源代码

复制连续的大量内存是一种由现代CPU改变理论优化的操作,实际上也使ArrayList/Vector更加高效


致谢:这里发布的所有基准都是由Kjell Hedström创建的。在他的博客上可以找到更多的数据

其他回答

这是一个效率问题。LinkedList添加和删除元素很快,但访问特定元素很慢。ArrayList访问特定元素的速度很快,但添加到两端的速度可能很慢,尤其是删除在中间的速度慢。

Array vs ArrayList vs LinkedList vs Vector更深入,同样如此链接列表。

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

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

ArrayList本质上是一个数组。LinkedList实现为双链接列表。

答案很清楚。O(1)表示ArrayList,因为ArrayList允许使用索引进行随机访问。O(n)表示LinkedList,因为它需要首先查找索引。注意:添加和删除有不同的版本。

LinkedList在添加和删除时速度更快,但在获取时速度较慢。简而言之,在以下情况下,应首选LinkedList:

元素没有大量的随机访问有大量的添加/删除操作

==阵列列表===

添加(E E)在ArrayList末尾添加需要内存大小调整成本。O(n)最差,O(1)摊销add(int索引,E元素)添加到特定索引位置需要移动和可能的内存调整成本O(n)删除(int索引)删除指定的元素需要移动和可能的内存调整成本O(n)删除(对象o)从此列表中删除第一个出现的指定元素需要先搜索元素,然后移动&可能的内存调整成本O(n)

==链接列表===

添加(E E)添加到列表末尾O(1)add(int索引,E元素)在指定位置插入需要先找到位置O(n)删除()删除列表的第一个元素O(1)删除(int索引)删除具有指定索引的元素需要先找到元素O(n)删除(对象o)删除指定元素的第一个引用需要先找到元素O(n)

这是programcreek.com中的一个图(add和remove是第一种类型,即在列表末尾添加元素,然后在列表中的指定位置删除元素):

我的经验法则是,如果我需要一个集合(即不需要是一个列表),那么如果你事先知道大小,或者可以自信地知道大小,或知道它不会有太大变化,那么就使用ArrayList。如果您需要随机访问(即使用get(index)),请避免LinkedList。基本上,只有当您不需要索引访问并且不知道正在分配的集合的(近似)大小时,才使用LinkedList。此外,如果您要进行大量添加和删除(再次通过Collection接口),则LinkedList可能更可取。

我已经阅读了答案,但有一种情况是,我总是使用LinkedList而不是ArrayList,我想分享它来听取意见:

每次我有一个方法返回从DB获得的数据列表时,我总是使用LinkedList。

我的理由是,因为不可能确切地知道我得到了多少结果,所以不会浪费内存(如ArrayList中的容量和实际元素数量之间的差异),也不会浪费时间复制容量。

至于ArrayList,我同意至少应该始终使用具有初始容量的构造函数,以尽可能减少数组的重复。