何时在 Java 中使用 LinkedList 而不是 ArrayList？

Question

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

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

我使用 interface 作为 portability 的类型名称，因此当我提出这样的问题时，我可以重新编写我的代码。

什么时候应该使用 LinkedList ArrayList 反之亦然？

原文由 sdellysse 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

总结 ArrayList 和 ArrayDeque 在 更多 的用例中比 LinkedList 更可取。如果您不确定 — 只需从 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<E>
• add(int index, E element) 是 O(n) （平均有 n/4 步），但是当 index = 0 或 index = list.size() - 1 时为 O(1) （在这种情况下，您可以也使用 addFirst() 和 addLast() / add() ）。 的主要好处之一 LinkedList<E>
• remove(int index) 是 O(n) （平均有 n/4 步），但是当 index = 0 或 index = list.size() - 1 时为 O(1) （在这种情况下，您可以也使用 removeFirst() 和 removeLast() ）。 的主要好处之一 LinkedList<E>
• Iterator.remove() 是 O(1) 。 的主要好处之一 LinkedList<E>
• ListIterator.add(E element) 是 O(1) 。 的主要优点之一 LinkedList<E>

注意：许多操作平均需要 n/4 步，最佳情况下的步数 _恒定_（例如 index = 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 步），尽管 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 - 1.8 为 10）。但是由于底层实现是一个数组，如果添加很多元素，则必须调整数组的大小。为了避免在您知道要添加大量元素时调整大小的高成本，请构建具有更高初始容量的 ArrayList 。

如果从数据结构的角度来理解这两种结构，LinkedList 基本上是一个包含头节点的顺序数据结构。 Node 是两个组件的包装器：一个 T 类型的值 [通过泛型接受] 和另一个对链接到它的 Node 的引用。所以，我们可以断言它是一个递归数据结构（一个节点包含另一个节点，另一个节点有另一个节点，依此类推……）。如上所述，在 LinkedList 中添加元素需要线性时间。

ArrayList 是一个可增长的数组。它就像一个常规数组。在幕后，当添加一个元素并且 ArrayList 已经满载时，它会创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新数组，并且要添加的元素也放置在指定的索引处。

原文由 Jonathan Tran 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

到目前为止，除了 LinkedList 比 ArrayList “多得多”这一普遍共识之外，似乎没有人解决过这些列表中的每一个的内存占用问题，所以我做了一些数字运算演示两个列表究竟占用了多少 N 个空引用。

由于引用在其相关系统上是 32 位或 64 位（即使为 null），因此我包含了 4 组 32 位和 64 位数据 LinkedLists 和 ArrayLists 。

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

注意 2：（ 感谢 BeeOnRope） 由于 CompressedOops 现在是 JDK6 中期及更高版本的默认设置，下面针对 64 位机器的值将基本上匹配它们的 32 位对应值，当然除非您特别将其关闭。

---

---

结果清楚地表明 LinkedList 比 ArrayList 多很多，尤其是在元素数量非常多的情况下。如果内存是一个因素，请避开 LinkedLists 。

我使用的公式如下，如果我做错了什么，请告诉我，我会修复它。对于 32 位或 64 位系统，’b’ 是 4 或 8，’n’ 是元素的数量。注意mods的原因是因为java中的所有对象无论是否全部使用都会占用8字节空间的倍数。

数组列表：

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 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)

原文由 Numeron 发布，翻译遵循 CC BY-SA 4.0 许可协议