对于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。

ArrayList是您想要的。LinkedList几乎总是一个（性能）bug。

为什么LinkedList很糟糕：

它使用了大量小内存对象，因此影响了整个过程的性能。许多小对象不利于缓存位置。任何索引操作都需要遍历，即具有O（n）性能。这在源代码中并不明显，导致算法O（n）比使用ArrayList时慢。获得好的表现是很棘手的。即使big-O性能与ArrayList相同，它也可能会明显变慢。在源代码中看到LinkedList很刺耳，因为它可能是错误的选择。

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

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

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

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

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

这取决于您将在列表中执行更多操作。

ArrayList访问索引值更快。插入或删除对象时，情况更糟。

要了解更多信息，请阅读任何关于数组和链接列表之间区别的文章。