Java 6 - ArrayDeque

Java programmers are getting rich day by day (as the new versions and other frameworks come into existence), as the Java Collections Framework is hosting a lot of different datastructures and algorithm implementations. The latest one I came across is 'ArrayDeque' from Java version 6.

ArrayDeque is an implementation of the 'Deque' interface, which is a short form for "Double Ended Queue's". Double Ended Queue's extend 'Queue' and support adding and removing elements from both ends. In a Queue, you can add from one end and remove from the other. Also, Deque's can be used as a Queue and also a 'Stack'. ArrayDeque has no capacity restrictions like some other data structures (although you can specify that in one of its constructors). ArrayDeque is not threadsafe, as other collections like HashMap, et al. If you want it thread-safe, use 'LinkedBlockingQueue', which implements the 'BlockingQueue' interface, which further extends from 'Deque' interface.

A 'Deque' can be traversed from both directions programmatically using 'iterator' and 'descendingIterator' methods. Deque is doubly linked and can be compared to 'LinkedList', which also implements a 'Deque', apart from List. In LinkedList, you can access an element randomly, by the element's index, which you cant do in Deque's. It was designed this way to make it more efficient.

This kind of datastructure, which can be operated as a 'Queue', 'Stack' and can be traversed from both ends, is pretty useful in certain scenarios. A couple of 'backtracking' and other useful algorithms can be easily implemented with this kind of 'off-the-shelf' datastructures available from the 'Java Collection Framweork'.

A couple of months/years back, I had to code my own implementation to implement some algorithms. Ofcourse, its fun and a learning experience, but with ready-made stuff like this, it saves some time for a Java developer. And ofcourse, its better and useful for any developer to know the implementation 'behind-the-scenes'. By the way, Java is getting more abstract day by day (more high-level) with all these implementations and frameworks popping up from everywhere.

Below is a trivial Java program, for testing/demonstrating the new 'ArrayDeque' class from 'Java 6 Collections Framework':

import java.util.ArrayDeque;
import java.util.Iterator;

public class ArrayDequeTest
{
public static void main(String[] args) 
{    
ArrayDeque arrDeque = new ArrayDeque();

arrDeque.add("mercedes");
arrDeque.add("porsche");
arrDeque.add("audi");

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();

arrDeque.addLast("bmw");
arrDeque.add("PORSCHE");
arrDeque.addLast("Ferrari");

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();

for(Iterator descendingIter = arrDeque.descendingIterator();descendingIter.hasNext();) {
System.out.println(descendingIter.next());
}

System.out.println();
System.out.println("First Element : " + arrDeque.getFirst());
System.out.println("Last Element : " + arrDeque.getLast());
System.out.println("Contains \"porsche\" : " + arrDeque.contains("porsche"));

arrDeque.addFirst("porsche");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

arrDeque.removeLastOccurrence("porsche");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

arrDeque.removeFirstOccurrence("porsche");
System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();
System.out.println("Popped Element : " + arrDeque.pop());

arrDeque.push("porsche");        
System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Size of Array Deck : " + arrDeque.size());

System.out.println("\n Peek : " + arrDeque.peek());

System.out.println("\n Peek First : " + arrDeque.peekFirst());
System.out.println("\n Peek Last : " + arrDeque.peekLast());

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Poll First : " + arrDeque.pollFirst());
System.out.println("\n Poll Last : " + arrDeque.pollLast());

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Poll : " + arrDeque.poll());

System.out.println("\n Peek First : " + arrDeque.peekFirst());
System.out.println("\n Peek Last : " + arrDeque.peekLast());

arrDeque.offerFirst("porsche");
arrDeque.offerLast("what the heck?");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Get First : " + arrDeque.getFirst());
System.out.println("\n Get Last : " + arrDeque.getLast());

System.out.println("\n Element : " + arrDeque.element());

Object[] objArray = arrDeque.toArray();
System.out.println("\n Object Array Size : " + objArray.length);

String[] strArray = (String[]) arrDeque.toArray(new String[0]);
System.out.println("\n String Array Size : " + strArray.length);

ArrayDeque arrDequeClone = arrDeque.clone();
System.out.println("Clone Size : " + arrDequeClone.size());

System.out.println("arrDeque == arrDequeClone : " + (arrDeque == arrDequeClone));

System.out.println("arrDeque.equals(arrDequeClone) : " + arrDeque.equals(arrDequeClone));
}
}



For more info, check the docs from Sun's website. I'll post some more info, if I happen to spend some more time and implement an algorithm or any other imp stuff, using this datastructure.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.