How To Contrary A Singly Linked Listing Without Recursion Inwards Java? Iterative Solution

Hello guys, contrary a linked listing is a mutual coding work from Programming Job interviews as well as I am certain you lot convey seen this inward your career, if you lot are not, peradventure you lot are a fresher as well as you lot volition going to notice nearly this rattling before long inward your side past times side technical interview. In the concluding article, I convey shown you lot how to role recursion to contrary a linked list as well as today, I'll exhibit you lot how to contrary a singly linked listing inward Java without recursion. H5N1 singly linked list, too known every bit only linked list is a collection of nodes which tin orbit the sack exclusively hold upward traversed inward i management similar inward the forrard management from caput to tail. Each node inward the linked listing contains ii things, a information as well as a pointer to the side past times side node inward the list.

In guild to contrary the linked list, you lot demand to iterate through the list as well as at each measurement nosotros demand to contrary the link similar afterward showtime iteration caput volition indicate to zippo as well as side past times side chemical ingredient volition indicate to head. At the halt of traversal when you lot accomplish the tail of the linked list, the tail volition indicate to the minute concluding chemical ingredient as well as it volition acquire a novel caput because you lot tin orbit the sack straight off traverse through all elements from this node.

Since nosotros cannot role the java.util.LinkedList class to demonstrate this example, every bit it is a doubly linked listing as well as too inward most of the fourth dimension on coding interviews, the Interviewer volition non allow you lot to role existing Java classes or API.

Anyway,  inward a doubly linked list, you lot tin orbit the sack traverse inward both directions like both forrard as well as backward every bit each node contains the reference to both previous as well as side past times side node.

Btw, if you lot are non familiar alongside the linked listing information structure, it's improve to showtime locomote through a  practiced information construction as well as algorithm course of education like Data Structures as well as Algorithms: Deep Dive Using Java to larn to a greater extent than nearly linked listing information structure.

Implementing Your Own Linked List on Interviews

Since using existing Java classes are straight off allowed on Programming Job interviews, you lot demand to do your ain to write code. For this example, I convey created our ain singly linked listing class. Similar to java.util.LinkedList which too contains a nested static class Node, which represents a node inward the linked list.

This shape contains an integer attribute to concord the information business office as well as around other Node reference to indicate to the side past times side i inward the list. If you lot desire to do a Generic linked list, you lot should supervene upon int with T , a generic type, every bit shown here.

In guild to demonstrate that our contrary method is working, nosotros volition non exclusively convey to do a linked listing but too demand to populate the linked list. In guild to populate, you lot demand to implement the add() method on the singly linked list.

You convey ii choices, either add the chemical ingredient at the head or at the tail, adding chemical ingredient to caput is tardily every bit it doesn't require a traversal till the halt but if you lot desire to do a listing which contains elements inward the guild they are added thus nosotros demand to add together nodes at the halt of linked list.

I convey too created a print() method to impress all nodes of the singly linked list, separated past times space. This method is rattling useful to demonstrate that our contrary method is truly working or not, every bit you lot tin orbit the sack impress the linked listing before as well as afterward reversal.

If you lot grapple alongside implementing essential information structures similar linked list, binary tree, the hash tabular array inward your ain code on whatever programming linguistic communication similar Java thus I advise you lot join linked listing information structure. I convey farther implemented add() as well as print() method to add together elements to the linked listing as well as impress them inward forwarding order.

The logic of reversing the linked listing is encapsulated within the reverse() method. It traverses through the linked listing from caput to tail as well as reverses the link inward each measurement similar each node instead of pointing to side past times side chemical ingredient started pointing to the previous node, this means the whole linked listing is reversed when you lot accomplish the concluding element, which thus becomes the novel caput of a linked list.

Here is a squeamish diagram which explains the algorithm to contrary a linked list without recursion inward Java:

You tin orbit the sack run across that links are contrary inward each steps using the pointers previous as well as next. This is too known every bit the iterative algorithm to contrary the linked listing inward Java. For the recursive algorithm, you lot tin orbit the sack too run 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();    }  } /**  * H5N1 shape to correspond singly listing inward 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 current = head;     while (current != null) {       if (current.next == null) {         current.next = node;         break;       }       electrical current = 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 current = null;      while (pointer != null) {       electrical current = pointer;       pointer = pointer.next;        // contrary the link       current.next = previous;       previous = current;       caput = current;     }    } } Output 1 2 three  three 2 1 

You tin orbit the sack run across that linked listing has reversed, before 1 was the showtime chemical ingredient straight off it is concluding as well as three is the showtime chemical ingredient of linked listing or head.


That's all nearly how to contrary a singly linked listing inward Java without using recursion. Yes, nosotros convey non used recursion inward this solution, instead, nosotros convey used iteration. You tin orbit the sack run across the acre loop within the reverse() method.

Further Learning
Data Structures as well as Algorithms: Deep Dive Using Java
solution)

How to notice the third chemical ingredient from the halt of a linked listing inward Java? (solution)

Top xv Data Structure as well as Algorithm Interview Questions (see here)

Top twenty String coding interview questions (see here)

When to role ArrayList vs LinkedList inward Java? (answer)

How to notice if a singly linked listing contains a loop? (solution)

How to notice the showtime as well as concluding chemical ingredient of a linked listing inward Java? (solution)

How to convert a linked listing to an array inward Java? (example)

How to search chemical ingredient within a linked listing inward Java? (solution)

What is the departure betwixt LinkedList as well as ArrayList inward Java? (answer)

Top thirty Array Coding Interview Questions alongside Answers (see here)

Top thirty linked listing coding interview questions (see here)

Top l Java Programs from Coding Interviews (see here)

5 Free Data Structure as well as Algorithms Courses for Programmers (courses)

10 Algorithms Books Every Programmer Should read (books)

50+ Data Structure as well as Algorithms Problems from Interviews (questions)

10 Free Data Structure as well as Algorithm Courses for Programmers (courses)

100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article thus far. If you lot similar this article thus delight part alongside your friends as well as colleagues. If you lot convey whatever query or dubiousness thus delight allow us know as well as I'll essay to notice an reply for you. As ever suggestions, comments, innovative as well as improve answers are most welcome.

Btw, if you lot acquire this query asked on the existent interview, you lot would hold upward most probable asked to contrary the linked listing using recursion now. So, hold off for my around other article to run across that solution or cheque out the Cracking the Coding Interview book, which contains a solution of this work along alongside several others.

P. S. - If you lot are looking for around Free Algorithms courses to improve your agreement of Data Structure as well as Algorithms, thus you lot should too cheque the Easy to Advanced Data Structures course of education on Udemy.