何时使用 ArrayList 何时使用 LinkedList?

问题

我一直只使用一个:

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

我使用接口作为类型名称来提供便携性,以便当我提出这些问题时,我可以重写我的代码。

什么时候应该使用LinkedList而不是ArrayList,反之亦然?


#1 热门回答(2820 赞)

摘要带有ArrayDeque的ArrayList`在比LinkedList更多的用例中更受欢迎。不确定

  • 只需从ArrayList开始。

 LinkedListArrayList是List接口的两种不同的实现。 LinkedList用双链表实现它。 ArrayList通过一个动态调整大小的数组来实现它。

与标准链表和数组操作一样,各种方法将具有不同的算法运行时。

对于LinkedList <E>

  • get(int index)是O(n)(平均n / 4步)
  • add(E元素)是O(1)
  • 增加(int index,E元素)为O(n)(平均n / 4步),但O(1)当index = 0时<--- LinkedList的主要优点<E>
  • 删除(int index)是O(n)(平均n / 4步)
  • Iterator.remove()是O(1)。 <--- LinkedList <E>的主要优点
  • ListIterator.add(E元素)是O(1)这是LinkedList <E>的一个主要优点,
    注意:许多操作平均需要n / 4步,最佳情况下的步数为常数(例如,索引= 0),最坏情况下为n / 2步(列表中部)
    对于ArrayList <E>
  • get(int index)是O(1)<--- ArrayList <E>的主要好处
  • 添加(E元素)是O(1)摊销,但O(n)最坏的情况,因为数组必须调整大小并复制
  • add(int index,E element)是O(n)(平均n / 2步)
  • 删除(int index)是O(n)(平均n / 2步)
  • Iterator.remove()是O(n)(平均n / 2步)
  • ListIterator.add(E元素)是O(n)(平均n / 2步)
    注意:许多操作平均需要2次/步,最佳情况下的步数不变(列表结束),最差情况下nsteps(列表开始)
     LinkedList <E>允许使用迭代器进行常量插入或删除,但只能按顺序访问元素。换句话说,您可以向前或向后遍历列表,但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc说“索引到列表中的操作将从开头或结尾遍历列表,以较近者为准”,因此这些方法平均为O(n)(n / 4步),但对于`index = 0,则为O(1) 。

 另一方面,ArrayList <E>允许快速的随机读访问,所以你可以在任何时候获取任何元素。但是,除了最终的目的地之外,添加或删除任何内容都需要将所有后面的元素转移,以便开放或填补空白。另外,如果添加的元素多于底层数组的容量,则会分配一个新的数组(1.5倍大小),并将旧数组复制到新数组中,因此将“ArrayList”添加到O(n)中最坏的情况,但平均不变。

所以根据你打算做的操作,你应该选择相应的实现。迭代任何一种List几乎同样便宜。 (迭代一个'ArrayList`在技术上更快,但除非你做一些真正对性能敏感的东西,你不应该担心这个 - 它们都是常量。)

当你重用现有的迭代器来插入和删除元素时,使用LinkedList的主要好处就出现了。这些操作可以通过仅在本地改变列表在O(1)中完成。在数组列表中,数组的其余部分需要被移动(即被复制)。另一方面,在LinkedList中寻找意味着在最坏情况下跟随O(n)(n / 2steps)中的链接,而在ArrayList中,期望的位置可以通过数学计算并在O(1)中访问。

使用LinkedList的另一个好处是当你从列表头部添加或删除时出现,因为这些操作是O(1),而对于ArrayList它们是O(n)。请注意,ArrayDeque可能是LinkedList的一个很好的替代方案,用于从头部添加和删除,但它不是List

另外,如果您有大型列表,请记住内存使用情况也不同。 “LinkedList”的每个元素都有更多的开销,因为还存储了指向下一个和前一个元素的指针。 ArrayLists没有这个开销。然而,无论元素是否实际添加,ArrayLists占用的容量都与分配的容量相同。

ArrayList的默认初始容量非常小(来自Java 1.4 - 1.8的10)。但是由于底层实现是一个数组,因此如果添加了很多元素,则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的成本,请构建具有较高初始容量的“ArrayList”。


#2 热门回答(532 赞)

到目前为止,似乎没有人解决这些列表中的每一个的内存占用情况,除了普遍认为“LinkedList”比“ArrayList”更“多得多”之外,所以我做了一些数字处理来证明这两个列表占用了多少为N空引用。

由于引用在其相关系统上是32位或64位(即使为空),我已经为32位和64位“LinkedLists”和“ArrayLists”包含了4组数据。

注释:“ArrayList”行显示的大小是fortrimmed列表 - 实际上,“ArrayList”中的后备数组的容量通常大于其当前的元素数。

注释2:(感谢BeeOnRope)由于CompressedOops现在默认从JDK6中部开始,因此64位机器的下面的值基本上与它们的32位机器相匹配,除非您特别关闭它。

Graph of LinkedList and ArrayList No. of Elements x Bytes

结果清楚地表明LinkedListArrayList要多得多,特别是元素数量非常多。如果记忆是一个因素,请避开LinkedLists

我使用的公式如下,让我知道如果我做错了什么,我会修复它。对于32或64位系统,'b'是4或8,'n'是元素的数量。注意mods的原因是因为java中的所有对象都占用8个字节的倍数,而不管它是否全部使用。

 ArrayList

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

 LinkedList

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

#3 热门回答(188 赞)

ArrayList就是你想要的。 LinkedList几乎总是一个(性能)错误。

为什么LinkedList很糟糕:

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