Make Selenium Easy

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

Introduction

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

Node.Java

LinkedList.java

PrintLinkedListInReverseOrder.java

Output

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.
#ThanksForReading
#HappyLearning

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

My name is Amod Mahajan and I am an IT employee with 6+ years of experience in Software testing and staying in Bengaluru. My area of interest is Automation testing. I started from basics and went through so many selenium tutorials. Thanks to Mukesh Otwani as his tutorials are easy and cover basics to advance. I have habit of exploring concepts by deep diving. I used to make notes. I thought of sharing my knowledge through posts and now I am here. #KeepLearning #ShareLearning

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.

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

by Amod Mahajan time to read: 4 min
0
%d bloggers like this: