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

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

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

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


当前回答

数组列表本质上是一个具有添加项等方法的数组(您应该使用通用列表)。它是可以通过索引器(例如[0])访问的项的集合。它意味着从一个项目到下一个项目的进展。

链接列表指定从一个项目到下一个项目(项目A->项目b)的进度。您可以使用数组列表获得相同的效果,但链接列表绝对会说明前一个列表后面应该包含哪些项。

其他回答

以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号:

阵列列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite阵列列表

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些,您必须决定选择什么。:)

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是第一种类型,即在列表末尾添加元素,然后在列表中的指定位置删除元素):

是的,我知道,这是一个古老的问题,但我会投入我的两分钱:

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList,但这些算法非常非常罕见,并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。

有一个常见的用例LinkedList优于ArrayList:队列。但是,如果您的目标是性能,那么您也应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且能够提前分配所有内存),而不是LinkedList,或者使用CircularArray实现。(是的,它来自2001年,因此您需要对其进行一般化,但我得到的性能比与最近一篇JVM文章中引用的性能比相当)

ArrayList是您想要的。LinkedList几乎总是一个(性能)bug。

为什么LinkedList很糟糕:

它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。

ArrayList中的get(i)操作比LinkedList更快,因为:ArrayList:List接口的可调整大小的数组实现LinkedList:list和Deque接口的双重链接列表实现

索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。