我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
ArrayList是可随机访问的,而LinkedList扩展和删除元素非常便宜。在大多数情况下,ArrayList都可以。
除非您创建了大量列表并测量了瓶颈,否则您可能永远不需要担心差异。
其他回答
您可以根据对该特定列表执行的操作的时间复杂性,使用一个而不是另一个。
|---------------------|---------------------|--------------------|------------|
| 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 |
|--------------------------------------|
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创建的。在他的博客上可以找到更多的数据
这取决于您将在列表中执行更多操作。
ArrayList访问索引值更快。插入或删除对象时,情况更糟。
要了解更多信息,请阅读任何关于数组和链接列表之间区别的文章。
ArrayList是可随机访问的,而LinkedList扩展和删除元素非常便宜。在大多数情况下,ArrayList都可以。
除非您创建了大量列表并测量了瓶颈,否则您可能永远不需要担心差异。
请参阅Java教程-列表实现。