何时通过ArrayList使用LinkedList？
我一直只使用一个：
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步），但O（1）当index = 0 <--- 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步，最佳情况下步数不变（例如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的默认初始容量非常小（10个来自Java 1.4 - 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糟糕：
ArrayList时慢。 ArrayList相同，反正它可能会明显变慢。 LinkedList是很令人震惊的，因为它可能是错误的选择。