到目前为止，除了人们普遍认为LinkedList比ArrayList“多得多”之外，似乎没有人解决这些列表中每一个的内存占用问题，所以我做了一些数字处理，以证明这两个列表对于N个空引用所占的空间。

由于引用在其相对系统上是32位或64位（即使为空），因此我为32位和64位LinkedList和ArrayList包含了4组数据。

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

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

结果清楚地表明，LinkedList比ArrayList多得多，尤其是元素数非常高的情况。如果内存是一个因素，请避开LinkedList。

我使用的公式如下，如果我做错了什么，请告诉我，我会改正的对于32位或64位系统，b’是4或8，而n’是元素的数量。注意mods的原因是因为java中的所有对象都将占用8字节的倍数空间，而不管是否全部使用。

阵列列表：

ArrayList对象头+大小整数+modCount整数+数组引用+（数组项目头+b*n）+MOD

链接列表：

LinkedList对象标头+大小整数+modCount整数+对标头的引用+对页脚的引用+（节点对象开销+对上一元素的引用+下一元素的参考+对元素的引用）*n）+MOD（节点对象，8）*n+MOD， 8)

1） 基础数据结构

ArrayList和LinkedList之间的第一个区别在于，ArrayList由Array支持，而LinkedList由LinkedList支持。这将导致性能的进一步差异。

2） LinkedList实现Deque

ArrayList和LinkedList之间的另一个区别是，除了List接口之外，LinkedList还实现了Deque接口，该接口为add（）和poll（）以及其他几个Deque函数提供先进先出操作。3） 在ArrayList中添加元素如果不触发Array的重新调整大小，则在ArrayList中添加元素是O（1）操作，在这种情况下，它变为O（log（n））。另一方面，在LinkedList中添加一个元素则是O（2）操作，因为它不需要任何导航。

4） 从位置移除元素

为了从特定索引中删除元素，例如通过调用remove（index），ArrayList执行复制操作，使其接近O（n），而LinkedList需要遍历到该点，这也使其成为O（n/2），因为它可以根据接近度从任意方向遍历。

5） 遍历ArrayList或LinkedList

迭代是LinkedList和ArrayList的O（n）操作，其中n是元素的数量。

6） 从位置检索元素

get（index）操作在ArrayList中为O（1），而在LinkedList中为其O（n/2），因为它需要遍历该条目。虽然，在大O符号中，O（n/2）只是O（n），因为我们忽略了那里的常数。

7） 内存

LinkedList使用一个包装对象Entry，这是一个静态嵌套类，用于存储数据和下一个和上一个节点，而ArrayList只在Array中存储数据。

因此，除了Array在将内容从一个Array复制到另一个Array时执行重新调整大小操作的情况外，ArrayList的内存需求似乎比LinkedList少。

如果Array足够大，那么此时可能会占用大量内存并触发垃圾收集，这会降低响应时间。

从ArrayList与LinkedList之间的所有差异来看，ArrayList在几乎所有情况下都是比LinkedList更好的选择，除非您经常执行add（）操作而不是remove（）或get（）操作。

修改链接列表比修改ArrayList更容易，尤其是当您从开始或结束处添加或删除元素时，因为链接列表内部保留了这些位置的引用，并且可以在O（1）时间内访问。

换句话说，您不需要遍历链接列表就可以到达要添加元素的位置，在这种情况下，添加就变成了O（n）操作。例如，在链接列表中间插入或删除元素。

在我看来，在Java中，使用ArrayList而不是LinkedList来实现大多数实际用途。

您可以根据对该特定列表执行的操作的时间复杂性，使用一个而不是另一个。

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

是的，我知道，这是一个古老的问题，但我会投入我的两分钱：

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于LinkedLists在使用ListIterator导航到列表中间后相对快速地插入和删除元素的能力。

有一个常见的用例LinkedList优于ArrayList：队列。但是，如果您的目标是性能，那么您也应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且能够提前分配所有内存），而不是LinkedList，或者使用CircularArray实现。（是的，它来自2001年，因此您需要对其进行一般化，但我得到的性能比与最近一篇JVM文章中引用的性能比相当）

与LinkedList相比，Summary ArrayList和ArrayDeque在更多的用例中更可取。如果您不确定，请从ArrayList开始。

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

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

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

对于LinkedList＜E＞

