Saturday, May 28, 2016

How to reverse an ArrayList in place in Java - Example

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 Java Collection framework. It's 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. Interviewer often tests the candidate with recursive algorithm just to check if they understand recursion or not.

On the same note, if you came here are part of your programming job interview preparation, you should also check Cracking the Coding Interview. It contains, more than 190 coding questions from reputed companies interviews like Facebook, Amazon, Google, and Microsoft.

How to reverse an ArrayList in place in Java

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. If you look carefully, we are just iterating over the array and swapping element from 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.

Though a couple of things, you need to keep in mind. Since we are using 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 linked list doesn't support index-based access and get() method traverse the linked list to retrieve the desired element.

How to reverse an ARrayList in Java place in Java

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

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

 * Java Program to reverse an ArrayList in place.
 * When you reverse ArrayList in place, you are not
 * allowed to use additional buffer e.g. an array
 * or any collection.
public class ReverseArrayListInPlace {

    public static void main(String args[]) {

        // Let's create a list of foods which helps
        // to lose weight, one of the prime concern programmers
        List<String> listOfFood = new ArrayList<>();
        listOfFood.add("Dark Chocolate");
        listOfFood.add("Pure Vegetables");

        System.out.println("Original ArrayList: " + listOfFood);

        // let's now reverse the list in place in Java
        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)); // swap
            listOfFood.set(size - i - 1, food); // swap

        System.out.println("Reversed ArrayList: " + listOfFood);


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 linked list in Java because time complexity would be O(n^2), see Java Programming Interview Exposed by Markham for more details.

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2

Hungry for More?? Here you go
  • How to reverse a String in place in Java? (solution)
  • Top 20 Amazon and Google Interview Questions? (list)
  • How to find all permutations of a String in Java? (solution)
  • How to find duplicate words in Java String? (solution)
  • How to print Fibonacci series without recursion? (solution)
  • How to check if a String is Palindrome in Java? (solution)
  • How to find duplicate elements in an array? (solution)
  • How do you print prime number up to a given number? (solution)
  • How to find the largest prime factor of a number in Java? (solution)
  • How to count the number of words in a given String? (solution)

No comments :

Post a Comment