Java中ArrayList与LinkedList删除第n个元素性能异常问题排查

哈哈，这个性能反转的坑我之前也踩过，完全懂你的困惑！你猜的没错，问题核心就在get()方法上——LinkedList的常数时间remove()是有前提的，不是随便用都快。

为什么你的测试结果反了？ #

• LinkedList的get(index)是O(n)复杂度：LinkedList是双向链表结构，没有数组那样的随机访问能力。每次调用get(index)，都要从头节点（或尾节点）开始遍历到目标位置，遍历次数和索引值正相关。如果你的deleteEachNth方法里是先通过get()定位元素再删除，那整个操作的时间复杂度会变成O(n²)——遍历找元素的开销远远盖过了删除本身的O(1)优势。
• ArrayList的remove(index)没你想的那么慢：虽然ArrayList删除元素时需要移动后面的所有元素（理论O(n)），但JVM对数组复制做了极致优化（用System.arraycopy这个native方法，速度极快）。当元素数量在10000这个级别时，数组复制的实际耗时反而比LinkedList反复遍历找节点的开销小，所以整体速度反超。

正确的LinkedList用法：用迭代器操作 #

LinkedList的优势要在迭代过程中删除才能体现，因为迭代器会持有当前节点的引用，删除时直接操作节点指针，不需要再遍历定位。给你写个正确的实现：

public static void deleteEachNth(LinkedList<Integer> list, int n) {
    Iterator<Integer> iterator = list.iterator();
    int count = 0;
    while (iterator.hasNext()) {
        iterator.next();
        count++;
        // 每第n个元素就删除
        if (count % n == 0) {
            iterator.remove();
        }
    }
}

这个版本的时间复杂度是O(n)，和ArrayList的最优实现性能接近，甚至在元素量更大的时候会超过ArrayList。

反面教材：错误的LinkedList写法 #

如果你的代码是类似下面这样，用索引去定位删除，那性能差就完全合理了：

// 性能极差的错误写法
public static void deleteEachNthBad(LinkedList<Integer> list, int n) {
    int count = 0;
    int i = 0;
    while (i < list.size()) {
        count++;
        if (count % n == 0) {
            // remove(index)内部会调用get(index)遍历找节点
            list.remove(i);
        } else {
            i++;
        }
    }
}

总结 #

• LinkedList适合迭代增删、头尾操作，不适合随机访问；
• ArrayList适合随机访问、批量操作，迭代中频繁删除的话性能不如LinkedList（但小数据量下优化后的数组复制可能更快）；
• 性能测试一定要结合实际使用场景，不能只看理论复杂度！

内容的提问来源于stack exchange，提问作者sæe