Omvända en lista i Java – På plats och på plats

I den här korta handledningen får du lära dig hur du vänder på en lista på plats och inte på plats i Java.

Backa på plats och på plats

När du utför operationer på listor – du kanske vill överväga om operationerna görs på plats (ändringar antas på det ursprungliga objektet), eller om de är malplacerade (ändringar antas på en kopia och originalet objektet är oförändrat).

Vissa språk och bibliotek föredrar olika standardbeteenden. I Java kommer de flesta operationer på reverseringslistor att vara på plats.

Om detta är ditt önskade beteende – bra! Om inte, vill du skapa en kopia av listan innan du vänder kopian:

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

Notera: Smakämnen clone() metod inte skapa en djup kopia. Skapa en lista med hjälp av new ArrayList(list) inte skapa en djup kopia. Att skapa djupa kopior är avskräckt och förvånansvärt svårt att göra på ett allmänt sätt (och är inte vettigt i vissa fall, beroende på datatyp(er) i listan). Detta hindrar dig inte från att kunna backa list och inte har inslag av listCopy är dock omvänd.

Collections.reverse()

Smakämnen Collections.reverse() metod är standardmetoden för att vända en samling och fungerar som den "saknade" List.reverse() metod. Det vänder på listan på plats:

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 Lists.reverse(list)

Om du redan använder Google Guava i ditt projekt kan du också utnyttja Lists klass, som erbjuder reverse() metod, som inte sorterar den ursprungliga listan på plats, utan skapar en kopia och vänder kopian:

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

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

Om du inte redan har det kan du lägga till Google Guava till ditt projekt med Maven, genom att inkludera dess beroende 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'

Notera: Om du inte redan har Google Guava, eller inte tänker använda det för andra delar av ditt projekt – importera det inte bara för den här operationen, och håll dig till Collections.reverse() metod. Guava är ett stort beroende, och det är en stor överdrift att bara använda den för denna operation.

List.add() och List.remove()

Om du vill utföra ytterligare operationer förutom att bara vända listan – kan du iterera genom den ursprungliga listan, ta bort elementen från slutet, skicka dem genom en godtycklig metod och lägga till dem i början av listan:

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

riktmärke

Så vilken är snabbast? Detta beror också på om du vill utföra operationen på plats eller på annan plats.

In-Place Reversal Benchmark

Låt oss jämföra båda tillvägagångssätten för alla tre metoderna, med början på 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);

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

Vad händer när vi ökar antalet element från 100 till 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 behåller 4ms-märket! Den manuella metoden har den värsta tidskomplexiteten och den steg linjärt. Collections.reverse() lider mindre av uppskalning, men Guavas implementering lider minst. Kom dock ihåg att vi inte manuellt kopierar listan för Guava-metoden. Kommer riktmärket att förändras när vi förkastar tanken på att ha en "original" och "omvänd" lista?

Reverseringsriktmärke för out-of-place

Med 1000 element, och var och en som arbetar på en icke-omvänd kopia av listan (som exkluderades från tidsmätningarna), när vi tar bort den manuella kopian från varje metod och kör 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 fortfarande lyckas konsekvent överträffa båda Collections.reverse() och det manuella tillvägagångssättet.

Slutsats

I den här korta guiden har du lärt dig hur du vänder på en lista i Java, på plats och på plats, och bevarar den ursprungliga listan från operationen. Vi har använt Collections.reverse() metod, Google Guava's Lists.reverse() metod och ett manuellt tillvägagångssätt.