Wir haben eine Liste von Elementen und haben eine sehr einfache Kollisionserkennung, bei der wir jedes Objekt gegen jedes andere Objekt prüfen.
Die Überprüfung ist kommutativ. Um dies zu vermeiden, würden wir dies in C ++ tun:
%Vor%Das Schlüsselbit hier ist die Kopie
%Vor%Wie würdest du das in Java schreiben?
Sie können Java-Iteratoren nicht kopieren, also müssen Sie es ohne sie machen:
%Vor%Sie können dies mit ListIterator tun:
%Vor% Bei einer verketteten Liste (die langsamen Indexzugriff hat) muss list.listIterator(index) jedoch immer noch an die richtige Stelle iterieren.
Aber so ist es nur O (n²) (und Sie können nicht besser werden) als O (n³) wie der Index-Zugang in den anderen Antworten. (Sie könnten sogar noch schneller sein, wenn Sie Ihre Liste zuerst in ein Array kopieren, aber das ist hier nur ein konstanter Faktor.)
Wenn Sie normalerweise indexbasierten Zugriff benötigen (oder dieses Iterator-Klonen), sollten Sie natürlich eine Array-basierte Liste verwenden (oder eine benutzerdefinierte Liste, deren Iterator das Klonen unterstützt).
Für eine verkettete Liste (die einen langsamen Indexzugriff hat) denke ich, dass es einen Weg gibt, dies zu tun, ohne in der O (n²) Verlangsamung zu geraten, die Paŭlo erwähnte. Solange Sie sich nicht um die Reihenfolge kümmern, in der die Liste aufgerufen wird, können Sie die äußere Schleife vom letzten Element aus starten und zurück iterieren und die innere Schleife vom ersten Element aus starten und iterieren, bis sich die beiden Iteratoren treffen. Siehe iterRevIterator im folgenden Code. Der Aufruf von list.listIterator(list.size()) ist schnell, weil list ein LinkedList ist, d. H. Eine doppelt verknüpfte Liste, und der Zugriff auf das letzte Element erfordert kein Durchlaufen der Liste.
Der Unterschied ist nicht enorm ...
aber immer noch wichtig.
%Vor%