协慌网

我一直只是一个人使用：

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

我使用接口作为可移植性的类型名称，因此当我问这些问题时，我可以重新编写代码。

何时应该使用LinkedList而不是ArrayList ，反之亦然？

摘要 ArrayList与ArrayDeque是更使用情况比最好LinkedList 。如果您不确定 - 只需从ArrayList开始。

LinkedList和ArrayList是 List 接口的两种不同实现。 LinkedList使用双向LinkedList实现它。 ArrayList使用动态重新调整大小的数组来实现它。

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

对于LinkedList<E>

• get(int index)是O（n） （平均n / 4步）
• add(E element)是O（1）
• add(int index, E element)是O（n） （平均n / 4步），但当index = 0时O（1） <--- LinkedList<E>主要好处LinkedList<E>
• remove(int index)是O（n） （平均n / 4步）
• Iterator.remove()是O（1） 。 <--- LinkedList<E>主要好处
• ListIterator.add(E element)是O（1）这是LinkedList<E>的主要优点之一

^{注意：许多操作平均需要n / 4步，最佳情况下需要恒定步数（例如索引 = 0），最坏情况下需要n / 2步（列表中间）}

对于ArrayList<E>

• get(int index)是O（1） <--- ArrayList<E>主要好处
• add(E element)是O（1）摊销，但是O（n）最坏情况，因为必须调整和复制数组
• add(int index, E element)是O（n） （平均n / 2步）
• remove(int index)是O（n） （平均n / 2步）
• Iterator.remove()是O（n） （平均n / 2步）
• ListIterator.add(E element)是O（n） （平均n / 2步）

^{注意：许多操作平均需要n / 2步，最好的情况下是常数步（列表末尾），最坏情况下是n步（列表开头）}

LinkedList<E>允许使用迭代器进行常量时间插入或删除，但只允许顺序访问元素。换句话说，您可以向前或向后遍历列表，但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc 说“索引到列表中的操作将从开头或结尾遍历列表，以较近者为准” ，因此这些方法平均为O（n） （ n / 4步），但index = 0 O（1） index = 0 。

另一方面， ArrayList<E>允许快速随机读取访问，因此您可以在恒定时间内获取任何元素。但是，除了末端之外的任何地方添加或移除都需要将所有后面的元素移位，以便打开或填补空白。此外，如果添加的元素多于底层数组的容量，则会分配一个新数组（大小的 1.5 倍），并将旧数组复制到新数组，因此添加到ArrayList是O（n）最坏的情况，但平均不变。

因此，根据您打算执行的操作，您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。 （迭代一个ArrayList在技​​术上更快，但除非你做的事情对性能非常敏感，否则你不应该担心这一点 - 它们都是常量。）

当您重用现有迭代器来插入和删除元素时，会出现使用LinkedList的主要好处。然后，可以通过仅在本地更改列表，在O（1）中完成这些操作。在数组列表中，需要移动 （即复制）数组的其余部分。另一方面，在LinkedList意味着在最坏情况下遵循O（n） （ n / 2步）中的链接，而在ArrayList ，可以在数学上计算所需位置并在O（1）中访问。

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

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

ArrayList的默认初始容量非常小（Java 1.4 中的 10 个 - 1.8）。但由于底层实现是一个数组，因此如果添加大量元素，则必须调整数组大小。当您知道要添加大量元素时，为了避免调整大小的高成本，请构造具有更高初始容量的ArrayList 。

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

由于在它们的相对系统上引用是 32 位或 64 位（即使为空），我已经为 32 位和 64 位LinkedLists和ArrayLists包含了 4 组数据。

注意： ArrayList行显示的大小用于修剪列表 - 实际上， ArrayList支持数组的容量通常大于其当前元素数。

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

结果清楚地表明LinkedList比ArrayList更多，特别是元素数量非常多。如果内存是一个因素，请避开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)

ArrayList就是你想要的。 LinkedList几乎总是（性能）错误。

为什么LinkedList糟糕：

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