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

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.
Head will become Tail in a reversed Linked List.

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:-

Logic in pictures

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; 
	}
}

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 {

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

}

Reverse LinkedList

package DataStructure;

public class ReverseLinkedList {

public static void main(String[] args) {
		// Create Linked list
		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);
		
		// Reverse LinkedList
		linkedList = linkedList.reverseList(linkedList);
		
		linkedList.printList(linkedList);
		
	}
}

Output

Nodes in LinkedList are: 1 2 3 4 5 
Nodes in LinkedList 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