插入时 ArrayList、LinkedList、Vector 谁更快？

直接回答

需要先说明测试条件。ArrayList 尾部追加的摊销成本通常是 O(1)，中间插入需移动引用；LinkedList 已定位后的插入成本低，但索引定位最坏 O(n)，还要分配节点；Vector 也基于数组，常用方法带同步。比较前必须说清插入位置、容量与线程数。

讲清原理

如果反复尾部追加，数组只有部分时刻需要扩容复制；不能用一次扩容的 O(n) 代表每次追加成本。若在链表某个已知游标附近连续插入，定位可以复用；若每次都随机索引，定位成本会改变结论。

数组有可能预留空槽，链表有节点和前后引用开销。缓存、对象分配、GC 与 JVM 优化也影响实际耗时，不能从渐进复杂度直接推导某台机器的毫秒数。

例子与易错点

要测量，可用 JMH 分别设置尾插、头插、随机插入和已有游标插入；在基准外准备等价初始数据，控制预分配条件，预热并用多个进程隔离。还应观察吞吐和分配量，而不只是一次 System.nanoTime 差值。

本题不给未经运行的性能排名。Vector 的锁也不意味着任何测试都必然最慢，某些同步可能被 JVM 优化；测量结论只适用于记录下来的条件。

相关题：第 10 题、第 20 题、第 23 题、第 25 题、第 49 题。