Wednesday 20 November 2013

Reverse a LinkedList in Java?

Java has a built in functionality to reverse Linked List. This function is available in Collections class and the method name is reverse(). It is a static function so you can simply call it using Collections.reverse(yourLinkedList);


Code :

import java.util.LinkedList;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/20/13
 * Time: 5:20 PM
 */
public class LinkedListReversal {
    public static void main(String args[]){
        LinkedList<String> myLList = new LinkedList<String>();
        myLList.add("A");
        myLList.add("B");
        myLList.add("C");
        myLList.add("D");
        System.out.println("Original LL : " + myLList);
        Collections.reverse(myLList);
        System.out.println("Revered LL : " + myLList);
    }
}


Output :

Original LL : [A, B, C, D]
Revered LL : [D, C, B, A]

This shows you are aware of Java APIs but ultimately interviewer will get to the logic part as of how this is exactly done. or to put it in other words how is the method Collections.reverse() exactly implemented?

You can view the source code to know the exact method but as far as our LinkedList reversal problem is concerned we do the following -

Code : 


import java.util.LinkedList;
import java.util.ListIterator;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/20/13
 * Time: 5:20 PM
 */
public class LinkedListReversal {
    public static void reverse(LinkedList<String> linkedList) {
        ListIterator<String> forwardIterator = linkedList.listIterator();
        ListIterator<String> backwardIterator = linkedList.listIterator(linkedList.size());
        for(int i = 1;i<=(linkedList.size()/2);i++){
            String tempString = forwardIterator.next();
            forwardIterator.set(backwardIterator.previous());
            backwardIterator.set(tempString);
        }
    }
    public static void main(String args[]){
        LinkedList<String> myLList = new LinkedList<String>();
        myLList.add("A");
        myLList.add("B");
        myLList.add("C");
        myLList.add("D");
        System.out.println("Original LL : " + myLList);
        LinkedListReversal.reverse(myLList);
        System.out.println("Revered LL : " + myLList);
    }
}

Output : 



Original LL : [A, B, C, D]

Revered LL : [D, C, B, A]


Note : LinkedList data structure in Java is in fact a doubly linked list and hence we could use previous() on the list iterator. If you look at the LinkedList class you will find Node structure as follows


    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }


If you notice we have both next and prev nodes which implies it is a doubly Linked List.

For java code of reversing a linkedlist from very basics(from creating using Node data structure) you can refer to How to reverse a LinkedList in Java? )

t> UA-39527780-1 back to top