我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,这样当我问类似这样的问题时,我就可以修改代码。
LinkedList何时应用于ArrayList,反之亦然?
当前回答
ArrayList是您想要的。LinkedList几乎总是一个(性能)bug。
为什么LinkedList很糟糕:
它使用了大量小内存对象,因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历,即具有O(n)性能。这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同,它也可能会明显变慢。在源代码中看到LinkedList很刺耳,因为它可能是错误的选择。
其他回答
Joshua Bloch,LinkedList的作者:
有人真的使用LinkedList吗?我写的,我从来没有用过。
链接:https://twitter.com/joshbloch/status/583813919019573248
很抱歉,我的答案没有其他答案那样信息丰富,但我认为这是最不言自明的答案。
这是一个效率问题。LinkedList添加和删除元素很快,但访问特定元素很慢。ArrayList访问特定元素的速度很快,但添加到两端的速度可能很慢,尤其是删除在中间的速度慢。
Array vs ArrayList vs LinkedList vs Vector更深入,同样如此链接列表。
ArrayList和LinkedList各有利弊。
与使用指向下一个节点的指针的LinkedList相比,ArrayList使用连续内存地址。因此,当您想在ArrayList中查找元素时,比使用LinkedList进行n次迭代更快。
另一方面,LinkedList中的插入和删除要容易得多,因为您只需更改指针,而ArrayList意味着对任何插入或删除都使用移位操作。
如果您的应用程序中有频繁的检索操作,请使用ArrayList。如果频繁插入和删除,请使用LinkedList。
1) 基础数据结构
ArrayList和LinkedList之间的第一个区别在于,ArrayList由Array支持,而LinkedList由LinkedList支持。这将导致性能的进一步差异。
2) LinkedList实现Deque
ArrayList和LinkedList之间的另一个区别是,除了List接口之外,LinkedList还实现了Deque接口,该接口为add()和poll()以及其他几个Deque函数提供先进先出操作。3) 在ArrayList中添加元素如果不触发Array的重新调整大小,则在ArrayList中添加元素是O(1)操作,在这种情况下,它变为O(log(n))。另一方面,在LinkedList中添加一个元素则是O(2)操作,因为它不需要任何导航。
4) 从位置移除元素
为了从特定索引中删除元素,例如通过调用remove(index),ArrayList执行复制操作,使其接近O(n),而LinkedList需要遍历到该点,这也使其成为O(n/2),因为它可以根据接近度从任意方向遍历。
5) 遍历ArrayList或LinkedList
迭代是LinkedList和ArrayList的O(n)操作,其中n是元素的数量。
6) 从位置检索元素
get(index)操作在ArrayList中为O(1),而在LinkedList中为其O(n/2),因为它需要遍历该条目。虽然,在大O符号中,O(n/2)只是O(n),因为我们忽略了那里的常数。
7) 内存
LinkedList使用一个包装对象Entry,这是一个静态嵌套类,用于存储数据和下一个和上一个节点,而ArrayList只在Array中存储数据。
因此,除了Array在将内容从一个Array复制到另一个Array时执行重新调整大小操作的情况外,ArrayList的内存需求似乎比LinkedList少。
如果Array足够大,那么此时可能会占用大量内存并触发垃圾收集,这会降低响应时间。
从ArrayList与LinkedList之间的所有差异来看,ArrayList在几乎所有情况下都是比LinkedList更好的选择,除非您经常执行add()操作而不是remove()或get()操作。
修改链接列表比修改ArrayList更容易,尤其是当您从开始或结束处添加或删除元素时,因为链接列表内部保留了这些位置的引用,并且可以在O(1)时间内访问。
换句话说,您不需要遍历链接列表就可以到达要添加元素的位置,在这种情况下,添加就变成了O(n)操作。例如,在链接列表中间插入或删除元素。
在我看来,在Java中,使用ArrayList而不是LinkedList来实现大多数实际用途。
与LinkedList相比,Summary ArrayList和ArrayDeque在更多的用例中更可取。如果您不确定,请从ArrayList开始。
TLDR,在ArrayList中,访问元素需要恒定的时间[O(1)],添加元素需要O(n)时间[最坏情况]。在LinkedList中,插入元素需要O(n)时间,访问也需要O(n)时间,但LinkedList比ArrayList使用更多内存。
LinkedList和ArrayList是List接口的两种不同实现。LinkedList使用双链接列表实现它。ArrayList通过动态调整数组大小来实现它。
与标准的链表和数组操作一样,不同的方法将有不同的算法运行时。
对于LinkedList<E>
get(int index)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用getFirst()和getLast())。LinkedList的主要优点之一add(int index,E元素)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用addFirst()和addLast()/add())。LinkedList的主要优点之一remove(int index)为O(n)(平均步数为n/4),但当index=0或index=list.size()-1时为O(1)(在这种情况下,还可以使用removeFirst()和removeLast())。LinkedList的主要优点之一Iterator.remove()为O(1)。LinkedList的主要优点之一ListIterator.add(E元素)为O(1)。LinkedList的主要优点之一
注:许多操作平均需要n/4步,在最佳情况下(例如索引=0)需要恒定的步数,在最坏情况下(列表中间)需要n/2步
对于ArrayList<E>
get(int索引)为O(1)。ArrayList的主要优势<E>add(E元素)是O(1)摊销,但O(n)最坏情况,因为数组必须调整大小并复制add(int索引,E元素)为O(n)(平均n/2步)remove(int索引)为O(n)(平均n/2步)Iterator.remove()为O(n)(平均为n/2步)ListIterator.add(E元素)为O(n)(平均n/2步)
注:许多操作平均需要n/2步,在最佳情况下(列表末尾)需要恒定的步数,在最坏情况下(开始列表)需要n步
LinkedList<E>允许使用迭代器进行恒定时间的插入或删除,但只能对元素进行顺序访问。换句话说,您可以向前或向后遍历列表,但在列表中找到位置所需的时间与列表的大小成正比。Javadoc表示“索引到列表中的操作将从开始或结束遍历列表,以较近者为准”,因此这些方法平均为O(n)(n/4步),尽管索引=0时为O(1)。
另一方面,ArrayList<E>允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,除了末端之外,任何地方的添加或删除都需要将后面的所有元素转换过来,要么打开,要么填补空白。此外,如果添加的元素超过了基础数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组,因此在最坏的情况下,添加到ArrayList是O(n),但平均来说是常量。
因此,根据您打算执行的操作,您应该相应地选择实现。对这两种列表进行迭代实际上都是同样便宜的。(在ArrayList上迭代在技术上更快,但除非您正在做一些对性能非常敏感的事情,否则不必担心这一点——它们都是常量。)
使用LinkedList的主要好处是重用现有迭代器来插入和删除元素。然后,这些操作可以在O(1)中通过仅本地更改列表来完成。在阵列列表中,需要移动(即复制)阵列的其余部分。另一方面,在LinkedList中查找意味着在最坏情况下遵循O(n)(n/2步)中的链接,而在ArrayList中,所需位置可以通过数学计算并在O(1)中访问。
使用LinkedList的另一个好处是在列表的开头添加或删除,因为这些操作是O(1),而ArrayList是O(n)。请注意,ArrayDeque可能是LinkedList的一个很好的替代方案,用于添加和删除头部,但它不是List。
此外,如果您有大量列表,请记住内存使用情况也不同。LinkedList的每个元素都有更多的开销,因为指向下一个和上一个元素的指针也会被存储。ArrayList没有这个开销。然而,ArrayList占用的内存与为容量分配的内存一样多,而不管是否实际添加了元素。
ArrayList的默认初始容量非常小(Java 1.4-1.8中为10)。但由于底层实现是一个数组,如果添加大量元素,则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的高昂成本,请使用更高的初始容量构建ArrayList。
如果使用数据结构透视图来理解这两个结构,LinkedList基本上是一个包含头节点的顺序数据结构。Node是两个组件的包装器:一个类型为T的值[通过泛型接受],另一个对链接到它的Node的引用。因此,我们可以断言它是一个递归数据结构(一个Node包含另一个节点,该节点具有另一个Node等等…)。如上所述,在LinkedList中添加元素需要线性时间。
ArrayList是一个可增长的数组。它就像一个常规数组。在后台,当添加了一个元素,并且ArrayList已经满了容量时,它将创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新的数组,并且将要添加的元素也放置在指定的索引处。