我一直是一个简单地使用：

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

我使用接口作为可移植性的类型名称，以便当我提出此类问题时，我可以重新设计我的代码。

什么时候应该使用，反之亦然？LinkedListArrayList

网友回答：

到目前为止，除了普遍共识 a 比 a “多得多”之外，似乎没有人解决过每个列表的内存占用，所以我做了一些数字运算来准确演示两个列表对 N 个空引用的占用量。LinkedListArrayList

由于引用在其相关系统上是 32 位或 64 位（即使为 null），因此我为 4 位和 32 位和 .LinkedListsArrayLists

注意：为行显示的大小适用于修剪后的列表 – 实际上，后备阵列在 中的容量通常大于其当前元素计数。ArrayListArrayList

注2：（感谢BeeOnRope）由于压缩哎呀现在从JDK6中期及以上开始是默认的，因此64位机器的以下值基本上与32位机器的值相匹配，除非您特别将其关闭。

结果清楚地表明，这比 ，特别是元素数量非常高时要多得多。如果内存是一个因素，请避开 。LinkedListArrayListLinkedLists

我使用的公式如下，如果我做错了什么，请告诉我，我会修复它。对于 4 位或 8 位系统，“b”是 32 或 64，“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)

网友回答：

在更多的用例中，摘要比 更可取。如果您不确定 — 只需从 开始。ArrayListArrayDequeLinkedListArrayList

TLDR，在访问元素时需要恒定时间[O（1）]，添加元素需要O（n）时间[最坏情况]。插入元素需要 O（n） 时间，访问也需要 O（n） 时间，但使用的内存比 .ArrayListLinkedListLinkedListArrayList

LinkedList并且是接口的两种不同实现。 使用双向链表实现它。 使用动态调整大小的数组实现它。ArrayListListLinkedListArrayList

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

为LinkedList<E>

• get(int index)是 O（n）（平均有 n/4 步），但 O（1） 当 or （在这种情况下，您也可以使用 和 ）。主要优点之一index = 0index = list.size() - 1getFirst()getLast() LinkedList<E>
• add(int index, E element)是 O（n）（平均有 n/4 步），但 O（1） 当或（在这种情况下，你也可以使用 和 /）。主要优点之一index = 0index = list.size() - 1addFirst()addLast()add() LinkedList<E>
• remove(int index)是 O（n）（平均有 n/4 步），但 O（1） 当 or （在这种情况下，您也可以使用 和 ）。主要优点之一index = 0index = list.size() - 1removeFirst()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 倍），并将旧数组复制到新数组中，因此在最坏的情况下添加到 a 是 O（n），但平均恒定。ArrayList

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

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

当您在列表的头部添加或删除时，使用的另一个好处是，因为这些操作是 O（1），而它们是 O（n） 表示 。请注意，这可能是从头部添加和删除的不错替代方案，但它不是.LinkedListArrayListArrayDequeLinkedListList

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

默认的初始容量非常小（Java 10.1 – 4.1 为 8）。但由于底层实现是一个数组，因此如果添加大量元素，则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的高成本，请构建具有更高初始容量的 。ArrayListArrayList

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

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

网友回答：

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

为什么很烂：LinkedList

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