Reversering af en liste i Java – På plads og ikke på plads

I denne korte vejledning lærer du, hvordan du vender en liste på plads og ikke på plads i Java.

Vende på plads og ude af sted

Når du udfører handlinger på lister – vil du måske overveje, om handlingerne udføres på stedet (ændringer udføres på det originale objekt), eller om de er malplacerede (ændringer udføres på en kopi, og originalen objektet er uændret).

Nogle sprog og biblioteker foretrækker anderledes standardadfærd. I Java vil de fleste operationer på vendelister være på plads.

Hvis dette er din ønskede adfærd - fantastisk! Hvis ikke, vil du gerne oprette en kopi af listen, før du vender kopien om:

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

Bemærk: clone() metode ikke lave en dyb kopi. Oprettelse af en liste vha new ArrayList(list) ikke lave en dyb kopi. Oprettelse af dybe kopier frarådes, og overraskende vanskeligt at gøre på en generisk måde (og giver ikke mening i nogle tilfælde, afhængigt af datatype(r) på listen). Dette forhindrer dig ikke i at kunne vende tilbage list , ikke har elementer af listCopy bliver dog omvendt.

Collections.reverse()

Collections.reverse() metode er standardmetoden til at vende en samling og fungerer som den "manglende" List.reverse() metode. Det vender listen på plads:

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 lister.reverse(liste)

Hvis du allerede bruger Google Guava i dit projekt, kan du også udnytte Lists klasse, som tilbyder reverse() metode, som ikke sorterer den originale liste på plads, men opretter en kopi og vender kopien om:

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

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

Hvis du ikke allerede har det, kan du tilføje Google Guava til dit projekt ved hjælp af Maven ved at inkludere dets afhængighed i din pom.xml fil:

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

Eller via Gradle:

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

Bemærk: Hvis du ikke allerede har Google Guava eller ikke har til hensigt at bruge det til andre dele af dit projekt – så lad være med at importere det kun til denne handling, og hold dig til Collections.reverse() metode. Guava er en stor afhængighed, og det er en stor overkill kun at bruge det til denne operation.

List.add() og List.remove()

Hvis du ønsker at udføre yderligere handlinger udover blot at vende listen om – du kan iterere gennem den originale liste, fjerne elementerne fra slutningen, sende dem gennem en vilkårlig metode og tilføje dem tilbage i starten af ​​listen:

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

Så hvad er den hurtigste? Dette afhænger også af, om du vil udføre operationen på stedet eller ude af stedet.

In-Place Reversal Benchmark

Lad os benchmarke begge tilgange på alle tre metoder, begyndende med malplaceret:

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);

Dette resulterer i:

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, ...

Hvad sker der, når vi øger antallet af elementer fra 100 til 1000?

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 beholder 4ms-mærket! Den manuelle tilgang har den værste tidskompleksitet, og den steg lineært. Collections.reverse() lider mindre af opskalering, men Guavas implementering lider mindst. Husk dog, at vi ikke manuelt kopierer listen for Guava-tilgangen. Vil benchmark ændre sig, når vi dropper tanken om at have en "original" og "omvendt" liste?

Out-of-Place Reversal Benchmark

Med 1000 elementer, og hver opererer på en ikke-omvendt kopi af listen (som var udelukket fra tidsmålingerne), når vi fjerner den manuelle kopi fra hver metode og kører koden igen:

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 stadig formår konsekvent at overgå begge Collections.reverse() og den manuelle tilgang.

Konklusion

I denne korte vejledning har du lært, hvordan du vender en liste i Java, på plads og ikke på plads, og bevarer den originale liste fra operationen. Vi har brugt Collections.reverse() metode, Google Guava's Lists.reverse() metode og en manuel tilgang.