我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
到目前为止,除了人们普遍认为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)
其他回答
如果您的代码有add(0)和remove(0),请使用LinkedList,这是更漂亮的addFirst()和removeFirst()方法。否则,请使用ArrayList。
当然,Guava的ImmutableList是你最好的朋友。
请参阅Java教程-列表实现。
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和LinkedList,remove()和insert()的运行时效率都为O(n)。然而,线性处理时间背后的原因来自两个非常不同的原因:
在ArrayList中,您可以找到O(1)中的元素,但实际上删除或插入某些元素会使其成为O(n),因为以下所有元素都需要更改。
在LinkedList中,实际到达所需元素需要O(n),因为我们必须从一开始就开始,直到达到所需的索引。实际上,移除或插入是常量,因为我们只需要为remove()更改1个引用,为insert()更改2个引用。
插入和删除这两项中的哪一项更快取决于发生的位置。如果我们更接近开始,LinkedList将更快,因为我们必须经过相对较少的元素。如果我们接近末尾,ArrayList将更快,因为我们在恒定的时间内到达那里,只需更改紧随其后的几个剩余元素。如果正好在中间完成,LinkedList将更快速,因为遍历n个元素比移动n个值更快。
好处:虽然无法为ArrayList创建这两个方法O(1),但实际上在LinkedList中有一种方法可以做到这一点。假设我们想在整个列表中删除和插入元素。通常,您可以使用LinkedList从头开始每个元素,我们也可以使用迭代器“保存”当前正在处理的元素。在迭代器的帮助下,当在LinkedList中工作时,remove()和insert()的效率为O(1)。使其成为我所知的唯一性能优势,LinkedList总是优于ArrayList。
链接列表的一个重要特性(我在另一个答案中没有看到)是两个列表的串联。对于数组,这是O(n)(+某些重新分配的开销),对于链接列表,这只是O(1)或O(2);-)
重要提示:对于Java的LinkedList,这不是真的!请参阅Java中是否有一种快速的链表连接方法?