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

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

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

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


当前回答

我知道这是一篇老帖子,但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque(和Queue)中的方法;如果您希望进行公平的比较,请尝试对ArrayDeque运行LinkedList,并进行功能比较。

其他回答

到目前为止,除了人们普遍认为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)

Joshua Bloch,LinkedList的作者:

有人真的使用LinkedList吗?我写的,我从来没有用过。

链接:https://twitter.com/joshbloch/status/583813919019573248

很抱歉,我的答案没有其他答案那样信息丰富,但我认为这是最不言自明的答案。

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

哈希表+链接列表

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

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

还可以看看红黑树

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

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

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

如果您的代码有add(0)和remove(0),请使用LinkedList,这是更漂亮的addFirst()和removeFirst()方法。否则,请使用ArrayList。

当然,Guava的ImmutableList是你最好的朋友。