Things must know about java collection API - Part V

31. Collection Name	Interface java.util.Queue
Implementation Of	extends Collection<E>
Is Ordered	Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	Depends on subclass
Complexity
More info	ü  Queues provide additional insertion, extraction, and inspection operations ü  The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues. ü  The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null. ü  The element() and peek() methods return, but do not remove, the head of the queue. ü  The Queue interface does not define the blocking queue methods, which are common in concurrent programming. These methods, which wait for elements to appear or for space to become available, are defined in the BlockingQueue interface, which extends this interface.                                                 ü  Below are the implementer classes   AbstractQueue, ArrayBlockingQueue, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingQueue, LinkedList, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

32. Collection Name	abstract class java.util. AbstractQueue
Implementation Of	AbstractCollection<E> implements Queue<E>
Is Ordered	Depends on subtypes
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	Depends on subtypes
Null allowed	No
Iterate Logic	Iterator<E>  iterator()
Complexity	NA
More info	ü  This class provides skeletal implementations of some Queue operations. ü  The implementations in this class are appropriate when the base implementation does not allow null elements. ü  Methods add, remove, and element are based on offer, poll, and peek, respectively, but throw exceptions instead of indicating failure via false or null returns. ü  A Queue implementation that extends this class must minimally define a method Queue.offer(E) ü  Which does not permit insertion of null elements, along with methods Queue.peek(), Queue.poll(), Collection.size(), and Collection.iterator(). Typically, additional methods will be overridden as well. If these requirements cannot be met, consider instead subclassing AbstractCollection.

33. Collection Name	Interface java.util.Deque
Implementation Of	Queue<E>
Is Ordered	Deques can also be used as Stack LIFO  or Queue FIFO
Is Resizable	This interface supports capacity-restricted deques as well as those with no fixed size limit.
Is Thread Safe	No
Duplicate allowed	Yes
Null allowed	A typical deque does not allow null to be inserted as its element, while some implementations allow it. But null should not be inserted even in these implementations, since method poll return null to indicate that there is no element left in the deque.
Iterate Logic	Does not provide support for indexed access to elements.
Complexity	In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n). In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
More info	ü  A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck".  ü  Methods are provided to insert, remove, and examine the element. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). ü  When a deque is used as a queue, FIFO (First-In-First-Out) behavior results. equivalent to Deque methods for Queue Queue Method Equivalent Deque Method add(e) addLast(e) offer(e) offerLast(e) remove() removeFirst() poll() pollFirst() element() getFirst() peek() peekFirst() ü  Elements are added at the end of the deque and removed from the beginning ü  When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. Equivalent to Deque methods for Stack Stack Method Equivalent Deque Method push(e) addFirst(e) pop() removeFirst() peek() peekFirst()

34. Collection Name	java.util.ArrayDeque
Implementation Of	extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
Is Ordered	Insertion order
Is Resizable	Array deques have no capacity restrictions; they grow as necessary to support usage.
Is Thread Safe	No
Duplicate allowed	Yes
Null allowed	No
Iterate Logic	Iterator<E>  iterator()
Complexity	ArrayDeque has amortized constant time (O(1)) adding/deletion of elements at both the front and back of the containe.
More info	ü  Resizable-array implementation of the Deque interface ü  This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. ü  ArrayDeque does not allow you to specifically remove an element at a certain position in the container. The various remove, removeFirst, and removeLast methods of the class allow you a slightly more limited element removal. ü  ArrayDeque comes with methods for using the class like a queue (peek, poll, add, addFirst) and like a stack (offer, push, pop, peekLast, addLast), or like both (hence why it is a Double-Ended Queue). ü  ArrayDeque has no support for adding elements into the middle of the deque.

