到目前为止，似乎没有人除了一般共识认为 LinkedList 占用的内存比 ArrayList 更多之外，还谈到这些列表的内存占用量，因此我进行了一些数据计算，以演示这两个列表对 N 个空引用占用的实际内存大小。

由于参考系统的引用大小（即使为空）为 32 位或 64 位，因此我为 32 位和 64 位 LinkedLists 和 ArrayLists 包含了 4 组数据。

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

注意 2：（感谢 BeeOnRope）由于 CompressedOops 现在是 JDK6 中间以及更高版本的默认设置，因此除非你明确关闭它，否则 64 位机器上的值基本上将与它们的 32 位对应项相同。

结果清楚地显示了，尤其是在非常高的元素数量下，LinkedList所需的内存远远超过ArrayList。如果内存是一个问题，就要避开使用LinkedList。

我使用的公式如下，如果有任何错误，让我知道，我会修复它。 'b'代表32位或64位系统中的4或8，'n'代表元素数量。请注意，进行取模的原因是因为Java中的所有对象都将占用8个字节的空间，无论是否完全使用。

ArrayList：

ArrayList对象头 + 大小整数 + modCount整数 + 数组引用 + (数组对象头 + b * n) + MOD(数组对象，8) + MOD(ArrayList对象，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 对象头 + size 整数 + modCount 整数 + 对头的引用 + 对尾的引用 + (节点对象开销 + 前一元素的引用 + 后一元素的引用 + 元素的引用) * n) + MOD(节点对象, 8) * n + MOD(LinkedList 对象, 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和ArrayDeque比LinkedList更可取。如果您不确定，可以先使用ArrayList。

简而言之，在ArrayList中，访问元素需要常数时间[O(1)]，添加元素需要O(n)时间[最坏情况]。在LinkedList中，插入元素需要O(n)时间，访问也需要O(n)时间，但是LinkedList比ArrayList使用更多的内存。

LinkedList和ArrayList是List接口的两种不同实现。 LinkedList使用双向链表实现，而ArrayList使用动态调整大小的数组实现。

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

针对 LinkedList：

• 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 ：

• get(int index) 是 O(1) 的。 ArrayList 的主要优点之一
• 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 允许使用迭代器进行常数时间插入或删除操作，但只能顺序访问元素。换句话说，您可以向前或向后遍历列表，但查找列表中的位置需要与列表大小成正比的时间。Javadoc说“索引列表的操作将从开始或结束遍历列表，以距离更近的一端为准”，因此这些方法平均情况下为 O(n)（n/4步），但在 index = 0 时为 O(1)。

另一方面，ArrayList 允许快速随机读取访问，因此您可以在常数时间内获取任何元素。但是，从任何位置添加或删除都需要将后面的所有元素移动，以创建一个空间或填补间隙。此外，如果添加的元素超过底层数组的容量，则分配一个新数组（大小为原来的1.5倍），并将旧数组复制到新数组中，因此在最坏情况下，添加到 ArrayList 的时间复杂度为 O(n)，但平均情况下为常数时间。

因此，根据您打算执行的操作，您应相应地选择实现。对任何一种列表进行迭代实际上都是相当便宜的。(虽然在 ArrayList 上进行迭代技术上更快，但除非您在做一些真正需要高性能的事情，否则不必担心这一点，它们都是常数时间。)

使用 LinkedList 的主要好处在于您可以重用现有的迭代器来插入和删除元素。这些操作可以通过仅在本地更改列表来以 O(1) 的复杂度执行。在数组列表中，剩余的数组需要被移动(即复制)。另一方面，在 LinkedList 中寻找位置意味着在最坏情况下需要花费 O(n)（n/2 步），而在 ArrayList 中，可以通过数学计算得出所需的位置，并在 O(1) 中访问它。

另一个使用LinkedList的好处是，在列表头部添加或删除元素的操作是O(1)，而对于ArrayList来说则是O(n)。请注意，ArrayDeque可能是从列表头部添加或删除元素的好选择，但它不是一个List。
此外，如果你有大型列表，请记住内存使用也是不同的。LinkedList的每个元素有更多的开销，因为它们还存储了指向前一个和后一个元素的指针。ArrayList没有这种开销。然而，ArrayList占用的内存与其容量分配的空间大小相同，而不管实际添加了多少元素。
ArrayList的默认初始容量相当小（从Java 1.4到1.8是10）。但由于其底层实现是一个数组，如果你添加了很多元素，数组必须被调整大小。为避免在知道要添加很多元素时重新分配大小的高成本，请使用更高的初始容量构造ArrayList。

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

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