Warum gibt das Aufrufen von remove() auf einem Iterator eine ConcurrentModificationException?

Question

ich versuche, eine sehr einfache Methode zu schreiben Duplikate in einer LinkedList zu entfernen:

ich versuche, dies zu tun, ohne zusätzliche Puffer, so dass ich halte zwei Iteratoren an der verknüpften Liste, macht man die normale Iteration, und eine andere Durchläuft alle vorherigen Knoten, um nach Duplikaten zu suchen (wie in CareerCup angegeben); aber der Compiler sagt mir, es ist ein CME obwohl ich itr1.remove nenne():

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    int count1 = 0; 
    int count2 = 0; 
    while (itr1.hasNext()) { 
     Object next = itr1.next(); 
     count1++; 
     count2 = 0; 
     ListIterator itr2 = l.listIterator(); 
     while (itr2.hasNext()) { 
      count2++; 
      if (count2 == count1) 
       break; 
      if (itr2.next() == next){ 
       itr1.remove(); 
      } 
     } 

    } 
} 

Eine andere einfachere Lösung dieses Problems mit Hilfe von Hashset leicht ist wie folgt und keine Ausnahme berichtet:

Ist es, weil, wenn ich durch itr2 iteriere ich kann nicht auf itr1 ändern? Gibt es eine Möglichkeit, das zu beheben? Danke Jungs.

Answer 1

Im ersten Fall ja - Sie ändern den Inhalt der Sammlung über Iterator2, während Iterator1 nicht über die Änderungen informiert ist. Im zweiten Fall erlaubt es HashSet/HashMap nicht, Elemente zu entfernen, während sie durchlaufen werden.

Sie können entfernte Elemente zu einer anderen Sammlung hinzufügen und sie nach einer Iteration entfernen. Z.B.

List toRemove = new ArrayList(); 
    for (Object next : collection) { 
     if (someCondition) toRemove.add(next); 
    } 
    collection.removeAll(toRemove); 

Ich hoffe, es hilft.

P.S. Weitere Details zum Entfernen von Elementen aus der Liste bezüglich der Komplexität des Algorithmus finden Sie hier. Removing ArrayList object issue

Answer 2

Sie erhalten CME, weil die Liste vom zweiten Iterator geändert wird und der erste Iterator diese Änderung nicht erkennt. Wenn es das nächste Mal versucht, auf die Liste zuzugreifen, ist es bereits modifiziert. Und daher wirft es die Ausnahme.

Verwenden Sie nur einen Iterator, um die Liste gleichzeitig zu ändern.

Answer 3

Ja. Sie können sich das so vorstellen: Wenn Sie einen Iterator erstellen, wird die aktuelle "Änderungsanzahl" der Liste angezeigt. Wenn ein Iterator ein Element aus der Liste entfernt, prüft es die Anzahl der Änderungen, um zu sehen, ob es das erwartet, und wenn alles in Ordnung ist, entfernt es das Element und aktualisiert die Änderungsanzahl sowohl im Iterator als auch in der Liste. Der andere Iterator hat immer noch die alte Änderungszahl und sieht den neuen Wert und wirft den CME.

Der hashset-basierte Weg ist in den meisten Fällen die richtige Lösung. Es wird viel besser funktionieren - zwei O (n) Durchgänge sind normalerweise besser als O (n^2), wie die geschachtelte Iterationslösung erzeugen würde (wenn es funktioniert).

Answer 4

Von the API docs:

Die die zurück Iteratoren von dieser Klasse iterator und listIterator Methoden sind ausfall schnell: wenn die Liste strukturell jeder Zeit geändert, nachdem der Iterator erstellt wird, in irgendeiner Weise außer durch die Iterator eigenen remove oder add Methoden, wird der Iterator eine ConcurrentModificationException werfen.

Answer 5

Der Grund, warum Sie CME wurde von anderen erklärt bekommen, ist hier möglich, wie Sie toRemove dups

Verwenden einer Liste entfernen können Element beim ersten Mal iterator Stolpern hinein aufnehmen, danach, wenn sich treffen wieder mit dem aufgenommenen Element, entfernen Sie es mit iterator.remove()

Answer 6

Ja, Sie können dies beheben, ohne zusätzlichen Platz zu verwenden.

Das Problem kommt von der Ausführung dieser beiden Zeilen nacheinander.

• itr1.remove();
• itr2.hasNext();

Sie können zwei Iteratoren gleichzeitig über dieselbe Liste verwenden. Wenn Sie vorsichtig sind.
Sobald jedoch einer dieser Iteratoren die Liste geändert hat (wie es bei 10 der Fall ist), können Sie den anderen Iterator nicht mehr verwenden (Sie können also nicht itr2.hasNext() aufrufen).

Die Lösung ist eine break nach itr1.remove() zu setzen. Und zu aktualisieren count1:

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    int count1 = 0; 
    int count2 = 0; 
    while (itr1.hasNext()) { 
     Object next = itr1.next(); 
     count1++; 
     count2 = 0; 
     ListIterator itr2 = l.listIterator(); 
     while (itr2.hasNext()) { 
      count2++; 
      if (count2 == count1) 
       break; 
      if (itr2.next() == next){ 
       itr1.remove(); 
       --count1; 
       break; 
      } 
     } 
    } 
} 

Eine elegantere Lösung wäre mit Elementen nach dem aktuellen zu vergleichen, anstatt Elementen vor dem aktuellen:

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    while (itr1.hasNext()) { 
    Object next = itr1.next(); 
    ListIterator itr2 = l.listIterator(itr1.nextIndex()); 
    while (itr2.hasNext()) { 
     if (itr2.next() == next) { 
     itr1.remove(); 
     break; 
     } 
    } 
    } 
} 

Dies sind nicht die besten Lösungen in Bezug auf Rechenkomplexität. Wenn Speicherplatz kein Problem ist, ist die Hashset-Lösung hinsichtlich der Rechenkomplexität besser.

Die Frage bezieht sich jedoch auf gleichzeitige Mofikation durch Iteratoren und nicht auf Komplexitätsoptimierung.