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

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

LinkedList.java

Reverse LinkedList

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

A software Tester who is paid to judge products developed by others. Writing technical posts and creating YouTube videos are my hobbies.

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.