我的经验法则是，如果我需要一个集合（即不需要是一个列表），那么如果你事先知道大小，或者可以自信地知道大小，或知道它不会有太大变化，那么就使用ArrayList。如果您需要随机访问（即使用get（index）），请避免LinkedList。基本上，只有当您不需要索引访问并且不知道正在分配的集合的（近似）大小时，才使用LinkedList。此外，如果您要进行大量添加和删除（再次通过Collection接口），则LinkedList可能更可取。

请参阅Java教程-列表实现。

我在这里看到的一个测试只进行一次测试。但我注意到的是，您需要多次运行这些测试，最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例，我需要向列表中添加/删除项目，该列表将增加到大约500个项目。在我的测试中，LinkedList的发布速度更快，LinkedList约为50000 NS，ArrayList约为90000NS。。。给予或索取。请参见下面的代码。

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

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

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

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

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

ArrayList是可随机访问的，而LinkedList扩展和删除元素非常便宜。在大多数情况下，ArrayList都可以。

除非您创建了大量列表并测量了瓶颈，否则您可能永远不需要担心差异。