[Solved] How to Reverse an ArrayList in Java using Recursion? Example Tutorial (original) (raw)

If you ever need to reverse a List in Java e.g. ArrayList or LinkedList, you should always use the Collections.reverse() method. It's safe and tested and probably performs better than the first version of the method you write to reverse an ArrayList in Java. It's also one of the recommended best practices to prefer the library method instead of writing your own, as advised by great Joshua Bloch in Effective Java. There are so many benefits of using library methods like it was written by experts, thoroughly and open-source tested, and more actively maintained. Anyway, if you have been asked to write a function to reverse a List using recursion in Java, maybe as part of your homework, assignment, or during an interview, then you are in the right place.

In this tutorial, I'll show you how to reverse an ArrayList of String using recursion. You can use this technique to reverse any type of List like List of Integer, List of String, or List of your own custom objects.

In a recursive algorithm, a function calls itself to do the job. After each pass problem becomes smaller and smaller until it reaches the base case from where the programmer starts to wind down. The base case is very important for a recursive algorithm because without this your program will never finish and you will quickly run out of memory in both Stack and Heap.

In order to reverse a List using recursion, our base case is a list of one element. If your list contains one element then the reverse of that list is the list itself, so just return it. Now, on each pass, we need to add the last element on the list into a new list called reversed.

Once the program reaches the base case and starts winding down, we end up with all the elements in the reverse order. To accommodate that, we have used the addAll() method of java.util.Collection class.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms courses like these best Data Structure and Algorithms courses to fill the gaps in your understanding.

Btw, recursive algorithms are quite popular in programming job interviews. You will often find recursive problems like the Fibonacci series, All permutations of String, or reverse String in place on written tests, telephonic rounds, or the face-to-face round of Java interviews.

If you are seriously preparing for a programming job, this is the one topic you cannot ignore. You can also check Cracking the Coding Interview book, which contains more than 189 Coding problems and solutions for few more recursive problems. It's one of the best books for practicing coding problems, especially from a programming interview perspective.

Java Program to Reverse a List using Recursion? Example

Here is our sample Java program to reverse a List in Java. It demonstrates both the practical approaches using the Collections.reverse() method and the algorithmic approach by using recursion.

Btw, a recursive method is quite expensive here as for each recursive call a new list is created, which is held in memory until the list is completely sorted. For a huge list of million elements, this can easily make the program goes Out Of Memory because the list will be created in the heap space.

There is also a risk of StackOverFlow because each method call will take some space on stack memory. Instead of using recursion here, you can use iteration to sort the list in place, which will just need a variable to hold one value to swap the first element to last and so on. The algorithm is similar to what we have learned while reversing an array in place in Java.

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

/*

• Java Program to demonstrate how to reverse a List.

• In this example, you will see two ways to reverse a List,

• first, using Collections.reverse() method and second

• by writing your own method using recursion. */ public class TestSolution {

  public static void main(String args[]) {

   List<String> books = new ArrayList<>();
   books.add("Beautiful Code");
   books.add("Clean Code");
   books.add("Working Effectively with Legacy Code");
  
   System.out.println("Original order of List: " + books);
  
   // Easy way to reverse a List in Java, use Collections.reverse()
   // method, use this to reverse ArrayList or LinkedList in
   // production
   Collections.reverse(books);
  
   System.out.println("The reversed List: " + books);
  
   // Now, let's try to reverse a List using recursion
   List<String> output = reverseListRecursively(books);
   System.out.println("Reversed list reversed again: " + output);

  }

  /**

  • A recursive algorithm to reverse a List in Java

  • @param list

  • @return */ private static List reverseListRecursively(List list) { if (list.size() <= 1) { return list; }

    List reversed = new ArrayList<>(); reversed.add(list.get(list.size() - 1)); // last element reversed.addAll( reverseListRecursively(list.subList(0, list.size() - 1))); return reversed;

  }

}

Output Original order of List: [Beautiful Code, Clean Code, Working Effectively with Legacy Code] The reversed List: [Working Effectively with Legacy Code, Clean Code, Beautiful Code] Reversed list reversed again: [Beautiful Code, Clean Code, Working Effectively with Legacy Code]

That's all about how to reverse a list in Java. You have seen 2 ways to reverse the list, first by using the Collections.reverse() method, which you should use to sort any List implementation like Vector, LinkedList, CopyOnWriteArrayList, or ArrayList in Java in production. The recursive algorithm is just for educational purposes. There is a task for you, try to reverse the list in place using an iterative algorithm, for the solution you can check here.