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:-
- 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.
- You can use the stack as well which works on the LIFO principle.
- 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
- Let’s create a method (without complete logic) that takes the head of the List as an argument.
- 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.
- 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.
- 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.
- 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.
// To print a LinkedList in reverse order
public void printListinReverseOrder(Node head) {
// Check if the next of current node is null
if(head.next == null)
{
System.out.print("Nodes in LinkedList in revser order are : ");
System.out.print(head.data+" ");
return;
}
// If not then call the same method with
// new head as next node of current node
printListinReverseOrder(head.next);
// If yes then print data
System.out.print(head.data +" ");
}
Complete Program
Node.Java
package DataStructure;
/*
* A node consists of two components. First one is data another one is a pointer to next node.
* If a node does not point to any other node, it will be NULL or point to NULL.
*/
public class Node {
// Data component
int data;
// Pointer component
Node next;
// A constructor to create a node
Node(int d)
{
data = d;
// Since while creating a node we can not say in advance about next node so pointer will be null
next = null;
}
}
LinkedList.java
package DataStructure;
/*
* A single linked list consists of zero or more nodes.
* First node in LinkedList is called Head and last node in a LinkedList
* is called a tail.
*/
public class LinkedList {
public Node headNode; // start of list
public Node tailNode; // end of list
// To add a new node in LinkedList
public LinkedList addNode(LinkedList list, int data) {
// Create a new node with given data
Node newNode = new Node(data);
newNode.next = null;
/*
* before adding a new node, check if list is empty. If list is empty, head and
* tail will be same.
*/
if (list.headNode == null) {
list.headNode = newNode;
list.tailNode = newNode;
}
// if list is not empty then set next of last node to new node from NULL
// and new node will have already null from constructor
else {
list.tailNode.next = newNode;
list.tailNode = newNode;
}
// Return the list by head
return list;
}
// To print a LinkedList
public void printList(LinkedList list) {
// Get the hold of starting node
Node currNode = list.headNode;
System.out.print("Nodes in LinkedList are: ");
// Traverse through the LinkedList till current node becomes null
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
System.out.println();
}
// To print a LinkedList in reverse order
public void printListinReverseOrder(Node head) {
// Check if the next of current node is null
if(head.next == null)
{
System.out.print("Nodes in LinkedList in revser order are : ");
System.out.print(head.data+" ");
return;
}
// If not then call the same method with
// new head as next node of current node
printListinReverseOrder(head.next);
// If yes then print data
System.out.print(head.data +" ");
}
}
PrintLinkedListInReverseOrder.java
package DataStructure;
public class PrintLinkedListInReverseOrder {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.addNode(linkedList,1);
linkedList.addNode(linkedList,2);
linkedList.addNode(linkedList,3);
linkedList.addNode(linkedList,4);
linkedList.addNode(linkedList,5);
linkedList.printList(linkedList);
linkedList.printListinReverseOrder(linkedList.headNode);
}
}
Output
Nodes in LinkedList are: 1 2 3 4 5 Nodes in LinkedList in revser order are : 5 4 3 2 1
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