package com.study.collection; import java.util.ArrayDeque; import java.util.Iterator; public class ArrayDequeDemo {       public static void main(String[] args) {             ArrayDeque<String> arrrayDeque = new ArrayDeque<String>();             arrrayDeque.add("A");             arrrayDeque.add("B");             arrrayDeque.add("C");             arrrayDeque.add("K");             arrrayDeque.add("L");             // offerFirst-adds elements at the front of the ArrayDeque             arrrayDeque.offerFirst("D");             // offerLast inserts the element at the last of ArrayDeque             arrrayDeque.offerLast("E");             Iterator<String> itr = arrrayDeque.iterator();             while (itr.hasNext()) {                   System.out.print(itr.next());                   System.out.print("-");             }                         System.out.println("\n" + "--Descending Order--------");             Iterator<String> itr2 = arrrayDeque.descendingIterator();             while (itr2.hasNext()) {                   System.out.print(itr2.next());                   System.out.print("-");             }       } } O/P D-A-B-C-K-L-E- --Descending Order-------- E-L-K-C-B-A-D-

35. Collection Name	Class  java.util.PriorityQueue
Implementation Of	extends AbstractQueue<E> implements java.io.Serializable
Is Ordered	The element of the priority queue is ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	Yes
Null allowed	No. Does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
Iterate Logic	Its iterator implements all of the optional methods of the Collection and Iterator interfaces.
Complexity	O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
More info	An unbounded priority queue based on a priority heap The head of this queue is the least element with respect to the specified ordering. DEFAULT_INITIAL_CAPACITY = 11 A PriorityQueue is a sorted collection. So the elements you add to them must be comparable with each other. Either they must implement Comparable (or the queue sorts them using the natural ordering implied by the compareTo method), or you must provide a Comparator when creating the Queue itself (and the queue will use this comparator to compare objects and sort them). If you don't do any of these, the queue has no way to decide if the first element has a bigger priority than the second one.

36. Collection Name	Class  java.util.PriorityQueue
Implementation Of	extends AbstractQueue<E> implements java.io.Serializable
Is Ordered	The element of the priority queue is ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	Yes
Null allowed	No. Does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
Iterate Logic	Its iterator implements all of the optional methods of the Collection and Iterator interfaces.
Complexity	O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
More info	ü  An unbounded priority queue based on a priority heap ü  The head of this queue is the least element with respect to the specified ordering. ü  DEFAULT_INITIAL_CAPACITY = 11 ü  A PriorityQueue is a sorted collection. So the elements you add to them must be comparable with each other. Either they must implement Comparable (or the queue sorts them using the natural ordering implied by the compareTo method), or you must provide a Comparator when creating the Queue itself (and the queue will use this comparator to compare objects and sort them). ü  If you don't do any of these, the queue has no way to decide if the first element has a bigger priority than the second one.

import java.util.Iterator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Random; public class PriorityQueueDemo {       /**        * @param args        */       public static void main(String[] args) {             Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);             Random rand = new Random();             //No Comparator so element follow the order of insertion             for (int i = 0; i < 7; i++) {                   integerPriorityQueue.add(new Integer(rand.nextInt(100)));             }             //IntegerPriorityQueue.add(null); Not allowed             //Poll Retrieves and removes the head of this queue,             //or returns null if this queue is empty.             //Polling 3 element             System.out.println("Original IntegerPriorityQueue is = "             + integerPriorityQueue);             for (int i = 0; i < 3; i++) {                   Integer in = integerPriorityQueue.poll();                   System.out.println("polling Integer:" + in);             }             System.out.println("IntegerPriorityQueue becomes " +                         "[No assurance of order] = " + integerPriorityQueue);             //Peek Retrieves, but does not remove, the head of this queue,             //or returns null if this queue is empty.             System.out.println("The head of this queue is = "+             integerPriorityQueue.peek());             System.out.println("integerPriorityQueue size " +             integerPriorityQueue.size());                         Queue<Student> studentPriorityQueue = new PriorityQueue<Student>(3);             Student s1 = new Student();             Student s2 = new Student();             Student s3 = new Student();             s1.setId(1);             s3.setId(3);             s2.setId(2);                         studentPriorityQueue.add(s1);             studentPriorityQueue.add(s2);             studentPriorityQueue.add(s3);                         Iterator<Student> iter = studentPriorityQueue.iterator();             System.out.println("studentPriorityQueue maintain the order" +                         " according to priority.......");             while(iter.hasNext()){                   System.out.println("Student id " + ((Student)iter.next()).getId());             }                   } }  class Student implements Comparable<Student> {               private int id;       private String name;                   public int getId() {             return id;       }       public void setId(int id) {             this.id = id;       }       public String getName() {             return name;       }       public void setName(String name) {             this.name = name;       }             @Override       public int compareTo(Student s1) {             // TODO Auto-generated method stub             return Integer.compare(this.id ,s1.id );       }  } O/P Original IntegerPriorityQueue is = [3, 53, 27, 80, 60, 71, 42] polling Integer:3 polling Integer:27 polling Integer:42 IntegerPriorityQueue becomes [No assurance of order] = [53, 60, 71, 80] The head of this queue is = 53 integerPriorityQueue size 4 studentPriorityQueue maintain the order according to priority....... Student id 1 Student id 2 Student id 3

37. Collection Name	Class  java.util.Arrays
Implementation Of	NA
Is Ordered	NA
Is Resizable	NA
Is Thread Safe	NA
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	NA
Complexity	NA
More info	ü  This is a Utility class [It's usually a class which only has static methods, Static methods belong to the class and do not require an instance of the class in order to be called. Instead they are called with the class name as a prefix.] ü  This class contains various methods for manipulating arrays (such as sorting and searching). ü  This class also contains a static factory /methods that allow arrays to be viewed as lists. ü  It provide sort() and binary search for all primitive data types in java ü  Two arrays are equal if they contain the same elements in the same order. So it is clear that this is going to be an O(n) operation as it will need to loop over all the items (at least if they are all equal). The default equals (i.e. Object#equals) is an O(1) operation, it is a simple reference comparison ü  copyOfRange()  Copies the specified range of the specified array into a new array.  ü  Few common method available with this class ·         binarySearch = Searches the specified array of particular data type  for the specified value using the binary search algorithm. ·         copyOf = Copies the specified array, truncating or padding with zeros (if necessary) so the copy has the specified length. ·         copyOfRange = Copies the specified range of the specified array into a new array. ·         deepEquals = Returns true if the two specified arrays are deeply equal to one another. ·         equals= returns true if the two specified arrays of particular data type  are equal to one another. ·         fill = Assigns the specified type value to each element of the specified array. ·         sort = Sorts the specified array into ascending numerical order/Natural order.

package com.study.collection; import java.util.Arrays; public class ArrayDemo {       public char[] mainArray = { 'a', 'b', 'c', 'c', 'e', 'f', 'g', 'h' };       public char[] getArray() {             return this.mainArray;       }       public static void main(String[] args) {             ArrayDemo arrayDemo = new ArrayDemo();             // array comparison             char[] first = arrayDemo.getArray().clone();             char[] second = arrayDemo.getArray();             char[] third = { 'a', 'b', 'k', 'c', 'e', 'f', 'g', 'h' };             if (Arrays.equals(first, second)) {                   System.out.println("first,second are equals");             }else{                   System.out.println("first,second are not equals");             }                               if (Arrays.equals(first, third)) {                   System.out.println("first,third  are equals");             }else{                   System.out.println("first,third are not equals");             }             // Arrays print             System.out.println("Print array =" + Arrays.toString(first));             // Search             System.out.println("Found element e at Position = "                         + Arrays.binarySearch(first, 'e'));             String[][] ticTacToe1 = { { "O", "O", "#" }, { "O", "#", "#" },                         { "#", "O", "#" } };             String[][] ticTacToe2 = { { "O", "O", "#" }, { "O", "#", "#" },                         { "#", "O", "#" } };             if (Arrays.deepEquals(ticTacToe1, ticTacToe2)) {                   System.out.println("Boards 1 and 2 are equal.");             } else {                   System.out.println("Boards 1 and 2 are not equal.");             }             // Fill the array with char             Arrays.fill(first, 'z');             System.out.println("After fill the array = " + Arrays.toString(first));             // Sort the array             Arrays.sort(third);             System.out.println("After sorting third array = " + Arrays.toString(third));       } } O/P first,second are equals first,third are not equals Print array =[a, b, c, c, e, f, g, h] Found element e at Position = 4 Boards 1 and 2 are equal. After fill the array = [z, z, z, z, z, z, z, z] After sorting third array = [a, b, c, e, f, g, h, k]

38. Collection Name	Abstract Class  java.util.Dictionary
Implementation Of	NA
Is Ordered	NO
Is Resizable	Yes
Is Thread Safe	NO
Duplicate allowed	Key cannot be duplicate
Null allowed	Neither the key nor the value can be null.
Iterate Logic	The general contract for the elements method is that an Enumeration is returned that will generate all the elements contained in entries in this dictionary. abstract public Enumeration<V> elements();
Complexity	NA
More info	ü  The Dictionary class is the abstract parent of any class, such as Hashtable, which maps keys to values. ü  Every key and every value is an object ü  Any non-null object can be used as a key and as a value. ü  As a rule, the equals method should be used by implementations of this class to decide if two keys are the same. ü  Dictionary formed the base for the now obsolete Hashtable.