我已经阅读了答案，但有一种情况是，我总是使用LinkedList而不是ArrayList，我想分享它来听取意见：

每次我有一个方法返回从DB获得的数据列表时，我总是使用LinkedList。

我的理由是，因为不可能确切地知道我得到了多少结果，所以不会浪费内存（如ArrayList中的容量和实际元素数量之间的差异），也不会浪费时间复制容量。

至于ArrayList，我同意至少应该始终使用具有初始容量的构造函数，以尽可能减少数组的重复。

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来实现大多数实际用途。

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

我应该何时使用LinkedList？大多数情况下使用堆栈时，或使用缓冲区时。我应该何时使用ArrayList？只有在使用索引时，否则您可以将HashTable与链接列表一起使用，那么您将得到：

哈希表+链接列表

通过密钥O（1）访问，通过键O（1）插入，通过键O（1）拆除在使用版本控制时，使用O（1）实现RemoveAll/SetAll有一个技巧

这似乎是一个很好的解决方案，在大多数情况下，你应该知道：HashTable占用了大量磁盘空间，所以当您需要管理1000000个元素列表时，它可能会变得很重要。这可能发生在服务器实现中，但在客户端中很少发生。

还可以看看红黑树

随机访问日志（n），插入日志（n），删除日志（n）

以下是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)

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

我知道这是一篇老帖子，但我真的不敢相信没有人提到LinkedList实现了Deque。只需查看Deque（和Queue）中的方法；如果您希望进行公平的比较，请尝试对ArrayDeque运行LinkedList，并进行功能比较。