# 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.
```// To print a LinkedList in reverse order
// Check if the next of current node is null
{
System.out.print("Nodes in LinkedList in revser order are : ");
return;
}

// If not then call the same method with
// new head as next node of current node

// If yes then print 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;
}
}
```

```package DataStructure;

/*
* A single linked list consists of zero or more nodes.
* is called a tail.
*/

public Node headNode; // start of list
public Node tailNode; // end of list

// 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.
*/
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;
}

// Get the hold of starting node
// 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
// Check if the next of current node is null
{
System.out.print("Nodes in LinkedList in revser order are : ");
return;
}

// If not then call the same method with
// new head as next node of current node

// If yes then print data
}
}

```

```package DataStructure;

public static void main(String[] args) {

}
}
```
##### Output
```Nodes in LinkedList are: 1 2 3 4 5
Nodes in LinkedList in revser order are : 5 4 3 2 1 ```