何时通过ArrayList使用LinkedList？

我一直只使用一个：

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

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

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

TL; DR ArrayList与ArrayDeque在优选的多更多的用例比LinkedList。不知道 – 刚开始ArrayList。

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

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

对于 LinkedList<E>

• get(int index)是O（n / 4）平均值
• add(E element)是O（1）
• add(int index, E element)是O（n / 4）的平均值，
  但O（1）时index = 0 <—主要受益LinkedList<E>
• remove(int index)是O（n / 4）平均值
• Iterator.remove()是O（1） <—的主要好处之一LinkedList<E>
• ListIterator.add(E element)是O（1） <—的主要好处之一LinkedList<E>

^{注：O（n / 4）是平均值，O（1）最好情况（例如索引= 0），O（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 / 2）平均值
• remove(int index)是O（n / 2）平均值
• Iterator.remove()是O（n / 2）平均值
• ListIterator.add(E element)是O（n / 2）平均值

^{注：O（n / 2）是平均值，O（1）最好的情况（列表的结尾），O（n）最差的情况（列表的开始）}

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

ArrayList<E>另一方面，允许快速的随机读取访问，所以你可以在任何时间获取任何元素。但是，除了最终的目的地之外，添加或删除任何内容都需要将所有后面的元素转移，以便开放或填补空白。此外，如果您比下面阵列的容量添加更多的元件，一个新的数组（1.5倍的尺寸）被分配，而旧的阵列被复制到新的一个，因此添加到ArrayList是O（n）的在最坏的但平均情况不变。

所以根据你打算做的操作，你应该选择相应的实现。迭代任何一种List几乎同样便宜。（迭代迭代在ArrayList技术上更快，但除非你对性能敏感，否则不应该担心这一点 – 它们都是常量。）

LinkedList当您重新使用现有的迭代器插入和删除元素时，使用a的主要好处就会产生。这些操作可以在O（1）中通过仅在本地修改列表完成。在数组列表中，数组的其余部分需要移动（即复制）。另一方面，LinkedList在O（n / 2）中寻找最差情况下的链接，而在ArrayList期望的位置可以通过数学计算并在O（1）中访问。

LinkedList由于这些操作是O（1），而它们是O（n） for ，因此在添加或从列表头部添加或删除时使用a的另一个好处ArrayList。请注意，这ArrayDeque可能是一个很好的替代方法，LinkedList用于从头部添加和删除，但它不是List。

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

an的默认初始容量ArrayList非常小（10个来自Java 1.4 – 1.8）。但是由于底层实现是一个数组，因此如果添加大量元素，则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的高成本，请使用ArrayList较高的初始容量构建。

到目前为止，似乎没有人能够解决这些列表中每个列表的内存占用情况，除了a LinkedList比“更多”更普遍的共识之外，ArrayList所以我进行了一些数字处理，以准确演示两个列表对N个空引用的占用程度。

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

注意：所显示的ArrayList线的尺寸用于修剪列表 – 实际上，an中的后台阵列的容量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)