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创建的。在他的博客上可以找到更多的数据

见原始答案下方作者的2021更新。

原答案（2011年）

作为一个在非常大规模的SOA web服务上做了大约十年操作性能工程的人，我更喜欢LinkedList而不是ArrayList的行为。虽然LinkedList的稳态吞吐量更差，因此可能会导致购买更多硬件，但ArrayList在压力下的行为可能会导致集群中的应用程序以近乎同步的方式扩展其阵列，而对于较大的阵列大小，可能会导致应用程序缺乏响应能力，在压力下停机，这是灾难性的行为。

类似地，您可以从默认的吞吐量固定垃圾收集器中获得更好的应用吞吐量，但一旦您获得了具有10GB堆的java应用程序，您就可以在完全GC期间锁定应用程序25秒，这会导致SOA应用程序超时和失败，如果太频繁，还会破坏SLA。尽管CMS收集器占用了更多的资源，并且没有实现相同的原始吞吐量，但它是一个更好的选择，因为它具有更可预测性和更小的延迟。

如果您所指的性能是吞吐量，并且可以忽略延迟，那么ArrayList只是性能的更好选择。根据我的工作经验，我不能忽视最坏情况下的延迟。

更新（2021 8月27日——10年后）

这个答案（也是我在SO问题上最受欢迎的答案）很可能是错误的（原因在下面的评论中概述）。我想补充一点，ArrayList将优化内存的顺序读取，并最小化缓存线和TLB未命中等。相比之下，当阵列增长超过边界时的复制开销可能无关紧要（可以通过高效的CPU操作完成）。考虑到硬件趋势，随着时间的推移，这个答案可能会变得更糟。LinkedList可能有意义的唯一情况是，如果您有数千个列表，其中任何一个都可能增长到GB大小，但在分配列表时无法做出正确的猜测，并且将它们全部设置为GB大小，则会炸毁堆。如果你发现了这样的问题，那么无论你的解决方案是什么，都需要重新设计（我不想轻率地建议重新设计旧代码，因为我自己维护了一堆又一堆的旧代码，但这是一个很好的例子，因为原始设计已经过时，确实需要扔掉）。尽管如此，我还是会把我几十年来的糟糕观点留在那里，让你读一读。简单、合乎逻辑，而且非常错误。

到目前为止，除了人们普遍认为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)

对于ArrayList和LinkedList，remove（）和insert（）的运行时效率都为O（n）。然而，线性处理时间背后的原因来自两个非常不同的原因：

在ArrayList中，您可以找到O（1）中的元素，但实际上删除或插入某些元素会使其成为O（n），因为以下所有元素都需要更改。

在LinkedList中，实际到达所需元素需要O（n），因为我们必须从一开始就开始，直到达到所需的索引。实际上，移除或插入是常量，因为我们只需要为remove（）更改1个引用，为insert（）更改2个引用。

插入和删除这两项中的哪一项更快取决于发生的位置。如果我们更接近开始，LinkedList将更快，因为我们必须经过相对较少的元素。如果我们接近末尾，ArrayList将更快，因为我们在恒定的时间内到达那里，只需更改紧随其后的几个剩余元素。如果正好在中间完成，LinkedList将更快速，因为遍历n个元素比移动n个值更快。

好处：虽然无法为ArrayList创建这两个方法O（1），但实际上在LinkedList中有一种方法可以做到这一点。假设我们想在整个列表中删除和插入元素。通常，您可以使用LinkedList从头开始每个元素，我们也可以使用迭代器“保存”当前正在处理的元素。在迭代器的帮助下，当在LinkedList中工作时，remove（）和insert（）的效率为O（1）。使其成为我所知的唯一性能优势，LinkedList总是优于ArrayList。

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

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

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

首先使用Vector而不是ArrayList，因为您可以覆盖insuranceCapasity方法，在ArrayList中是私有的，并添加1.5大小的当前数组https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#ensureCapacity-整数-

在很多情况下，linkedList会更好，las有一个很大的优势：你可以高频插入数据，所以列表的大小变化很快，你不能为数字元素分配大小。从理论上讲，你可能会遇到“内存不足”之类的错误，但在现代计算机中，你有16G和交换磁盘，所以如果你列出的是billoins元素，与15-20年前相比，你可能失败。