How to reverse a singly linkedlist

How to reverse a singly linked list in Java? Example



I'll show you how to reverse a singly linked list in Java without recursion. A singly linked list, also known as just linked list is a collection of nodes which can only be traversed in one direction e.g. forward. Each node in the linked list contains two things, a data and a pointer to next node in the list. In order to reverse the linked list, we need to iterate through the list and at each step we need to reverse the link e.g. after first iteration head will point to null and next element will point to head. At the end of traversal when you reach the tail of linked list, the tail will point to the second last element and it will become a new head because you can traverse through all elements from this node.


In order to demonstrate that our reverse method is working, we will not only have to create a linked list but also to populate the linked list. In order to populate, we need to implement the add() method on singly linked list. You have two choices, either add the element at the head or at the tail, adding element to head is easy as it doesn't require a traversal till the end but if you want to create a list which contains elements in the order they are added then we need to add nodes at the end of linked list.







EXAMPLE













public class SinglyLinkedListImpl<T> {

  

    private Node<T> head;

      

    public void add(T element){

          

        Node<T> nd = new Node<T>();

        nd.setValue(element);

        System.out.println("Adding: "+element);

        Node<T> tmp = head;

        while(true){

            if(tmp == null){

                //since there is only one element, both head and

                //tail points to the same object.

                head = nd;

                break;

            } else if(tmp.getNextRef() == null){

                tmp.setNextRef(nd);

                break;

            } else {

                tmp = tmp.getNextRef();

            }

        }

    }

      

    public void traverse(){

          

        Node<T> tmp = head;

        while(true){

            if(tmp == null){

                break;

            }

            System.out.print(tmp.getValue()+"\t");

            tmp = tmp.getNextRef();

        }

    }

     

    public void reverse(){

         

        System.out.println("\nreversing the linked list\n");

        Node<T> prev = null;

        Node<T> current = head;

        Node<T> next = null;

        while(current != null){

            next = current.getNextRef();

            current.setNextRef(prev);

            prev = current;

            current = next;

        }

        head = prev;

    }

     

    public static void main(String a[]){

        SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();

        sl.add(3);

        sl.add(32);

        sl.add(54);

        sl.add(89);

        System.out.println();

        sl.traverse();

        System.out.println();

        sl.reverse();

        sl.traverse();

    }

}

  

class Node<T> implements Comparable<T> {

      

    private T value;

    private Node<T> nextRef;

      

    public T getValue() {

        return value;

    }

    public void setValue(T value) {

        this.value = value;

    }

    public Node<T> getNextRef() {

        return nextRef;

    }

    public void setNextRef(Node<T> ref) {

        this.nextRef = ref;

    }

    @Override

    public int compareTo(T arg) {

        if(arg == this.value){

            return 0;

        } else {

            return 1;

        }

    }

}