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

在比 更多的用例中，摘要 with 更可取。如果您不确定 — 请从 .ArrayListArrayDequeLinkedListArrayList

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

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

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

对于链接列表<E>

• get(int index)是 O（n） （平均步长为 n/4），但 O（1） 当 或 （在这种情况下，您也可以使用 和 ）。主要优点之一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） 当 或 （在这种情况下，您也可以使用 和 ）。主要优点之一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 步（列表中间）}

对于数组列表<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

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

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

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

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

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

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

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

由于引用在其相对系统上为 32 位或 64 位（即使为空），因此我包含了 32 位和 64 位和 .LinkedListsArrayLists

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

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

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

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