遍历List删除匹配元素：for循环与Iterator.remove()性能对比

先看你给出的两种实现代码：

实现一：普通索引遍历 #

for (int i = 0; i < list.size(); i++) {
    if (shouldBeRemoved(list.get(i))) {
        E toRemove = list.get(i);
        list.remove(i);
        return toRemove;
    }
}
return null;

实现二：Iterator遍历 #

Iterator<E> iterator = list.iterator();
while (iterator.hasNext()) {
    E element = iterator.next();
    if (shouldBeRemoved(element)) {
        iterator.remove();
        return element;
    }
}
return null;

效率对比与不同List实现的表现 #

1. ArrayList（基于数组的实现）

• 普通索引遍历：get(i)是O(1)操作，但代码里对同一个索引调用了两次get(i)（判断一次、取值一次），多了一次无意义的数组访问；remove(i)需要把索引i后面的所有元素向前移动一位，开销是O(n)。
• Iterator遍历：next()直接拿到当前元素，只做一次取值；iterator.remove()内部调用ArrayList的索引删除方法，开销同样是O(n)，但少了一次get(i)的开销，效率略高于普通遍历，但差距极小，几乎可以忽略。

2. LinkedList（基于双向链表的实现）

• 普通索引遍历：get(i)是O(n)操作——LinkedList需要从头/尾节点遍历到第i个元素。如果匹配元素在第k位，循环会执行k次get(i)，总时间复杂度是O(k²)，当List较大且匹配位置靠后时，性能会急剧下降。
• Iterator遍历：LinkedList的Iterator是双向迭代器，next()仅需移动当前节点指针，是O(1)操作；找到匹配元素后，iterator.remove()直接修改当前节点的前后指针，也是O(1)操作，总时间复杂度是O(k)，效率远高于普通索引遍历。

适用场景总结 #

• 若确定使用ArrayList：两种方法都能用，Iterator略优，但普通遍历也不会有明显性能问题；不过Iterator是Java集合框架推荐的遍历删除方式，代码更规范。
• 若使用LinkedList：必须用Iterator，普通索引遍历的性能问题会非常严重，尤其是数据量较大时。
• 若不确定List的具体实现（比如方法参数是List接口）：优先用Iterator，它能在所有List实现上保证稳定的性能，避免踩LinkedList的性能坑。

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