ArrayList 与 LinkedList 的插删成本怎样算？

直接回答

要把“找到位置”和“修改结构”分开。ArrayList 找下标快，但中间插删要移动后续引用；LinkedList 改链接便宜，但用索引寻找中间节点通常要走链。只有已经通过迭代器定位等条件成立时，链表局部插删的优势才不会被定位成本掩盖。

讲清原理

linked.add(i, x) 不是从任意位置瞬间插入，它先找到索引对应的节点，最坏 O(n)。array.add(i, x) 可以直接知道槽位，却仍可能移动 O(n) 个引用，容量不够时还要增长。

如果顺序扫描时用 ListIterator 连续定位并在当前位置修改，LinkedList 可以复用游标；若每次重新随机索引，情况不同。两者普通 get 循环的成本也不同，不能只看代码外层循环有一层就判定 O(n)。

例子与易错点

Java 21 的 main 片段：

var values = new java.util.LinkedList<>(java.util.List.of("A", "C"));
var it = values.listIterator();
it.next();
it.add("B");
System.out.println(values);

输出 [A, B, C]。这里修改用的是已经定位的游标。它没有证明任意数据量下 LinkedList 都更快；节点分配、缓存行为和真实操作分布仍会影响结果。

相关题：第 10 题、第 23 题、第 35 题、第 38 题。