Reversing a List in Java – In-Place and Out-Of-Place

In this short tutorial, you’ll learn how to reverse a list in-place and out-of-place in Java.

Reversing In-Place and Out-Of-Place

When performing operations on lists – you might want to consider whether the operations are done in-place (changes are enacted on the original object), or whether they’re out-of-place (changes are enacted on a copy, and the original object is unchanged).

Some languages and libraries prefer different default behaviors. In Java, most operations on reversing lists will be in-place.

If this is your desired behavior – great! If not, you’ll want to create a copy of the list before reversing the copy:

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

Note: The clone() method doesn’t create a deep copy. Creating a list using new ArrayList(list) doesn’t create a deep copy. Creating deep copies is discouraged, and surprisingly difficult to do in a generic way (and doesn’t make sense in some cases, depending on the data type(s) in the list). This won’t stop you from being able to reverse list and not have the elements of listCopy being reversed, though.

Collections.reverse()

The Collections.reverse() method is the standard method for reversing a collection, and acts as the “missing” List.reverse() method. It reverses the list in-place:

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)

If you’re using Google Guava already in your project, you can also leverage the Lists class, which offers the reverse() method, which doesn’t sort the original list in-place, but creates a copy and reverses the copy:

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

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

If you don’t have it already, you can add Google Guava to your project using Maven, by including its dependency in your pom.xml file:

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

Or via Gradle:

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

Note: If you don’t already have Google Guava, or don’t intend to use it for other parts of your project – don’t import it just for this operation, and stick to the Collections.reverse() method. Guava is a large dependency, and it’s a major overkill use it for this operation only.

List.add() and List.remove()

If you wish to perform additional operations besides just reversing the list – you can iterate through the original list, remove the elements from the end, pass them through an arbitrary method, and add them back at the start of the list:

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

So, which is the fastest? This also depends on whether you want to perform the operation in-place or out-of-place.

In-Place Reversal Benchmark

Let’s benchmark both approaches on all three of the methods, starting with 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);

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

What happens when we increase the number of elements from 100 to 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 retains the 4ms mark! The manual approach has the worst time complexity, and it rose linearly. Collections.reverse() suffer less from scaling up, but Guava’s implementation suffers the least. Though, keep in mind that we don’t manually copy the list for the Guava approach. Will the benchmark change when we ditch the idea of having an “original” and “reversed” list?

Out-Of-Place Reversal Benchmark

With 1000 elements, and each operating on a non-reversed copy of the list (which was excluded from the time measurements), when we remove the manual copy from each method and re-run the code:

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 still manages to consistently outperform both Collections.reverse() and the manual approach.

Conclusion

In this short guide, you’ve learned how to reverse a list in Java, in-place and out-of-place, preserving the original list from the operation. We’ve used the Collections.reverse() method, Google Guava’s Lists.reverse() method and a manual approach.