ArrayList新增删除比LinkedList快？

大家在面试中会被经常被问到ArrayList和LinkedList，相信大家都能回答ArrayList是基于数组实现，LinkedList是基于链表。ArrayList适合读多写少的场景，LinkedList适合写多读少的场景， 这句结论真的是真理吗？

在实际的 Java 运行环境中，由于 CPU 缓存、内存连续性等因素的影响，这个传统结论在某些特定操作下，并不完全成立。

💡 问题一：ArrayList 在新增/删除元素的场景下效率就一定比 LinkedList 慢吗？

答案是：不一定，要看具体操作的位置！

传统观点认为：

ArrayList 新增/删除需要移动数组元素，复杂度为 O(N)。
LinkedList 只需修改指针，复杂度为 O(1)。

但这个 O(1) 的前提是，你已经找到了要操作的节点。

1. 尾部新增 (add) —— ArrayList 更快！

测试结果：

从集合头部位置新增元素
从集合中间位置新增元素
从集合尾部位置新增元素

测试结果(花费时间)：

ArrayList>LinkedList
ArrayList<LinkedList
ArrayList<LinkedList

集合	操作	复杂度	实际性能
ArrayList	尾部新增	O(1) (摊还)	非常快
LinkedList	尾部新增	O(1)	较慢

原理：

ArrayList： 尾部追加是直接在底层数组的末尾赋值，操作时间极短。即使偶尔需要进行扩容（O(N)），但平均来看仍是 O(1)。
LinkedList： 虽然是 O(1)，但它需要创建新的节点对象，并为每个节点分配内存空间。在大量新增操作中，这种创建和分配内存的开销，以及 CPU 缓存未命中 的问题，使得它比 ArrayList 慢得多。

2. 中间/头部删除 —— 性能差距不显著，甚至 ArrayList 更快！

测试结果：

从集合头部位置删除元素
从集合中间位置删除元素
从集合尾部位置删除元素

测试结果(花费时间)：

ArrayList>LinkedList
ArrayList<LinkedList
ArrayList<LinkedList

集合	操作	复杂度	实际性能
ArrayList	中间删除	O(N)	更快
LinkedList	中间删除	O(N/2) 查找到 O(1) 删除	较慢

原理：
LinkedList 的 O(1) 删除只针对已知节点。如果要在列表中间删除，必须先通过索引遍历找到该节点，其查找复杂度为 O(N/2)。

ArrayList 的优势：
尽管 ArrayList 中间删除需要移动后面的元素，但由于 ArrayList 的数据在内存中是连续存储的，CPU 在执行移动（本质上是内存拷贝）时，可以利用 CPU 缓存机制和 系统级优化，进行批量操作。而 LinkedList 的查找和操作都需要跳跃到不连续的内存位置，导致缓存频繁失效，实际性能反而可能不如 ArrayList 的数组移动。

🚀 性能验证代码

我们使用 System.nanoTime() 来精确测试 尾部新增 和 头部删除 两种场景。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class ListPerformanceTest {
    private static final int ITERATIONS = 100_000;

    public static void main(String[] args) {
        Random random = new Random();

        // 1. 尾部新增测试 (ArrayList vs LinkedList)
        testAddPerformance(new ArrayList<>(), "ArrayList 尾部新增");
        testAddPerformance(new LinkedList<>(), "LinkedList 尾部新增");
        
        System.out.println("\n--------------------------------------\n");

        // 2. 头部删除测试 (ArrayList vs LinkedList)
        // 注意：先填充数据
        List<Integer> alist = new ArrayList<>(ITERATIONS);
        List<Integer> llist = new LinkedList<>();
        for (int i = 0; i < ITERATIONS; i++) {
            alist.add(random.nextInt());
            llist.add(random.nextInt());
        }
        
        testRemoveFirstPerformance(alist, "ArrayList 头部删除");
        testRemoveFirstPerformance(llist, "LinkedList 头部删除");
    }

    // 测试尾部新增
    private static void testAddPerformance(List<Integer> list, String listName) {
        long start = System.nanoTime();
        for (int i = 0; i < ITERATIONS; i++) {
            list.add(i); // 尾部新增
        }
        long end = System.nanoTime();
        double timeMs = (end - start) / 1_000_000.0;
        System.out.printf("%s: %.2f ms\n", listName, timeMs);
    }

    // 测试头部删除 (remove(0))
    private static void testRemoveFirstPerformance(List<Integer> list, String listName) {
        long start = System.nanoTime();
        // 从头部移除 ITERATIONS / 2 次
        for (int i = 0; i < ITERATIONS / 2; i++) {
            list.remove(0); 
        }
        long end = System.nanoTime();
        double timeMs = (end - start) / 1_000_000.0;
        System.out.printf("%s: %.2f ms\n", listName, timeMs);
    }
}

💡 问题二：For 循环 vs 迭代循环遍历，你会使用哪种方式呢？

对于 ArrayList，使用标准 For 循环（带索引）最快；对于 LinkedList，使用迭代器循环更快。

原理：

for(;;)循环
迭代器迭代循环

测试结果(花费时间)：

ArrayList<LinkedList
ArrayList≈LinkedList

1. 遍历 ArrayList：标准 For 循环（带索引）最快

// 最快方式：直接通过索引访问内存连续的数组
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

原理：
ArrayList 是基于数组实现的，通过索引 list.get(i) 访问元素是 O(1) 的操作。由于内存连续，CPU 缓存命中率极高，性能最佳。

2. 遍历 LinkedList：迭代器最快

1
2
3

for (Iterator<String> it=list.iterator(); it.hasNext();) {
			it.next();
		}

原理：
LinkedList 的 get(i) 操作需要从头结点或尾结点开始遍历到索引 i，复杂度为 O(N)。因此，在标准 For 循环中每次调用 list.get(i) 都会导致 O(N) 的开销，总复杂度达到 O(N^2)，性能灾难！