3. Data Structure For Testers – Print Linked List In Reverse Order Without Reversing List In Java – With Recursion


As a part of the Data structure for Testers in this post, we will learn to print a LinkedList in reverse order without reversing the actual List.

Prerequisite post

Data Structure For Testers – Implement Linked List In Java

Data Structure For Testers – Reverse Linked List In Java

Logic to print Linked List in reverse order

There are multiple ways to achieve the same. Let’s see some logics:-

  1. Get the size of the List and create and create an array of that size. Now iterate given LinkedList and start storing in array in reverse order.
  2. You can use the stack as well which works on the LIFO principle.
  3. Using recursion.

In this post, we will focus on Recursion logic as this solution is expected in interviews and good for logic building as well.

Let’s not get into the word “Recursion”. Think about printing Linked List in reverse order.

Just imagine how you will do it manually. Suppose we have a list as 10, 20, 30, 40, 50. Since we need to print the list in reverse order obviously we will look at the last element first i.e. 50 then 40, 30, 20, and 10.

So for the first-time pass, iterate till last and print data. In the second pass, iterate till the second last element and print data, and repeat the process five times which is the size of the given Linked List.

If you think more then you should understand that we are going to have many iterations and controlling them is also a challenge. We should think now about reducing the number of iterations.

For the first pass when we start iterating to reach the last node of List, in fact, we are reaching the desired state for future passes. Instead of losing that state let’s store that. This we can easily achieve that using recursion.

Basic of Recursion

Recursion is a process in which a method calls itself till exit/stop criteria meet. When a recursive call meets exit criteria, it returns to the previous recursive call.

Step by step recursion logic to print list in reverse order

  1. Let’s create a method (without complete logic) that takes the head of the List as an argument.
  2. We know that we need to iterate to the last element of the List. So check if the next of the current node is pointing to the null or the current node is the last node of the List.
  3. If the current node is not the last element of the list then call (recursion) the method of step 1 again within the same method with the Next element of the current element as Head.
  4. If the current node is the last element of the List then there is no further iteration needed. This will be the exit criteria of a recursive call. Before exiting print the data.
  5. Now all the initiate recursive calls will go in reverse order. In this process let’s print the data of the current node as each call has stored the state before the next recursive call.

Complete Program





You can download/clone the above sample project from here.

You can subscribe to my YouTube channel RetargetCommon to learn from video tutorials.

If you have any doubt, feel free to comment below.
If you like my posts, please like, comment, share and subscribe.

Find all Selenium related posts here, all API manual and automation related posts here, and find frequently asked Java Programs here.

Many other topics you can navigate through the menu

Author: Amod Mahajan

A software Tester who is paid to judge products developed by others. Writing technical posts and creating YouTube videos are my hobbies.

Leave a Reply

Please wait...

Subscribe to new posts to become automation expert

Want to be notified when my new post is published? Get my posts in your inbox.