如果您的代码有add（0）和remove（0），请使用LinkedList，这是更漂亮的addFirst（）和removeFirst（）方法。否则，请使用ArrayList。

当然，Guava的ImmutableList是你最好的朋友。

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

算法：Big Oh符号（存档）

ArrayList适用于一次写入、多次读取或追加，但不适用于从前面或中间添加/删除。

数组列表本质上是一个具有添加项等方法的数组（您应该使用通用列表）。它是可以通过索引器（例如[0]）访问的项的集合。它意味着从一个项目到下一个项目的进展。

链接列表指定从一个项目到下一个项目（项目A->项目b）的进度。您可以使用数组列表获得相同的效果，但链接列表绝对会说明前一个列表后面应该包含哪些项。

以下是ArrayList和LinkedList以及CopyOnWrite ArrayList中的Big-O符号：

阵列列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite阵列列表

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些，您必须决定选择什么。：）

ArrayList和LinkedList都实现了List接口，它们的方法和结果几乎相同。然而，它们之间几乎没有区别，这取决于需求，使一个优于另一个。

阵列列表与链接列表

1） 搜索：与LinkedList搜索操作相比，ArrayList搜索操作非常快。ArrayList中的get（int index）给出了O（1）的性能，而LinkedList的性能为O（n）。

原因：ArrayList为其元素维护基于索引的系统，因为它隐式使用数组数据结构，这使得在列表中搜索元素的速度更快。另一方面，LinkedList实现了双链接列表，这需要遍历所有元素来搜索元素。

2） 删除：LinkedList删除操作提供O（1）性能，而ArrayList提供可变性能：最坏情况下（删除第一个元素时）为O（n），最好情况下（移除最后一个元素时，为O（2）。

结论：LinkedList元素删除速度比阵列列表。

原因：LinkedList的每个元素都有两个指针（地址），指向列表中的两个相邻元素。因此，移除仅需要改变将要移除的节点的两个相邻节点（元素）中的指针位置。当在ArrayList中时，需要移动所有元素以填充移除的元素所创建的空间。

3） 插入性能：LinkedList add方法提供O（1）性能，而ArrayList在最坏情况下提供O（n）性能。原因与删除说明相同。

4） 内存开销：ArrayList维护索引和元素数据，而LinkedList维护相邻节点的元素数据和两个指针

因此LinkedList中的内存消耗相对较高。

这些类之间几乎没有相似之处，如下所示：

ArrayList和LinkedList都是List接口的实现。它们都保持元素插入顺序，这意味着在显示ArrayList和LinkedList元素时，结果集将具有元素插入列表的相同顺序。这两个类都是非同步的，可以使用Collections.synchronizedList方法显式同步。这些类返回的迭代器和listIterator是快速失败的（如果在创建迭代器之后的任何时候对列表进行结构修改，除了通过迭代器自己的remove或add方法之外，其他任何方式，迭代器都会抛出ConcurrentModificationException）。

何时使用LinkedList，何时使用ArrayList？

如上所述，与ArrayList（O（n））相比，插入和删除操作在LinkedList中提供了良好的性能（O（1））。因此，若应用程序中需要频繁添加和删除，则LinkedList是最佳选择。搜索（get方法）操作在Arraylist（O（1））中很快，但在LinkedList（O（n））中不快因此，如果添加和删除操作更少，搜索操作需求更多，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创建的。在他的博客上可以找到更多的数据