How to reverse a doubly linked list ?

I talked about how to reverse a singly linked list earlier. That was slightly tricky to understand.
Reversing a doubly linked list is relatively easy. The logic is : You need to keep on changing the next and previous pointers as you traverse the entire list. Here is the code snippet in Java :

public void reverse()
{
    if (first == null) 
          return;

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

Implement a Queue using two stacks

Recently I encountered a trivial but interesting question. "How to implement a queue using two stacks ? ". My first reaction was "Why would I do that ..? " But if I am forced to do such a thing, how would I go about doing it ? So, here is how we implement a queue using two stacks.
Logic : We'll implement a FIFO queue using two stacks. Lets call the stacks Instack and Outstack. An element is inserted in the queue by pushing it into the Instack. An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
We start with a Stack Interface :

public interface Stack {
        void push( Object x );
        Object pop( );
        Object top( );
        boolean isEmpty( );
        void makeEmpty( );
}

and a class that implements this interface :

public class ArrayStack implements Stack {
        private Object [ ] theArray;
        private int        topOfStack;
        private static final int DEFAULT_CAPACITY = 10;
        public ArrayStack( ) {
                theArray = new Object[ DEFAULT_CAPACITY ];
                topOfStack = -1;
        }
        public boolean isEmpty() {
                return topOfStack==-1;
        }
        public void makeEmpty() {
                topOfStack= -1;
        }
        public Object pop() {
                if(!isEmpty())
                return theArray[topOfStack--];
                else
                return null;
        }
        public void push(Object x) {

                if(!isFull())
                theArray[++topOfStack] = x;
        }
        public Object top() {
                return theArray[topOfStack];
        }
        public static void main(String[] args) {
                //Not relevant to our code
        }
        public boolean isFull()
        {
                return (topOfStack == theArray.length);

        }
}

Now we come to actual class that implements a Queue using two stacks.

public class stackQueue {

       ArrayStack inStack = new ArrayStack();
       ArrayStack outStack = new ArrayStack();

       public static void main(String[] args)
       {
               stackQueue queue = new stackQueue();
               queue.enqueue(new String("first"));
               queue.enqueue(new String("second"));
               queue.enqueue(new String("third"));
               queue.enqueue(new String("fourth"));
               queue.enqueue(new String("fifth"));
               System.out.println("1. " + queue.dequeue());
               System.out.println("2. " + queue.dequeue());
               System.out.println("3. " + queue.dequeue());
               System.out.println("4. " + queue.dequeue());
               System.out.println("5. " + queue.dequeue());
       }

       public void enqueue(Object value)
       {
               inStack.push(value);
       }
       public Object dequeue()
       {
               if(outStack.isEmpty())
               {
                       while( ! inStack.isEmpty())
                       {
                               outStack.push(inStack.pop());
                       }
               }
               return outStack.pop();
       }
}

Efficient String Permutation Program.

The following piece of a code is a very efficient use of recursion to find the possible permutation of a string.

public class Permutations {

   public  static void perm1(String s) { perm1("", s); }

   private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0)
            System.out.println(prefix);
        else {
            for(int i = 0; i < N; i++){
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
            }
        }
    }
    public static void main(String[] args) {
       String alphabet = "Test";
       String elements = alphabet.substring(0, alphabet.length());
       perm1(elements);
    }
}

Debugging this code might prove to be a little difficult though but excellent logic though.

Technorati Tags: Programming, Data Structures, Java

Find loops in a linked list.

There are several algorithms floating on the net to detect a cycle/loop in a linked list. The following code detects cycle in a linked list in time O(N) and space O(1).

/*Algorithm : P2 is moving through the list twice as fast as P1.
  If the list is circular, it will eventually get around P1 and meet */

  public boolean hasCycle()
  {
      DoubleNode p1,p2;
      p1=p2=firstNode;    //Start with the first loop
   
      try
     {
        while (p2 != null)     //If p2 reaches end of linked list, no cycle exists
        {
            p1=p1.next;   //Move to next
            p2=p2.next.next; //Move to 2 steps next
            if(p1==p2)
               return true;     //p1 and p2 met, so this means that there is a cycle
        }
      }
      catch(NullPointerException npe)
      {
          //This means that p2 could not move forward
          return false;
      }

      return false;
  }

How to reverse a singly linked list in Java ?

Sometimes the solutions are not quite obvious. Search for an algorithm to reverse a singly linked list using Java and you wont find any good hits except for this code.

public void reverse()
{
   Node currentNode, nextNode, loopNode;
   if(first==null)
      return;

   currentNode=first;
   nextNode= first.next;
   loopNode=null;


   while(nextNode != null)
   {
        currentNode.next = loopNode;
        loopNode= currentNode;
        currentNode=nextNode;
        nextNode =nextNode.next;
   }

   first = currentNode;
   first.next = loopNode;

}

This might not be a very intuitive solution at first sight but infact this is a very clever simulation of C/C++ pointers in Java. Credit goes to my wife for this fascinating algorithm.

Another version of this algorithm can be found here. This is a much improved and efficient way of doing this.

Technorati tags: Programming, Java, Data structures