# 2. Data Structure For Testers – Reverse Linked List in Java

### Introduction

As a part of the Data structure for Testers in this post, we will learn to reverse a Linked List data structure in Java.

### Prerequisite post

Data Structure For Testers – Implement Linked List In Java

### Logic to reverse Linked List

1. A node in a Linked List points to the next node but in a reversed Linked List, a node will point to the previous element.

To reverse a Linked List every node will go through four steps:-

Let’s have three references:-

```a. current = To refer current node
b. next = To refer next node of current node
c. previous = To refer to previous node of current node. Null in beginning```

#### Store the reference of next of current node

Currently, Node will be pointing to the next node or NULL if there is no further node in List. To reverse Linked List, the current node needs to point to the previous node. If we directly change from the next node to the previous node then we will lose the reference to the next node in the List. So the first step will be to store the next node.

next = current -> next

#### Change the reference of next of current node to the previous node

This is the major step where the current node will point to the previous node instead of the next node. We already stored the next node reference. But there is a question that who will be the previous node and how we will get that.

There will be no previous node for the head node. As I said Head node will become the tail so the head next will be null. For any other node in the list, there will be a previous node.

prev = null ( at beginning)

current -> next = prev

#### Assign reference of current to the previous node

We have updated the next of the current node in step 2. Now current node will behave like the previous node for the next node in the list. Let’s store the current node reference in the previous. After this step current will not refer to any node.

previous = current

#### Assign reference of next to current to repeat the process

Now we need to repeat Steps 1 to 3 for the next node in Linked List. We have already stored the next reference in Step 1. Now next node will be the current node.

current = next

Once all nodes go through above four steps, we need to mark current head of the Linked List to “previous” reference as after end of iteration “previous” will be pointing to the last node in Linked List. In short Head and Tail will be interchanged now.

Let’s understand the above flow with the below images:-

Let’s suppose we have a Linked List as below:-

After reverse it should be as below:-

### Java 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.
*/

private Node headNode; // start of list
private 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 reverse a Linked List
Node current;
Node previous = null;
Node next;
while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return list;
}

}
```

```package DataStructure;

public static void main(String[] args) {

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