Revertendo uma lista em Java – In-Place e Out-Of-Place

Neste breve tutorial, você aprenderá como reverter uma lista no local e fora do local em Java.

Inversão no local e fora do local

Ao executar operações em listas – você pode querer considerar se as operações são feitas no local (as alterações são executadas no objeto original) ou se estão fora do local (as alterações são executadas em uma cópia e o original objeto permanece inalterado).

Algumas linguagens e bibliotecas preferem comportamentos padrão diferentes. Em Java, a maioria das operações em listas de reversão serão no lugar.

Se este é o comportamento desejado – ótimo! Caso contrário, convém criar uma cópia da lista antes de reverter a cópia:

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

Observação: A clone() método não criar uma cópia profunda. Criando uma lista usando new ArrayList(list) não criar uma cópia profunda. A criação de cópias profundas é desencorajada e surpreendentemente difícil de fazer de maneira genérica (e não faz sentido em alguns casos, dependendo do(s) tipo(s) de dados na lista). Isso não vai impedir você de poder reverter list e não tem os elementos de listCopy sendo revertida, no entanto.

Coleções.reverse()

A Collections.reverse() é o método padrão para reverter uma coleção e atua como o método “ausente” List.reverse() método. Ele inverte a lista no local:

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 goiaba.reverse(lista)

Se você já usa o Google Guava em seu projeto, também pode aproveitar o Lists classe, que oferece a reverse() método, que não classifica a lista original no local, mas cria uma cópia e inverte a cópia:

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

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

Caso ainda não o tenha, você pode adicionar o Google Guava ao seu projeto usando o Maven, incluindo sua dependência no seu pom.xml arquivo:

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

Ou via Gradle:

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

Observação: Se você ainda não tem o Google Guava, ou não pretende usá-lo para outras partes do seu projeto – não importe apenas para esta operação, e fique com o Collections.reverse() método. Guava é uma grande dependência, e é um grande exagero usá-lo apenas para esta operação.

List.add() e List.remove()

Se você deseja realizar operações adicionais além de apenas reverter a lista - você pode percorrer a lista original, remover os elementos do final, passá-los por um método arbitrário e adicioná-los novamente no início da 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);  

referência

Então, qual é o mais rápido? Isso também depende se você deseja executar a operação no local ou fora do local.

Referência de reversão no local

Vamos comparar as duas abordagens em todos os três métodos, começando com fora do 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);

Isto resulta em:

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

O que acontece quando aumentamos o número de elementos de 100 para 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, ...

Goiaba mantém a marca de 4ms! A abordagem manual tem a pior complexidade de tempo e aumentou linearmente. Collections.reverse() sofrem menos com a ampliação, mas a implementação do Guava sofre menos. No entanto, lembre-se de que não copiamos manualmente a lista para a abordagem Guava. O benchmark mudará quando abandonarmos a ideia de ter uma lista “original” e “invertida”?

Referência de reversão fora do local

Com 1000 elementos, e cada um operando em uma cópia não invertida da lista (que foi excluída das medições de tempo), quando removemos a cópia manual de cada método e executamos novamente o 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, ...

Goiaba ainda consegue superar consistentemente os dois Collections.reverse() e a abordagem manual.

Conclusão

Neste pequeno guia, você aprendeu como reverter uma lista em Java, in-place e out-of-place, preservando a lista original da operação. Nós usamos o Collections.reverse() método, Google Guava Lists.reverse() método e uma abordagem manual.