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:-
|
1 2 3 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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
|
1 2 |
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
