How to reverse an ArrayList in place in Java? Example [Solved] (original) (raw)

How to reverse an ArrayList in place is a popular coding interview problem, not just on Java interviews but also for other programming language. I often ask to check whether candidate is familiar with in place algorithms or not. You can reverse an ArrayList in place in Java by using the same algorithm we have used to reverse an array in place in Java. If you have already solved that problem then It's a no-brainer because ArrayList is nothing but a dynamic array, which can resize itself. All elements of an array are stored in the internal array itself.

By the way, if you need to reverse an ArrayList then you should be using the Collections.reverse() method provided by the Java Collection framework. It's a generic method, so you can not only reverse an ArrayList but also Vector, LinkedList, CopyOnWriteArrayList, or any other List implementation.

Though, worth noting is that this method internally uses a ListIterator for reversing the list, which might not be as efficient as our algorithm.

If this question is asked in an interview, then you can also use recursion to reverse the ArrayList, as shown in this article. The interviewer often tests the candidate with a recursive algorithm just to check if they understand recursion or not.

How to reverse an ArrayList in place in Java? Example

Here is code to reverse an ArrayList of String in place. The algorithm is generic, so you can also use it to reverse an ArrayList of Integer, Double, or any other object.

If you look carefully, we are just iterating over the array and swapping elements from the opposite end until we reach the middle of the list. At this point, our list is completely reversed.

This is the same algorithm we have used to reverse an array earlier.

    int size = listOfFood.size();
    for (int i = 0; i < size / 2; i++) {
        final String food = listOfFood.get(i);
        listOfFood.set(i, listOfFood.get(size - i - 1)); 
        listOfFood.set(size - i - 1, food); 
    }

Though a couple of things, you need to keep in mind. Since we are using the set() method, you cannot pass an unmodifiable or read-only ArrayList to this method. Using this algorithm with read-only ArrayList will throw java.lang.UnSupportedOperationException.

The time complexity of this algorithm is O(n/2) i.e. O(n) where n is the size of ArrayList, and space complexity is O(1) because we don't need additional list or space required by the recursive algorithm to reverse a list in Java.

One more thing which you should keep in mind this algorithm should only be used with List which supports RandomAccess e.g. ArrayList and Vector.

Though you can reverse the LinkedList using this algorithm, it will be of order O(n^2) because the linked list doesn't support index-based access and get() method traverse the linked list to retrieve the desired element.

Since traversal in a linked list is O(n), the time complexity of algorithm rises to O(n^2) for reversing linked list in place using this algorithm.

.

Java Program to reverse an ArrayList in place

Here is our sample Java program to reverse an ArrayList of String in place. The algorithm is generic, so you can also use it to reverse an ArrayList of Integer, Double, or any other object.

import java.util.ArrayList; import java.util.List;

/*

}

Output: Original ArrayList: [Beans, Soup, Dark Chocolate, Yogurt, Sausage, Pure Vegetables, Nuts] Reversed ArrayList: [Nuts, Pure Vegetables, Sausage, Yogurt, Dark Chocolate, Soup, Beans]

That's all about how to reverse an ArrayList in place in Java. Just keep in mind that you can use reverse ArrayList of any object e.g. String, Integer, Float, or Double. You can also use this algorithm to reverse Vector or any other List which supports index-based access.

One more requirement of this algorithm is that List should not be unmodifiable i.e. set() method should not throw UnSupportedOperationException.

Don't use this algorithm to_ reverse the linked list in Java_ because time complexity would be O(n^2), you can see the following courses for more details on calculating time and space complexity.

Other Coding Problems you may want to Practice