get（int index）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用getFirst（）和getLast（））。LinkedList的主要优点之一add（int index，E元素）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用addFirst（）和addLast（）/add（））。LinkedList的主要优点之一remove（int index）为O（n）（平均步数为n/4），但当index=0或index=list.size（）-1时为O（1）（在这种情况下，还可以使用removeFirst（）和removeLast（））。LinkedList的主要优点之一Iterator.remove（）为O（1）。LinkedList的主要优点之一ListIterator.add（E元素）为O（1）。LinkedList的主要优点之一

注：许多操作平均需要n/4步，在最佳情况下（例如索引=0）需要恒定的步数，在最坏情况下（列表中间）需要n/2步

对于ArrayList＜E＞

get（int索引）为O（1）。ArrayList的主要优势<E>add（E元素）是O（1）摊销，但O（n）最坏情况，因为数组必须调整大小并复制add（int索引，E元素）为O（n）（平均n/2步）remove（int索引）为O（n）（平均n/2步）Iterator.remove（）为O（n）（平均为n/2步）ListIterator.add（E元素）为O（n）（平均n/2步）

注：许多操作平均需要n/2步，在最佳情况下（列表末尾）需要恒定的步数，在最坏情况下（开始列表）需要n步

LinkedList＜E＞允许使用迭代器进行恒定时间的插入或删除，但只能对元素进行顺序访问。换句话说，您可以向前或向后遍历列表，但在列表中找到位置所需的时间与列表的大小成正比。Javadoc表示“索引到列表中的操作将从开始或结束遍历列表，以较近者为准”，因此这些方法平均为O（n）（n/4步），尽管索引=0时为O（1）。

另一方面，ArrayList＜E＞允许快速随机读取访问，因此您可以在恒定时间内获取任何元素。但是，除了末端之外，任何地方的添加或删除都需要将后面的所有元素转换过来，要么打开，要么填补空白。此外，如果添加的元素超过了基础数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组，因此在最坏的情况下，添加到ArrayList是O（n），但平均来说是常量。

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

使用LinkedList的主要好处是重用现有迭代器来插入和删除元素。然后，这些操作可以在O（1）中通过仅本地更改列表来完成。在阵列列表中，需要移动（即复制）阵列的其余部分。另一方面，在LinkedList中查找意味着在最坏情况下遵循O（n）（n/2步）中的链接，而在ArrayList中，所需位置可以通过数学计算并在O（1）中访问。

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

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

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

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

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

TL；DR由于现代计算机体系结构，ArrayList对于几乎所有可能的用例都将显著提高效率，因此除了一些非常独特和极端的情况外，应避免使用LinkedList。

理论上，LinkedList的add（E元素）有一个O（1）

此外，在列表中间添加元素应该非常有效。

实践非常不同，因为LinkedList是一个缓存敌对数据结构。从性能POV来看，LinkedList很少比缓存友好的ArrayList性能更好。

以下是在随机位置插入元素的基准测试结果。如您所见，数组列表效率更高，但理论上，每次在列表中间插入都需要“移动”数组后面的n个元素（值越低越好）：

使用新一代硬件（更大、更高效的缓存），结果更为确凿：

LinkedList需要更多的时间来完成相同的任务。源源代码

这主要有两个原因：

主要是LinkedList的节点在内存中随机分布。RAM（“随机存取存储器”）不是真正随机的，需要将内存块提取到缓存中。此操作需要时间，并且当此类提取频繁发生时，缓存中的内存页需要一直被替换->缓存未命中->缓存效率不高。ArrayList元素存储在连续内存中——这正是现代CPU架构正在优化的目标。Secondary LinkedList需要保留/转发指针，这意味着与ArrayList相比，每个存储值的内存消耗是3倍。

顺便说一句，DynamicIntArray是一个自定义ArrayList实现，它保存Int（原始类型）而不是Object，因此所有数据都是相邻存储的，因此效率更高。

需要记住的一个关键因素是，获取存储块的成本比访问单个存储单元的成本更重要。这就是为什么读卡器1MB的顺序存储器比从不同内存块读取此数据量快x400倍的原因：

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

来源：每个程序员都应该知道的延迟数

为了让这一点更加清晰，请检查在列表开头添加元素的基准。这是一个用例，从理论上讲，LinkedList应该非常出色，而ArrayList应该呈现出糟糕甚至更糟糕的用例结果：

注意：这是C++标准库的一个基准测试，但我以前的经验表明C++和Java的结果非常相似。源代码

复制连续的大量内存是一种由现代CPU改变理论优化的操作，实际上也使ArrayList/Vector更加高效

致谢：这里发布的所有基准都是由Kjell Hedström创建的。在他的博客上可以找到更多的数据