对 Java ArrayList 使用迭代器而不是 c 风格的循环

Question

当遍历链表时，get(i) 是一个 O(N) 操作。那么我们使用 Iterator 对象来遍历列表是有道理的。但是对于 ArrayList，get(i) 是 O(1)。所以，在那种情况下，我说当使用 ArrayList 时，我们使用 c 风格的循环还是 Iterator 对象没有区别是正确的吗？

Answer 1

是的，ArrayList 在这两种情况下都是 O(n)。如果您使用迭代器查找元素，在最坏的情况下您将不得不检查每个元素。在一般情况下，您必须检查一半。因此它仍然是 O(n)。

此外，用于遍历列表的 for 语法只是用于调用迭代器的语法糖。如果查看编译后的字节码，您会发现它调用了列表的迭代器。

例如下面的代码：

import java.util.*;

public class IterTest {

    public static void main() {
        List<String> l = new ArrayList<>();

        for(String s : l) {
            System.out.println(s);
        }
    }
}

具有以下字节码：

Compiled from "IterTest.java"
public class IterTest {
  public IterTest();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main();
    Code:
       0: new           #2                  // class java/util/ArrayList
       3: dup
       4: invokespecial #3                  // Method java/util/ArrayList."<init>":()V
       7: astore_0
       8: aload_0
       9: invokeinterface #4,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
      14: astore_1
      15: aload_1
      16: invokeinterface #5,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
      21: ifeq          44
      24: aload_1
      25: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
      30: checkcast     #7                  // class java/lang/String
      33: astore_2
      34: getstatic     #8                  // Field java/lang/System.out:Ljava/io/PrintStream;
      37: aload_2
      38: invokevirtual #9                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      41: goto          15
      44: return

您可以看到它正在使用迭代器遍历列表。

更新

回复您的评论：

带索引的 for 循环将具有与显式迭代器和 for 迭代器样式循环相同的性能（如果您使用的是 ArrayList。

但是，使用带有 LinkedList 的索引的 for 将比 ArrayList 严格（平均）差，因为对于每个索引，您正在执行 O(n) 查找。因此，你的总表现实际上最终是 O(n²)。

Answer 2

与 while 循环相比，在删除元素时使用 Iterator 更不容易出错，因为您在删除时不必调整某些位置值（i、光标，无论您怎么称呼它） .正如@Vivin Paliath 所解释的那样，for 循环已经在使用迭代器，并且不适用于删除（删除将导致 ConcurrentModificationExceptions）。

Answer 3

你是对的。你应该避免这样的循环

for (int i = 0; i < linkedList.size(); i++) {
    ... linkedList.get(i) ...
}

对于一个LinkedList因为get(i)是O(n)所以整个过程变成了O(n^2).

对于 ArrayList 没关系，因为 iterator.next() 和 get(i) 都是 O(1)。

但是，即使对于 LinkedList，您通常也不需要显式使用 Iterator 对象，因为 foreach 循环 for (Object object : linkedList) 无论如何都会在后台使用 Iterator .

Iterator只需要在相对罕见的情况下显式使用（例如过滤一个List或并行遍历两个LinkedList）。

对 Java ArrayList 使用迭代器而不是 c 风格的循环

Using an Iterator for a Java ArrayList rather than c-style loop

java

arraylist

time-complexity

data-structures