Java技术疑问：LinkedList的插入操作真的比ArrayList更快吗？

嘿，这个现象其实挺正常的，咱们从底层结构和你的测试场景来拆解一下：

1. 两种集合的底层实现差异 #

• ArrayList：基于动态数组实现，底层是一块连续的内存空间。当你调用add(E)（默认尾部插入）时：
  • 如果数组还有剩余容量，直接在尾部下标位置赋值，这是个O(1)的操作，几乎没有额外开销；
  • 就算数组满了需要扩容，JVM会一次性分配新的更大的数组，然后把旧数组元素批量复制过去——这种扩容是均摊O(1)的，10000次插入的话，扩容次数非常少（初始容量10，每次扩容1.5倍，总共扩容不到10次），对整体耗时影响极小。
• LinkedList：基于双向链表实现，每个元素都是一个独立的Node对象，包含数据、前驱指针、后继指针。调用add(E)时，需要：
  • 新建一个Node实例（涉及对象内存分配、构造函数调用）；
  • 修改链表尾部节点的后继指针，再把新节点设为尾部——这两步虽然也是O(1)，但对象实例化和指针操作的开销，比数组直接赋值要大得多。

2. 缓存友好性的影响 #

ArrayList的数组是连续内存，CPU的缓存机制可以高效地预加载连续的内存块，缓存命中率极高；而LinkedList的节点是分散在堆内存中的各个位置，CPU缓存很难命中，每次访问节点都可能需要从主存读取，这也会拖慢整体速度。

3. 你的测试场景刚好放大了ArrayList的优势 #

你的测试是连续10000次尾部插入，这完全是ArrayList的舒适区。如果换成随机位置插入/删除，比如在列表中间操作，那LinkedList的表现会反过来比ArrayList好——因为ArrayList需要移动插入点后面的所有元素，而LinkedList只需要修改几个指针。

补全你的测试代码（方便其他读者参考）：

// LinkedList 测试
List<String> strLnkdList = new LinkedList<String>();
long start1 = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    strLnkdList.add("Test"+i);
}
long end1 = System.currentTimeMillis();
System.out.println("LinkedList Time in millis: " + (end1-start1));

// ArrayList 测试
List<String> strArrayList = new ArrayList<String>();
long start2 = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    strArrayList.add("Test"+i);
}
long end2 = System.currentTimeMillis();
System.out.println("ArrayList Time in millis: " + (end2-start2));

总结一下：你看到的耗时差异，本质是两种数据结构在尾部插入场景下的固有特性导致的，ArrayList的数组结构在这种场景下就是比LinkedList的链表结构更高效～

内容的提问来源于stack exchange，提问作者Nitin Vnk