Ist die Methode remove von Java's ArrayList Iterator O (n^2) oder O (n)? wenn ich über die Liste iteriere?

Question

Ich überarbeite eine ArrayList mit einer while-Schleife und entferne Werte, wenn sie bestimmte Kriterien erfüllen. Mein Code ist im Geist des folgenden Ausschnitts:

List<Integer> list = new ArrayList<>(); 
    int N = 1000 
    // setup list to show as an example 
    for (int i = 0; i < N; i++) { 
     list.add(i); 
    } 

    Date start = new Date(); 
    // iterate over entire list, removing half the values 
    Iterator<Integer> iter = list.iterator(); 
    while (iter.hasNext()) { 
     Integer in = iter.next(); 
     if (in % 2 == 0) { 
      // is it even? 
      iter.remove(); 
     } 
    } 

    Date end = new Date(); 
    System.out.println(end.getTime() - start.getTime()); 
    System.out.println(list.size()); 

Was will ich weiß, ist, wenn die Zeit Komplexität dieser Iterator Schleife ist O (N) oder O (N^2). Ich glaube, dass es O (N^2) ist, weil Java ArrayLists in einem regulären Array gesichert werden, und für jede Entfernung müssen Sie unbedingt O (N) der nachfolgenden Werte nach links verschieben, um das Array in einem vernünftigen Zustand zu halten.

Answer 1

Keine der Antworten auf meine Frage liefern Beweise, wie Iterator.remove funktioniert, also habe ich meine eigenen Tests gemacht. Meine persönlichen Tests lassen mich glauben, dass die Zeitkomplexität O (N^2) ist. Hier ist es, Daten aus 3 verschiedenen Tests, wobei jeder "Time" Wert ist ein Durchschnittswert über 10 Iterationen:

N = 10.000 Time = 8ms

N = 100.000 Zeit = 487ms

N = 200.000 Zeit = 2026ms

eine Verdoppelung der Listengröße ergibt eine ungefähr 4 mal längere Laufzeit.