Friday 1 January 2016

Reversing a Linked List in Java

Hello Friends,

I am with you with a famous problem in data structure, Reversing a Linked List.

For java.util.LinkedList Collections.reverse(List list) can be used. It takes List as input and after the execution of this method, the list passed as parameter is reversed.

But lets see how to reverse a LinkedList if we have made our custom LinkedList. Reversing a custom LinkedList basically involves use of three references. Previous, Current and Next.

The main idea is
1. Starting step : Initialize the current node as head node
2. Preserve Next : In each iteration preserve the next node to the current node,
3. Break and Remake the next link : Making the next node to the current node as previous node.
4. Move ahead : Finally moving previous node to current node and current node to the preserved next node.
5. Loop : Go to step 2 if current node != null
6. Update Head : Make head node as previous node.

Lets see the code below :

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
/**
 * 
 * @author Krishna Kumar
 * 
 * This class demostrates as how to reverse a linked list.
 *
 */
public class ListReversal {

    public static void main(String[] args) {
        reverseJavaUtilListDemo();
        System.out.println();
        reverseCustomLinkedList();
    }
    
    public static void reverseJavaUtilListDemo(){
        System.out.println("Reversing the java.util.List...");
        java.util.List<String> javaUtilList = new ArrayList<>();
        javaUtilList.add("Hello");
        javaUtilList.add("Hi");
        javaUtilList.add("Hola");
        javaUtilList.add("Namaste");
        System.out.println("printing in order of insersion");
        System.out.println(javaUtilList);
        Collections.reverse(javaUtilList);
        System.out.println("printing in reverse order");
        System.out.println(javaUtilList);
    }
    
    public static void reverseCustomLinkedList(){
        System.out.println("Reversing the custom list");
        CustomLinkedList<String> customList = new CustomLinkedList<String>();
        customList.add("Hello");
        customList.add("Hi");
        customList.add("Hola");
        customList.add("Namaste");
        System.out.println("printing in order of insersion");
        customList.print();
        customList.reverse();
        System.out.println("printing in reverse order");
        customList.print();
    }

    public static class CustomLinkedList<V> implements Iterable<V> {
        private Node head;
        private Node tail;

        public void add(V data) {
            if (head == null) {
                head = new Node(data);
                tail = head;
            } else {
                Node newNode = new Node(data);
                tail.next = newNode;
                tail = newNode;
            }
        }

        public void reverse() {
            Node previous = null;
            Node current = head;
            Node next = null;

            while (current != null) {
                next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }

            head = previous;
        }

        private class Node {
            V data;
            Node next;

            public Node(V data) {
                this.data = data;
            }
        }

        public void print() {
            for (V data : this) {
                System.out.print(data + "->");
            }
            System.out.println("null");
        }

        @Override
        public Iterator<V> iterator() {
            return new Iterator<V>() {
                Node temp = head;

                @Override
                public boolean hasNext() {
                    return temp != null;
                }

                @Override
                public V next() {
                    V data = temp.data;
                    temp = temp.next;
                    return data;
                }
            };
        }
    }
}

Below is the summary of the above with an example.