ArrayList 与 LinkedList

ArrayList 的扩容机制

关于 ArrayList 扩容，你仅需要记住以下两点（源码比较简单，本文不再进行源码分析）：

• ArrayList 内部数组默认初始大小为 10；
• 每次扩容后，新的数组大小变为原来的 1.5 倍。

LinkedList 插入操作真比 ArrayList 快？

在比较 ArrayList 和 LinkedList 时，通常会认为 ArrayList 适用于“大量随机访问”的场景，而 LinkedList 则适用于“大量随机插入”的场景。前一个结论毋庸置疑，但后一个结论真的正确吗？

我们使用如下代码分别对 ArrayList 和 LinkedList 进行随机插入测试：

public void arrayLisAdd(int elementCount, int loopCount) {
    List<Integer> list = IntStream.range(0, elementCount).boxed()
        .collect(Collectors.toCollection(ArrayList::new));
    IntStream.range(0, loopCount)
        .forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount)， i));
}
public void linkedListAdd(int elementCount, int loopCount) {
    List<Integer> list = IntStream.range(0, elementCount).boxed()
        .collect(Collectors.toCollection(LinkedList::new));
    IntStream.range(0, loopCount)
        .forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount), i));
}

运行结果可能让你大跌眼睛，在我的实际测试中，elementCount 和 loopCount 都为 10 万，ArrayList 用时 1.3 s，而 LinkedList 则用时 25 s。

虽然 LinkedList 的插入操作的时间复杂度为 O(1)，但在插入元素前，你需要先通过遍历获取到那个节点，然后再执行插入操作，而前者也是有开销的，不能仅考虑插入操作本身的代价。

就连 LinkedList 类的作者 Josh Bloch 也表示：Does anyone actually use LinkedList? I wrote it, and I never use is。

可见理论和实际是有一定差距的，在下定论之前，最好实际测试一番。