Invertir una lista en Java: en el lugar y fuera del lugar

En este breve tutorial, aprenderá cómo invertir una lista en el lugar y fuera del lugar en Java.

Inversión en el lugar y fuera del lugar

Al realizar operaciones en listas, es posible que desee considerar si las operaciones se realizan en el lugar (los cambios se implementan en el objeto original) o si están fuera de lugar (los cambios se implementan en una copia y el objeto original). el objeto no cambia).

Algunos idiomas y bibliotecas prefieren diferentes comportamientos predeterminados. En Java, la mayoría de las operaciones en listas inversas serán en su lugar.

Si este es su comportamiento deseado, ¡genial! De lo contrario, querrá crear una copia de la lista antes de invertir la copia:

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

Nota: El clone() Método no crear una copia profunda. Creando una lista usando new ArrayList(list) no crear una copia profunda. Se desaconseja la creación de copias profundas y es sorprendentemente difícil hacerlo de forma genérica (y no tiene sentido en algunos casos, según los tipos de datos de la lista). Esto no impedirá que puedas revertir list y no tener los elementos de listCopy aunque al revés.

Colecciones.reverse ()

El Collections.reverse() El método es el método estándar para revertir una colección y actúa como el método "faltante". List.reverse() método. Invierte la lista en el lugar:

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

Listas de guayaba.reverse(lista)

Si ya usa Google Guava en su proyecto, también puede aprovechar la Lists clase, que ofrece la reverse() método, que no ordena la lista original en el lugar, sino que crea una copia y la invierte:

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

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

Si aún no lo tiene, puede agregar Google Guava a su proyecto usando Maven, al incluir su dependencia en su pom.xml archivo:

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

O a través de Gradle:

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

Nota: Si aún no tiene Google Guava, o no tiene la intención de usarlo para otras partes de su proyecto, no lo importe solo para esta operación y apéguese a la Collections.reverse() método. Guava es una gran dependencia, y es una gran exageración usarla solo para esta operación.

List.add() y List.remove()

Si desea realizar operaciones adicionales además de simplemente invertir la lista, puede iterar a través de la lista original, eliminar los elementos del final, pasarlos a través de un método arbitrario y agregarlos nuevamente al comienzo de la lista:

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

Entonces, ¿cuál es el más rápido? Esto también depende de si desea realizar la operación en el lugar o fuera del lugar.

Punto de referencia de reversión en el lugar

Comparemos ambos enfoques en los tres métodos, comenzando con fuera de lugar:

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

Esto resulta en:

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

¿Qué sucede cuando aumentamos el número de elementos de 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, ...

¡La guayaba conserva la marca de 4ms! El enfoque manual tiene la peor complejidad de tiempo y aumentó linealmente. Collections.reverse() sufren menos con la ampliación, pero la implementación de Guava es la que menos sufre. Sin embargo, tenga en cuenta que no copiamos manualmente la lista para el enfoque Guayaba. ¿Cambiará el punto de referencia cuando abandonemos la idea de tener una lista "original" e "invertida"?

Punto de referencia de inversión fuera de lugar

Con 1000 elementos, y cada uno operando en una copia no invertida de la lista (que fue excluida de las medidas de tiempo), cuando eliminamos la copia manual de cada método y volvemos a ejecutar el código:

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

Guayaba aun se las arregla para superar consistentemente a ambos Collections.reverse() y el enfoque manual.

Conclusión

En esta breve guía, aprendió cómo invertir una lista en Java, en el lugar y fuera del lugar, preservando la lista original de la operación. hemos usado el Collections.reverse() método, Google Guayaba Lists.reverse() método y un enfoque manual.