Inversione di un elenco in Java: sul posto e fuori luogo

In questo breve tutorial imparerai come invertire un elenco sul posto e fuori posto in Java.

Inversione sul posto e fuori posto

Quando si eseguono operazioni sugli elenchi, è possibile considerare se le operazioni vengono eseguite sul posto (le modifiche vengono apportate sull'oggetto originale) o se sono fuori posto (le modifiche vengono eseguite su una copia e l'originale oggetto è invariato).

Alcuni linguaggi e librerie preferiscono comportamenti predefiniti diversi. In Java, la maggior parte delle operazioni sull'inversione degli elenchi lo saranno a posto.

Se questo è il tuo comportamento desiderato, fantastico! In caso contrario, ti consigliamo di creare una copia dell'elenco prima di annullare la copia:

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

Nota: I clone() metodo non crea una copia profonda. Creazione di un elenco utilizzando new ArrayList(list) non crea una copia profonda. La creazione di copie profonde è sconsigliata e sorprendentemente difficile da eseguire in modo generico (e non ha senso in alcuni casi, a seconda dei tipi di dati nell'elenco). Questo non ti impedirà di essere in grado di invertire list ed non avere gli elementi di listCopy essendo invertito, però.

Collezioni.reverse()

I Collections.reverse() metodo è il metodo standard per annullare una raccolta e funge da "mancante" List.reverse() metodo. Inverte l'elenco sul posto:

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

Liste di Guava.reverse(list)

Se stai già utilizzando Google Guava nel tuo progetto, puoi anche sfruttare il Lists classe, che offre il reverse() metodo, che non ordina l'elenco originale sul posto, ma crea una copia e inverte la copia:

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

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

Se non lo hai già, puoi aggiungere Google Guava al tuo progetto utilizzando Maven, includendo la sua dipendenza nel tuo pom.xml file:

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

Oppure tramite Gradle:

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

Nota: Se non hai già Google Guava, o non intendi utilizzarlo per altre parti del tuo progetto, non importarlo solo per questa operazione e attieniti al Collections.reverse() metodo. Guava è una grande dipendenza ed è un grave eccesso usarla solo per questa operazione.

List.add() e List.remove()

Se desideri eseguire operazioni aggiuntive oltre a invertire l'elenco, puoi scorrere l'elenco originale, rimuovere gli elementi dalla fine, passarli attraverso un metodo arbitrario e aggiungerli all'inizio dell'elenco:

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

Segno di riferimento

Allora, qual è il più veloce? Ciò dipende anche dal fatto che si desideri eseguire l'operazione sul posto o fuori posto.

Benchmark di inversione sul posto

Esaminiamo entrambi gli approcci su tutti e tre i metodi, iniziando con fuori luogo:

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

Questo risulta in:

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

Cosa succede quando aumentiamo il numero di elementi da 100 a 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 mantiene il segno di 4ms! L'approccio manuale ha la peggiore complessità temporale ed è aumentato in modo lineare. Collections.reverse() risente meno dell'aumento progressivo, ma l'implementazione di Guava ne soffre di meno. Tuttavia, tieni presente che non copiamo manualmente l'elenco per l'approccio Guava. Il benchmark cambierà quando abbandoneremo l'idea di avere un elenco "originale" e "invertito"?

Benchmark di inversione fuori posto

Con 1000 elementi, e ciascuno operante su una copia non invertita dell'elenco (che era esclusa dalle misurazioni del tempo), quando rimuoviamo la copia manuale da ogni metodo ed eseguiamo nuovamente il codice:

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

Guaiava ancora riesce a sovraperformare costantemente entrambi Collections.reverse() e l'approccio manuale.

Conclusione

In questa breve guida, hai imparato come invertire un elenco in Java, sul posto e fuori posto, preservando l'elenco originale dall'operazione. Abbiamo usato il Collections.reverse() metodo, Google Guava Lists.reverse() metodo e un approccio manuale.