为何迭代器删除LinkedList元素比for循环快数百倍？

你测试用的LinkedList包含0到100000的整数，删除远端元素时迭代器速度是for循环的500倍，核心原因完全在于两者底层实现的效率差异，你的猜测（和remove有关）没错，但更准确地说，是get(i)和remove(i)组合起来的低效导致的：

测试代码 #

public static void iteratorRemove() {
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        int item = iterator.next();
        if (item == 99999) {
            iterator.remove();
        }
    }
}

public static void linkedListRemove() {
    for(int i=0; i<list.size(); i++) {
        if(list.get(i)==99997) {
            list.remove(i);
        }
    }
}

为什么for循环这么慢？ #

LinkedList是双向链表结构，没有数组那样的随机访问能力：

• 每次调用list.get(i)，都得从链表头（或尾，取更近的一端）开始逐个遍历到第i个节点。你要找的99997接近链表末尾，每次get(i)都要遍历近10万个节点，循环10万次的话，总时间复杂度是O(n²)，这是慢的核心原因。
• 调用list.remove(i)时，同样要先遍历找到第i个节点（又是一次O(n)操作），再修改前后节点的引用完成删除。等于找一次、删一次，双重耗时。

迭代器快在哪？ #

LinkedList的迭代器是专门实现的ListItr，天生适配链表结构：

• 迭代器内部维护了当前节点的引用，每次next()只需要移动到下一个节点，耗时O(1)，不需要从头遍历。
• iterator.remove()直接用当前持有的节点引用修改前后节点的链接，不需要再查找节点，也是O(1)操作。
• 整个过程只需要遍历链表一次，总时间复杂度是O(n)，和for循环的O(n²)比，效率差距自然拉到几百倍。

额外提醒 #

你的linkedListRemove()还有个bug：删除元素后链表长度减少，但循环的i仍在递增，会跳过被删元素的下一个节点。不过这和速度慢的核心问题无关。

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