我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
我知道这是一篇老帖子,但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque(和Queue)中的方法;如果您希望进行公平的比较,请尝试对ArrayDeque运行LinkedList,并进行功能比较。
其他回答
首先使用Vector而不是ArrayList,因为您可以覆盖insuranceCapasity方法,在ArrayList中是私有的,并添加1.5大小的当前数组https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-整数-
在很多情况下,linkedList会更好,las有一个很大的优势:你可以高频插入数据,所以列表的大小变化很快,你不能为数字元素分配大小。从理论上讲,你可能会遇到“内存不足”之类的错误,但在现代计算机中,你有16G和交换磁盘,所以如果你列出的是billoins元素,与15-20年前相比,你可能失败。
除了上面的其他好参数之外,您应该注意到ArrayList实现了RandomAccess接口,而LinkedList实现了Queue。
因此,他们解决的问题略有不同,效率和行为有所不同(见他们的方法列表)。
如果您的代码有add(0)和remove(0),请使用LinkedList,这是更漂亮的addFirst()和removeFirst()方法。否则,请使用ArrayList。
当然,Guava的ImmutableList是你最好的朋友。
链接列表的一个重要特性(我在另一个答案中没有看到)是两个列表的串联。对于数组,这是O(n)(+某些重新分配的开销),对于链接列表,这只是O(1)或O(2);-)
重要提示:对于Java的LinkedList,这不是真的!请参阅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是第一种类型,即在列表末尾添加元素,然后在列表中的指定位置删除元素):