Wednesday, July 10, 2024

How to reverse an ArrayList in place in Java? Example [Solved]

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.

// 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
        }

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;

/*
 * 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("Beans");
        listOfFood.add("Soup");
        listOfFood.add("Dark Chocolate");
        listOfFood.add("Yogurt");
        listOfFood.add("Sausage");
        listOfFood.add("Pure Vegetables");
        listOfFood.add("Nuts");

        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);
    }

}

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 
  • How to reverse a String in place in Java? (solution)
  • Top 20 Amazon and Google Interview Questions? (list)
  • How to implement the Quicksort algorithm in Java? [solution]
  • 7 Best courses to learn Data Structure and Algorithms (courses)
  • How to find all permutations of a String in Java? (solution)
  • Write a program to find the top two numbers from an integer array? [solution]
  • How to find duplicate words in Java String? (solution)
  • 10+ Algorithms and Programming Courses to Crack Interviews (courses)
  • How to check if an array contains a number in Java? [solution]
  • How to print the Fibonacci series without recursion? (solution)
  • 10 Free Data Structure and Algorithms Courses for beginners (free courses)
  • How to find the highest and lowest element in the unsorted array? [solution]
  • 10 Books to learn Data Structure and Algorithms (books)
  • How to check if a String is a Palindrome in Java? (solution)
  • 10 Data Structure and Programming Courses to Crack Interviews (courses)
  • How to find duplicate elements in an array? (solution)
  • 20+ binary tree questions from coding interviews (questions)
  • How do you print prime numbers up to a given number? (solution)
  • 25 systems design questions from interviews (questions)
  • 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)

1 comment :

Anonymous said...

Many people don't know but in place algorithm is so powerful and beautiful that you can sort an array of 1 billion numbers with that. Imagine if you needed extra space for that, most likely many system will not have that much memory spare for you. That's why knowing in place algorithm is must for any programmer

Post a Comment