Reversere en liste i Java – på plass og ut på plass

I denne korte opplæringen lærer du hvordan du snur en liste på plass og ikke på plass i Java.

Reversering på plass og ute av plass

Når du utfører operasjoner på lister – kan det være lurt å vurdere om operasjonene gjøres på plass (endringer er vedtatt på det opprinnelige objektet), eller om de er malplasserte (endringer er vedtatt på en kopi, og originalen objektet er uendret).

Noen språk og biblioteker foretrekker annen standardatferd. I Java vil de fleste operasjoner på reverseringslister være det på plass.

Hvis dette er ønsket oppførsel – flott! Hvis ikke, bør du lage en kopi av listen før du reverserer kopien:

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

OBS: De clone() metode ikke lage en dyp kopi. Opprette en liste ved hjelp av new ArrayList(list) ikke lage en dyp kopi. Å lage dype kopier frarådes, og overraskende vanskelig å gjøre på en generisk måte (og gir ikke mening i noen tilfeller, avhengig av datatypen(e) i listen). Dette stopper deg ikke fra å kunne reversere list og ikke har elementer av listCopy blir imidlertid reversert.

Collections.reverse()

De Collections.reverse() metoden er standardmetoden for å reversere en samling, og fungerer som den "manglende" List.reverse() metode. Det snur listen på plass:

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

Guava's Lists.reverse(list)

Hvis du allerede bruker Google Guava i prosjektet ditt, kan du også dra nytte av Lists klasse, som tilbyr reverse() metode, som ikke sorterer den opprinnelige listen på plass, men lager en kopi og reverserer kopien:

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 legge til Google Guava i prosjektet ditt ved å bruke Maven, ved å inkludere dens avhengighet i pom.xml file:

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

Eller via Gradle:

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

OBS: Hvis du ikke allerede har Google Guava, eller ikke har tenkt å bruke den til andre deler av prosjektet – ikke importer den bare for denne operasjonen, og hold deg til Collections.reverse() metode. Guava er en stor avhengighet, og det er en stor overkill å bruke den kun til denne operasjonen.

List.add() og List.remove()

Hvis du ønsker å utføre flere operasjoner i tillegg til å bare reversere listen – kan du iterere gjennom den opprinnelige listen, fjerne elementene fra slutten, sende dem gjennom en vilkårlig metode og legge dem til på begynnelsen av 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å, hvilken er den raskeste? Dette avhenger også av om du ønsker å utføre operasjonen på stedet eller ikke.

In-Place Reversal Benchmark

La oss måle begge tilnærmingene på alle tre metodene, og starter med malplassert:

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

Hva skjer når vi øker antall 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-merket! Den manuelle tilnærmingen har den verste tidskompleksiteten, og den steg lineært. Collections.reverse() lider mindre av oppskalering, men Guavas implementering lider minst. Husk imidlertid at vi ikke manuelt kopierer listen for Guava-tilnærmingen. Vil referansen endres når vi dropper ideen om å ha en "original" og "omvendt" liste?

Reverseringsbenchmark som ikke er på plass

Med 1000 elementer, og hver opererer på en ikke-omvendt kopi av listen (som ble ekskludert fra tidsmålingene), når vi fjerner den manuelle kopien fra hver metode og kjører koden på nytt:

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 fortsatt klarer å overgå begge deler Collections.reverse() og den manuelle tilnærmingen.

konklusjonen

I denne korte veiledningen har du lært hvordan du reverserer en liste i Java, på plass og ikke på plass, og bevarer den opprinnelige listen fra operasjonen. Vi har brukt Collections.reverse() metode, Google Guava Lists.reverse() metode og en manuell tilnærming.