1. Overview
ArrayList is an often-used List implementation in Java.
In this tutorial, we’ll explore how to reverse an ArrayList.
2. Introduction to the Problem
As usual, let’s understand the problem through an example. Let’s say we have a List of Integer:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
After the reversing, we’re expecting to have the result:
List<Integer> EXPECTED = new ArrayList<>(Arrays.asList(7, 6, 5, 4, 3, 2, 1));
So, the requirement looks pretty straightforward. However, the problem may have a couple of variants:
- Reversing a List in place
- Reversing a List and returning the result as a new List object
We’ll cover both cases in this tutorial.
The Java standard library has provided a helper method to do the job. We’ll see how we can quickly solve the problem using this method.
Additionally, considering that some of us may be learning Java, we’ll address two interesting but efficient implementations of reversing a List.
Next, let’s see them in action.
3. Using the Standard Collections.reverse Method
The Java standard library has provided the Collections.reverse method to reverse the order of the elements in the given List.
This convenient method does in-place reversing, which will reverse the order in the original list it received. But, first, let’s create a unit test method to understand it:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
Collections.reverse(aList);
assertThat(aList).isEqualTo(EXPECTED);
When we execute the test above, it passes. As we’ve seen, we’ve passed the aList object to the reverse method, and then the order of the elements in the aList object gets reversed.
In case we don’t want to change the original List, and expect to get a new List object to contain the elements in the reversed order, we can pass a new List object to the reverse method:
List<Integer> originalList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> aNewList = new ArrayList<>(originalList);
Collections.reverse(aNewList);
assertThat(aNewList).isNotEqualTo(originalList).isEqualTo(EXPECTED);
In this way, we keep the originalList untouched, and the order of the elements in aNewList is reversed.
As we can see from the two examples above, the standard Collections.reverse method is pretty convenient for reversing a List.
However, if we’re learning Java, probably, we want to practice implementing a “reverse” method by ourselves.
Next, let’s explore a couple of nice implementations: one using recursion and another using a simple loop.
4. Reversing a List Using Recursion
First, let’s implement our own list-reverse method using the recursion technique. First, let’s take a look at the implementation:
public static <T> void reverseWithRecursion(List<T> list) {
if (list.size() > 1) {
T value = list.remove(0);
reverseWithRecursion(list);
list.add(value);
}
}
As we can see, the implementation above looks pretty compact. Now, let’s understand how it works.
The stop condition in our recursion logic is list.size() <=1. In other words, if the list object is empty or contains only a single element, we stop the recursion.
In each recursion call, we execute “T value = list.remove(0)“, popping the first element from the list. It works in this way:
recursion step 0: value = null, list = (1, 2, 3, ... 7)
|_ recursion step 1: value = 1, list = (2, 3, 4,...7)
|_ recursion step 2: value = 2, list = (3, 4, 5, 6, 7)
|_ recursion step 3: value = 3, list = (4, 5, 6, 7)
|_ ...
|_ recursion step 6: value = 6, list = (7)
As we can see, when the list object contains only one element (7), we stop the recursion and then start executing list.add(value) from the bottom. That is, we first add 6 to the end of the list, then 5, then 4, and so on. In the end, the order of the elements in the list has been in-place reversed. Further, this method runs in linear time.
Next, let’s create a test to verify if our recursion implementation works as expected:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);
If we run the test, it passes. So, our recursion implementation solves the problem.
5. Reversing a List Using Iteration
We’ve just reversed the list using recursion. Alternatively, we can solve the problem using iteration.
First, let’s have a look at the implementation:
public static <T> void reverseWithLoop(List<T> list) {
for (int i = 0, j = list.size() - 1; i < j; i++) {
list.add(i, list.remove(j));
}
}
As we can see, the iteration implementation is pretty neat as well. However, we have only one for loop, and in the loop body, we have only one single statement.
Next, let’s understand how it works.
We defined two pointers, i and j, on the given list. The pointer j always points to the last element in the list. But the point i increments from 0 to j-1.
We remove the last element at each iteration step and fill it to the i-th position using list.add(i, list.remove(j)). When i reaches j-1, the loop ends, and we’ve reversed the list:
Iteration step 0: i = j = null, list = (1, 2, 3,...7)
Iteration step 1: i = 0; j = 6
|_ list.add(0, list.remove(6))
|_ list = (7, 1, 2, 3, 4, 5, 6)
Iteration step 2: i = 1; j = 6
|_ list.add(1, list.remove(6))
|_ list = (7, 6, 1, 2, 3, 4, 5)
...
Iteration step 5: i = 4; j = 6
|_ list.add(4, list.remove(6))
|_ list = (7, 6, 5, 4, 3, 1, 2)
Iteration step 6: i = 5; j = 6
|_ list.add(5, list.remove(6))
|_ list = (7, 6, 5, 4, 3, 2, 1)
The method runs in linear time as well.
Finally, let’s test our method, and see if it works as expected:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithLoop(aList);
assertThat(aList).isEqualTo(EXPECTED);
When we run the test above, it passes.
6. Conclusion
In this article, we’ve addressed how to reverse an ArrayList through examples. The standard Collections.reverse method is pretty handy to solve this problem.
However, if we would like to create our own reversing implementations, we’ve learned two efficient in-place reversing approaches.
As usual, the complete code of this article can be found over on GitHub.
