How to opposite a singly linked listing inwards Java? Example

In this article, I'll demonstrate y'all how to contrary a singly linked listing inwards Java without recursion. Influenza A virus subtype H5N1 singly linked list, every bit good known every bit simply linked listing is a collection of nodes which tin alone last traversed inwards i management e.g. forward. Each node inwards the linked listing contains ii things, a information in addition to a pointer to side past times side node inwards the list. In fellowship to contrary the linked list, nosotros demand to iterate through the list in addition to at each measuring nosotros demand to contrary the link e.g. afterwards starting fourth dimension iteration caput volition signal to naught in addition to side past times side chemical ingredient volition signal to head. At the destination of traversal when y'all achieve the tail of linked list, the tail volition signal to the minute concluding chemical ingredient in addition to it volition travel a novel caput because y'all tin traverse through all elements from this node.

Since nosotros cannot role java.util.LinkedList to demonstrate this example, every bit it is a doubly linked list. In doubly linked listing y'all tin traverse inwards both directions i.e. forrard in addition to backward every bit each node contains the reference to both previous in addition to side past times side node. See a expert information construction in addition to algorithm mass similar Introduction to Algorithms past times Thomas H. Cormen to acquire to a greater extent than close linked listing information structure.

For this example, I bring created our ain singly linked listing class. Similar to java.util.LinkedList it every bit good contains a nested static class Node, which represents a node the linked list. This contains an integer attribute to concur the information business office in addition to to a greater extent than or less other Node reference to signal to the side past times side i inwards the list. If y'all desire to practise a Generic linked list, y'all should supercede int amongst T , a generic type, every bit shown here.

In fellowship to demonstrate that our contrary method is working, nosotros volition non alone bring to practise a linked listing but every bit good to populate the linked list. In fellowship to populate, nosotros demand to implement the add() method on singly linked list. You bring ii choices, either add the chemical ingredient at the head or at the tail, adding chemical ingredient to caput is slow every bit it doesn't require a traversal till the destination but if y'all desire to practise a listing which contains elements inwards the fellowship they are added in addition to hence nosotros demand to add together nodes at the destination of linked list.

I bring every bit good created a print() method to impress all nodes of singly linked list, separated past times space. This method is real useful to demonstrate that our contrary method is genuinely working or not, every bit y'all tin impress the linked listing before in addition to afterwards reversal.

Java Program to contrary singly linked listing without recursion

Here is our sample plan to demonstrate how to contrary a linked listing inwards Java. In fellowship to reverse, I bring starting fourth dimension created a degree called SinglyLinkedList, which stand upwards for a linked listing information structure. I bring farther implemented add() in addition to print() method to add together elements to the linked listing in addition to impress them inwards forrard order.

The logic of reversing the linked listing is encapsulated within the reverse() method. It traverses through the linked listing from caput to tail in addition to reverses the link inwards each measuring e.g. each node instead of pointing to side past times side chemical ingredient started pointing to the previous node, this agency the whole linked listing is reversed when y'all achieve the concluding element, which in addition to hence becomes the novel caput of linked list.

Here is a dainty diagram which explains the algorithm to contrary linked listing without recursion inwards Java:

You tin come across that links are contrary inwards each steps using the pointers previous in addition to next. This is every bit good known every bit the iterative algorithm to contrary the linked listing inwards Java. For the recursive algorithm, come across Introduction to Algorithms mass past times Thomas H. Cormen.

package test;  /**  * Java Program to contrary a singly listing without using recursion.  */ public class LinkedListProblem {    public static void main(String[] args) {      // creating a singly linked list     SinglyLinkedList.Node caput = new SinglyLinkedList.Node(1);     SinglyLinkedList linkedlist = new SinglyLinkedList(head);      // adding node into singly linked list     linkedlist.add(new SinglyLinkedList.Node(2));     linkedlist.add(new SinglyLinkedList.Node(3));     // printing a singly linked list     linkedlist.print();      // reversing the singly linked list     linkedlist.reverse();      // printing the singly linked listing again     linkedlist.print();    }  } /**  * Influenza A virus subtype H5N1 degree to stand upwards for singly listing inwards Java  *   * @author WINDOWS 8  *  */ class SinglyLinkedList {    static class Node {      private int data;     private Node next;      public Node(int data) {       this.data = data;     }      public int data() {       return data;     }      public Node next() {       return next;     }   }    private Node head;    public SinglyLinkedList(Node head) {     this.head = head;   }    /**    * Java method to add together an chemical ingredient to linked listing    * @param node    */   public void add(Node node) {     Node electrical flow = head;     while (current != null) {       if (current.next == null) {         current.next = node;         break;       }       electrical flow = current.next;     }   }    /**    * Java method to impress a singly linked listing    */   public void print() {     Node node = head;     while (node != null) {       System.out.print(node.data() + " ");       node = node.next();     }     System.out.println("");   }    /**    * Java method to contrary a linked listing without recursion    */   public void reverse() {     Node pointer = head;     Node previous = null, electrical flow = null;      while (pointer != null) {       electrical flow = pointer;       pointer = pointer.next;        // contrary the link       current.next = previous;       previous = current;       caput = current;     }    } } Output 1 2 three  three 2 1

You tin come across that linked listing has reversed, before 1 was the starting fourth dimension chemical ingredient straightaway it is concluding in addition to three is the starting fourth dimension chemical ingredient of linked listing or head.

That's all close how to contrary a singly linked listing inwards Java without using recursion. Yes, nosotros bring non used recursion inwards this solution, instead, nosotros bring used iteration. You tin come across the field loop within reverse() method. Though, if y'all acquire this enquiry asked on the existent interview, y'all would last most probable asked to contrary the linked listing using recursion now. So, await for my to a greater extent than or less other article to come across that solution or cheque out the Cracking the Coding Interview book, which contains a solution of this work along amongst several others.

Further Reading
Algorithms in addition to Data Structures - Part 1 in addition to 2
Java Fundamentals, Part 1 in addition to 2

Other linked listing tutorials for Java Programmers

When to role ArrayList vs LinkedList inwards Java? (answer)
How to honour if a singly linked listing contains a loop? (solution)
How to honour the starting fourth dimension in addition to concluding chemical ingredient of linked listing inwards Java? (solution)
How to honour middle chemical ingredient of linked listing inwards i pass? (solution)
How to convert linked listing to array inwards Java? (example)
How to search chemical ingredient within linked listing inwards Java? (solution)
What is the divergence betwixt LinkedList in addition to ArrayList inwards Java? (answer)