我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
ArrayList扩展了AbstractList并实现了List接口。ArrayList是动态数组。可以说,它的创建基本上是为了克服数组的缺点LinkedList类扩展了AbstractSequentialList并实现了List、Deque和Queue接口。表演arraylist.get()是O(1),而linkedlist.getarraylist.add()为O(1),linkedlist.add)为0(1)arraylist.contains()为O(n),linkedlist.contans()为0(n)arraylist.next()为O(1),linkedlist.next()为0(1)arraylist.remove()是O(n),而linkedlist.remove()是0(1)在arraylistiterator.remove()是O(n),而在linkedlist迭代器.remove
其他回答
我在这里看到的一个测试只进行一次测试。但我注意到的是,您需要多次运行这些测试,最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例,我需要向列表中添加/删除项目,该列表将增加到大约500个项目。在我的测试中,LinkedList的发布速度更快,LinkedList约为50000 NS,ArrayList约为90000NS。。。给予或索取。请参见下面的代码。
public static void main(String[] args) {
List<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 500; i++) {
list.add(i);
}
Iterator it = list.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
long end = System.nanoTime();
long diff = end - start;
//uncomment to see the JVM warmup and get faster for the first few iterations
//System.out.println(diff)
return diff;
}
到目前为止,除了人们普遍认为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)
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创建的。在他的博客上可以找到更多的数据
如果您的代码有add(0)和remove(0),请使用LinkedList,这是更漂亮的addFirst()和removeFirst()方法。否则,请使用ArrayList。
当然,Guava的ImmutableList是你最好的朋友。
ArrayList是您想要的。LinkedList几乎总是一个(性能)bug。
为什么LinkedList很糟糕:
它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。