With the release of Java 6, Sun Microsystems has added some new interfaces and their implementation to the existing java collection family.

Deque

BlockingDeque

NavigableMap

NavigableSet

ConcurrentNavigableMap

Deque

Deque is short for double-ended queue, and Sun Microsystem likes it to be pronounced as “deck” and not de-queue. Deque is a combination of both queue (that supports adding from one side and removing from the other side) and stack (that supports adding and removing from one single side). So it means that Deque can be used as a queue (FIFO) or as a stack (LIFO). It perfectly suites your “Why does not Sun Microsystems provides a collection class that work as a queue as well as a stack?” requirement.

Deque interface extends Queue interface added in Java 5. Classes that implements Deque interface in Java 6 are LinkedList, LinkedBlockingDeque, ArrayDeque. LinkedList has been re-written to implement Deque interface. Both LinkedList and ArrayDeque are not thread-safe.

If we compare LinkedList and ArrayDeque (both are unbound collections, that means they don’t have any fixed size limits), both are descendents of Deque but LinkedList at the same time also supports List that allows it to access element based on index. Now if we compare List with Deque, we will find that List support the notion of accessing the element contained in the list by index value that Deque does not support. Unlike Deque, List also allows us to insert or delete at any location within the list with a high performance cost. ArrayList has a higher cost for insert and delete operation as compared to ArrayDeque, as the portions of the array must be copied during these operations.

As a deque is a doubly linked, one can traverse through elements in both the directions, forward and backward. Deque provides iterators for both directions. You can use Iterator() to iterate through elements from front to back and use descendingIterator() to iterate through elements from back to front. Iterators returned by these implementation classes are fail-fast, that means if the deque is modified in any way except the remove of the Iterator after the creation of the Iterator it will throw a ConcurrentModificationException. The fail-fast behaviour is not guaranteed according to Sun Microsystems’ Java Document 6.0 but under most circumstances I have witnessed that it throws ConcurrentModificationException.

Any implementation of deque does not allow you to insert null elements because null is used as a return value by various deque methods indicating the collection is empty.

If one tries to do so, it will throw NullPointerException.

BlockingDeque

As earlier mentioned that Deque is not synchronized which makes it vulnerable in a shared environments. Java 6 provides BlockingDeque, a Deque that supports blocking operations that waits for the deque to become non-empty when retrieving an element, and waits for space to become available in the deque when storing an element. BlockingDeque is part of java.util.concurrent package that has changed the world of Java Multithreading and spared us from dealing with wait, notify and notifyAll methods. BlockingDeque does not allow null elements though it extends Deque.

BlockingDeque methods come in four forms, with different ways of handling operations that cannot be satisfied immediately, but may be satisfied at some point in

the future: one throws an exception, the second returns a special value (either null or false, depending on the operation), the third blocks the current thread indefinitely until the operation can succeed, and the fourth blocks for only a given maximum time limit before giving up

The Implementing class is LinkedBlockingDeque and the Iterator returned by Iterator() method is “weakly consistent” that means it does not provide fail – fast behaviour and will never throw ConcurrentModificationException and guarantees to traverse elements as they existed upon creation of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

NavigableMap and NavigableSet and ConcurrentNavigableMap.

According to JDK 6.0 Documentation, the definition of Navigable Map is “A SortedMap extended with navigation methods returning the closest matches for given search targets”. In the same way the definition of NaviagableSet is “A SortedSet extended with navigation methods reporting closest matches for given search targets”. Methods like lower, floor, ceiling, and higher return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, returning null if there is no such element in case of NavigableSet. Similarly, in case of NavigableMap methods like lowerEntry, floorEntry, ceilingEntry, and higherEntry return object of Map.Entry of keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning null if there is no such key. These methods are not designed for traversing entries but for locating entries.

NavigableMap come with three sets of methods. One set of methods retrieves submaps, another set works with the map entries, and last one works with the map keys. First set contains methods that returns all the keys upto the given key, but not including it. Other two methods in the first set returns all the entries between from key and to key, and entries from key to the end.

The next set of methods works with the keys of the map. Methods like firstKey(), lastKey(), ceiling Key(), floorKey(), higherKey(), lowerKey() are used to retrieve object of the key stored in the map. Correspondingly the methods return the first key, last key, the first key of the map greater than or equal to given key, the first key of the map less than or equal to the given key, the first key of the map strictly greater than the given key, the first key of the map strictly less than the given key.

The last set of methods returns a Map.Entry instance instead of a key from the Map instance. Like for the key, similar methods exists for entries in the map that returns the first entry, last key, the first entry of the map greater than or equal to given key, the first entry of the map less than or equal to the given key, the first entry of the map strictly greater than the given key, the first entry of the map strictly less than the given key. Two other NavigableMap methods worth mentioning are descendingKeySet() and descendingEntrySet(). The old TreeMap class has been re-written to extend from NavigableMap instead of SortedMap.

The implemented class of ConcurrentNavigableMap is ConcurrentSkipListMap that is a form of ordered linked list that maintains parallel lists for speeding up search time. The map is sorted according to the natural ordering ok its keys, but if you want your own sorting order then need to implement the Comparator interface and provide this implementation to the map at the time of creation. There are constructors available that takes the implementation of a Comparator as a parameter.

Insert, update, delete and access operations safely execute concurrently by multiple threads. The iterators provided by this implementation class are weakly consistent and not fail-fast that means keys or elements reflect the state of the map since the iterators ever created. In the absence of fail-fast behaviour, may modification to the map after the creation of the iterator does not throw ConcurrentModificationException and may proceed concurrently with other tasks.

Tags: ,