Umkehren einer Liste in Java – In-Place und Out-Of-Place

In diesem kurzen Tutorial erfahren Sie, wie Sie eine Liste in-place und out-of-place in Java umkehren.

In-Place und Out-Of-Place umkehren

Wenn Sie Operationen an Listen durchführen, sollten Sie überlegen, ob die Operationen an Ort und Stelle durchgeführt werden (Änderungen werden am ursprünglichen Objekt vorgenommen) oder ob sie nicht am Platz sind (Änderungen werden an einer Kopie und am Original vorgenommen). Objekt bleibt unverändert).

Einige Sprachen und Bibliotheken bevorzugen andere Standardverhalten. In Java werden die meisten Operationen zum Umkehren von Listen sein an Ort und Stelle.

Wenn dies Ihr gewünschtes Verhalten ist – großartig! Wenn nicht, sollten Sie eine Kopie der Liste erstellen, bevor Sie die Kopie rückgängig machen:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Hinweis: Das clone() Methode nicht Erstellen Sie eine tiefe Kopie. Erstellen einer Liste mit new ArrayList(list) nicht Erstellen Sie eine tiefe Kopie. Es wird davon abgeraten, tiefe Kopien zu erstellen, und es ist auf generische Weise überraschend schwierig (und macht in einigen Fällen keinen Sinn, abhängig von den Datentypen in der Liste). Das hindert Sie nicht daran, umzukehren list und nicht haben die Elemente von listCopy allerdings umgekehrt.

Sammlungen.reverse()

Das Collections.reverse() -Methode ist die Standardmethode zum Umkehren einer Sammlung und fungiert als „fehlende“ List.reverse() Methode. Es kehrt die Liste an Ort und Stelle um:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Collections.reverse(list);

System.out.println(list);     
System.out.println(listCopy); 

Guavas Listen.reverse(list)

Wenn Sie Google Guava bereits in Ihrem Projekt verwenden, können Sie auch die nutzen Lists Klasse, die die bietet reverse() -Methode, die die ursprüngliche Liste nicht direkt sortiert, sondern eine Kopie erstellt und die Kopie umkehrt:

List list = new ArrayList(Arrays.asList(1, 2, 3));
List reversedList = Lists.reverse(list);

System.out.println(list);         
System.out.println(reversedList); 

Wenn Sie es noch nicht haben, können Sie Google Guava mit Maven zu Ihrem Projekt hinzufügen, indem Sie seine Abhängigkeit in Ihre pom.xml Datei:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>

Oder über Gradle:

implementation group: 'com.google.guava', name: 'guava'

Hinweis: Wenn Sie Google Guava noch nicht haben oder nicht beabsichtigen, es für andere Teile Ihres Projekts zu verwenden – importieren Sie es nicht nur für diesen Vorgang und bleiben Sie bei der Collections.reverse() Methode. Guave ist eine große Abhängigkeit, und es ist ein großer Overkill, es nur für diese Operation zu verwenden.

List.add() und List.remove()

Wenn Sie neben dem Umkehren der Liste weitere Operationen ausführen möchten, können Sie die ursprüngliche Liste durchlaufen, die Elemente am Ende entfernen, sie durch eine beliebige Methode führen und sie wieder am Anfang der Liste hinzufügen:

public static int process(int input) {
    return input;
}

List list = new ArrayList(Arrays.asList(1, 2, 3));

for (int i = 0, j = list.size()-1; i <= j; i++) {
    int lastValue = process(list.remove(j));
    list.add(i, lastValue);
}

System.out.println(list);  

Benchmark

Also, was ist am schnellsten? Dies hängt auch davon ab, ob Sie die Operation in-place oder out-of-place durchführen möchten.

In-Place-Reversal-Benchmark

Lassen Sie uns beide Ansätze mit allen drei Methoden vergleichen, beginnend mit out-of-place:

List list = new Random().ints(100, 1, 11)
                .boxed()
                .collect(Collectors.toList());

int runs = 1000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListCollections(list);
}
long end1 = System.currentTimeMillis();
System.out.println(String.format("Collections.reverse() took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListGuava(list);
}
long end2 = System.currentTimeMillis();
System.out.println(String.format("Guava's Lists.reverse() took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListManually(list);
}
long end3 = System.currentTimeMillis();
System.out.println(String.format("Manually took: %s miliseconds", end3-start3));

System.out.println("Original list: " + list);

Das führt zu:

Collections.reverse() took: 3 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 13 miliseconds
Original list: [6, 7, 9, 7, 2, 5, 4, 1, 3, 2, 2, 6, ...

Was passiert, wenn wir die Anzahl der Elemente von 100 auf 1000 erhöhen?

Collections.reverse() took: 9 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 133 miliseconds
Original list: [10, 2, 2, 6, 2, 4, 7, 3, 9, 2, 7, 5, ...

Guava behält die 4ms-Marke! Der manuelle Ansatz hat die höchste Zeitkomplexität und stieg linear an. Collections.reverse() leiden weniger unter der Skalierung, aber die Implementierung von Guave leidet am wenigsten. Beachten Sie jedoch, dass wir die Liste für den Guava-Ansatz nicht manuell kopieren. Wird sich der Benchmark ändern, wenn wir die Idee einer „ursprünglichen“ und einer „umgekehrten“ Liste aufgeben?

Out-of-Place-Umkehr-Benchmark

Mit 1000 Elementen, die jeweils auf einer nicht umgekehrten Kopie der Liste arbeiten (die von den Zeitmessungen ausgeschlossen wurde), wenn wir die manuelle Kopie von jeder Methode entfernen und den Code erneut ausführen:

Collections.reverse() took: 7 miliseconds
Guava's Lists.reverse() took: 3 miliseconds
Manually took: 131 miliseconds
Original list: [6, 8, 10, 7, 3, 8, 7, 1, 1, 9, 5, ...

Guava Noch schafft es, beide konstant zu übertreffen Collections.reverse() und der manuelle Ansatz.

Zusammenfassung

In dieser kurzen Anleitung haben Sie gelernt, wie Sie eine Liste in Java an Ort und Stelle umkehren und dabei die ursprüngliche Liste der Operation beibehalten. Wir haben die benutzt Collections.reverse() Methode, Google Guave Lists.reverse() Methode und manueller Ansatz.