Things must know about java collection API - Part I

Overview:-

I tried to study the collections API as much as I can, in general it is good advice for any programming language/platform to invest some time, and learn the basics of collection API

The Collections Framework

The collections framework is a unified architecture for representing and manipulating collections, enabling them to be manipulated independently of the details of their representation. It reduces programming effort while increasing performance. It enables interoperability among unrelated APIs, reduces effort in designing and learning new APIs, and fosters software reuse. The framework is based on more than a dozen collection interfaces. It includes implementations of these interfaces and algorithms to manipulate them.

The designing of these collection based on factors like immutability,Cloneable,Serializable,iterable, duplicate element  support

Some of the benefits of collections framework are;

·         Reduced development effort by using core collection classes rather than implementing our own collection classes.

·         Code quality is enhanced with the use of well tested collections framework classes.

·         Reduced effort for code maintenance by using collection classes shipped with JDK.

·         Reusability and Interoperability

Java 1.5 came with Generics and all collection interfaces and implementations use it heavily. Generics allow us to provide the type of Object that a collection can contain, so if you try to add any element of other type it throws compile time error.

This avoids ClassCastException at Runtime because you will get the error at compilation. Also Generics make code clean since we don’t need to use casting and instanceof operator.

All collection classes of java store memory location of the objects they collect. The primitive values do not fit in to the same definition.

To circumvent this problem, JDK5 and onwards have autoboxing - wherein the primitives are converted to appropriate objects and back when they are added or read from the collections.

1. Collection Name	Interface java.util.Collection
Implementation Of	extends Iterable<E>
Is Ordered	Depends on Subtypes
Is Resizable	Depends on Subtype
Is Thread Safe	Depends on Subtypes.  ConcurrentModificationException is thrown when multiple treat tries to modify the collection. So you can try  Collections.synchronizedXXX(collection);
Duplicate allowed	Depends on Subtypes
Null allowed	Depends on Subtypes
Iterate Logic	extends Iterable<E>
More info	ü  The root interface in the collection hierarchy. ü  Though you do not instantiate a Collection directly, but rather a subtype of Collection, you may often treat these subtypes uniformly as a Collection Bags or multisets (unordered collections that may contain duplicate elements) should implement this interface directly. ü  Almost all collections in Java are derived from the java.util.Collection interface. Collection defines the basic parts of all collections. The interface states the add() and remove() methods for adding to and removing from a collection respectively. Also required is the toArray() method, which converts the collection into a simple array of all the elements in the collection. Finally, the contains() method checks if a specified element is in the collection. ü  The Collection interface is a subinterface of java.lang.Iterable, so any Collection may be the target of a for-each statement. ü  Collection is a generic. Any collection can be written to store any class. For example, Collection<String> can hold strings, and the elements from the collection can be used as strings without any casting required. ü  You can create your own collection by implementing this interface ü  public class MyCollection<E> implements java.util.Collection<E>{} ü  boolean addAll(Collection<? extends E> coll)  this method design in such way that , when you add item to your collection you want to be sure that they do have a certain type so, for any collection containing elements of type E , addAll must be able to deal with input collections not just of E, but all of its subclasses as well. Hence <? extends E> but  remove(Object o)  For removal, the limits need not be so strictly set, and there is no harm in trying to remove elements of a collection of some totally unrelated type.

import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Map; public class HowToCheckCollectionType {                 /**                  * @param args                  */                 public static void main(String[] args) {                                 // TODO Auto-generated method stub                                 Collection col = new ArrayList<String>();                                 // Check weather object is of type collection                                 System.out.println("is col object is of type Collection = "                                                                 + isCollection(col));                                 // Check if class it of type collection                                 System.out.println("is col class is of Collection = "                                                                 + isClassCollection(col.getClass()));                                 Map map = new HashMap<String, String>();                                 // Check weather object is of type collection                                 System.out.println("is map object is of type Collection = "                                                                 + isCollection(map));                                 // Check if class it of type collection                                 System.out.println("is map class is of Collection = "                                                                 + isClassCollection(map.getClass()));                 }                 public static boolean isCollection(Object ob) {                                 return ob instanceof Collection;                 }                 public static boolean isClassCollection(Class c) {                                 return Collection.class.isAssignableFrom(c);                 } }

O/P is col object is of type Collection = true is col class is of Collection = true is map object is of type Collection = false is map class is of Collection = false

2. Collection Name	Class  java.util.Collections
Implementation Of	Object class as no parent
Is Ordered	Provide sort(), reverse() ,reverseOrder() for List
Is Resizable	NA
Is Thread Safe	Provide method likes synchronizedList / synchronizedMap/synchronizedSet to get the respective synchronized collection
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	Provide method  to get Iterator<E> iterator(), listIterator()
More info	ü  This class consists exclusively of static utility methods that operate on or return collections. ü  It contains polymorphic algorithms that operate on collections, “wrappers”, which return a new collection backed by a specified collection, and a few other odds and ends. ü  This class contains methods for collection framework algorithms, such as binary search, sorting, shuffling, reverse etc. ü  The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. ü  Java manual for binarySearch: Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; public class CollectionsDemo {             public static void main(String[] args) {             // create an array of string objs             String init[] = { "One", "Two", "Three", "Four", "Five", "Three" };             // create one list             List list = new ArrayList(Arrays.asList(init));             System.out.println("List value before: " + list);             // sort the list             Collections.sort(list);             System.out.println("List value after sort: " + list);             // binarySearch             System.out.println("after sort Four is at index = "                         + Collections.binarySearch(list, "Four"));             // unmodifiable Collection             Collection coll = Collections.unmodifiableCollection(list);             try {                   coll.add("Six");             } catch (UnsupportedOperationException e) {                   System.out.println("Can not modify collection");             }             // Convert Set into sorted list             Set set = new HashSet();             set.add("C");             set.add("B");             set.add("A");             ArrayList newList = new ArrayList<String>(set);             Collections.sort(newList);             System.out.println("Sorted newList = " + newList);             // Create the list with repeterd object             List<String> repeatedList = Collections.nCopies(10, "RepeatedElement");             System.out.println("ncopies list = "+repeatedList);       } }

O/P List value before: [One, Two, Three, Four, Five, Three] List value after sort: [Five, Four, One, Three, Three, Two] after sort Four is at index = 1 Can not modify collection Sorted newList = [A, B, C] ncopies list = [RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement, RepeatedElement]

3. Collection Name	abstract class AbstractCollection<E>
Implementation Of	Collections<E>
Is Ordered	NA
Is Resizable	NA
Is Thread Safe	NA
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	abstract Iterator<E> iterator();
Complexity	NA
More info	ü  This class provides a skeletal implementation [skeletal implementation meaning an abstract class implementing the particular interface.] of the Collection interface, to minimize the effort required to implement this interface by implementing below methods ·         isEmpty() ·         contains() ·         toArray() ·         addAll() ·         removeAll() ü  To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. ü  It does not override the equals() because both AbstractList and AbstractSet extend AbstractCollection, and they have different behaviors for their equals() methods, specified by the interfaces List and Set so in this way AbstractCollection avoids adding semantic constraints on potential subclasses. ü  It also not implemented size() to avoid its default implementation and gave a chance to subclass to design it accordingly ü  The AbstractCollection does not know of how the data is stored, so  they they kept  iterator() as abstract like ArrayList and HashSet has different implementation

4. Collection Name	Interface List<E>
Implementation Of	Collection<E>, Iterable<E>
Is Ordered	Yes
Is Resizable	Yes
Is Thread Safe	By default Yes. Depends on Subtypes
Duplicate allowed	By default Yes. Depends on Subtypes
Null allowed	By default Yes (More than one)
Iterate Logic	The user can access elements by their integer index .The List interface provides a special   iterator, called a ListIterator . these are the few  std  method provided by this interface ·         int size(); ·         isEmpty() ·         contains(Object o); ·         iterator(); ·         toArray(); ·         add(E e); ·         remove(Object o); ·         addAll(Collection<? extends E> c); ·         removeAll(Collection<?> c); It allow you to add any type of object so still no generics used in contains(Object o)/ remove(Object o) ..

5. Collection Name	Abstract class AbstractList<E>
Implementation Of	extends AbstractCollection<E> implements List<E>
Is Ordered	Yes
Is Resizable	Depends on subclass
Is Thread Safe	Depends on subclass
Duplicate allowed	Depends on subclass
Null allowed	Depends on subclass
Iterate Logic	Implemented by this class
More Info	ü  This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "random access" data store (such as an array) ü  Need to implement  1) get(int index)  2) size() ü  Unlike the other abstract collection implementations, the programmer does not have to provide an iterator implementation; the iterator and list iterator are implemented by this class, on top of the "random access" methods: get(int), set(int, E), add(int, E) and remove(int). ü  For sequential access data (such as a linked list), AbstractSequentialList should be used in preference to this class. ü  To implement a modifiable list, the programmer must additionally override the set(int, E) method (which otherwise throws an UnsupportedOperationException). ü  If the list is variable-size the programmer must additionally override the add(int, E) and remove(int) methods.

6. Collection Name	Class ArrayList<E>
Implementation Of	implements List<E>, RandomAccess, Cloneable, Serializable
Is Ordered	Yes
Is Resizable	Yes
Is Thread Safe	No. This implementation is not synchronized.
Duplicate allowed	By default Yes.
Null allowed	Yes
Iterate Logic	The user can access elements by their integer index .The List interface provides a special   iterator, called a ListIterator
Complexity	Adding n elements requires O(n) time.
More info	ü  Internally an ArrayList uses an Object[]. As you add items to an ArrayList, the list checks to see if the backing array has room left. If there is room, the new item is just added at the next empty space. If there is not room, a new, larger, array is created, and the old array is copied into the new one. Now, there is more room left, and the new element is added in the next empty space. ü  Constructs an empty list with an initial capacity of ten. ü  trimToSize() Trims the capacity of this ArrayList instance to be the list's current size.  An application can use this operation to minimize the storage of an ArrayList instance. ü  ensureCapacity() Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument. ü  For Equal check it uses (o==null ? e==null : o.equals(e)). ü  toArray(T[] a) Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list. ü  If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.) ü  ArrayList implements List with a dynamically resizing array. ü  Does not implements Comparable interface ü  allow fast random read access, But adding or removing from anywhere is expensive ü  adding more elements than the capacity of the underlying array, a new array (50% of the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average ü  So ArrayLists are good for write-once-read-many or appenders, but bad at add/remove from the front or middle. ü  The capacity of an ArrayList is effectively an implementation detail - it controls when the backing array needs to be replaced by a larger one to cope with more elements. The size of a list is the important part here - a list with capacity 100 but size 5 is still only a list of 5 elements, and so inserting at position 67 into such a list would make no sense. ü  Throws: ü  IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())

package com.study.collection; import java.util.ArrayList; import java.util.Iterator; public class ArrayListDemo {        /**         * @param args         */        public static void main(String[] args) {                             ArrayList<String> arrayList = new ArrayList<String>();               for(int i = 0; i < 10; i ++){                      arrayList.add("Data");                      arrayList.add(null);                                    }               Iterator<String> iter = arrayList.iterator();               while(iter.hasNext()){                      System.out.println("Using iterator " + iter.next());               }                             for(String s : arrayList){                      System.out.println("Using For loop "+ s);               }                      } }

7. Collection Name	abstract class AbstractSequentialList<E>
Implementation Of	AbstractList<E>
Is Ordered	sequential access
Is Resizable	NA
Is Thread Safe	NA
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	public abstract ListIterator<E> listIterator(int index); Depends on subclass
Complexity	NA
More info	ü  AbstractSequentialList is generic ü  This class provides a skeletal implementation of the List interface . ü  This collection is backed by a "sequential access" data store (such as a linked list).  For random access data (such as an array),AbstractList should be used in preference to this class. ü  To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. ü  To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. ü  For a modifiable list the programmer should additionally implement the list iterator's set method. For a variable-size list the programmer should additionally implement the list iterator's remove and add methods.

8. Collection Name	Inter face ListIterator<E>
Implementation Of	Iterator<E>
Is Ordered	NA
Is Resizable	NA
Is Thread Safe	NA
Duplicate allowed	NA
Null allowed	NA
Iterate Logic	NA
Complexity
More info	ü  An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list ü  ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). ü  How it is different from the Iterator? 1)      We can use Iterator to traverse Set and List and also Map type of Objects, but List Iterator can be used to traverse for List type Objects, but not for Set type of Objects. 2)      By using Iterator we can retrieve the elements from Collection Object in forward direction only. 3)        ü  Has below method declare hasPrevious() nextIndex() hasNext() hasPrevious()

 Continue reading.....Things must know about java collection API - Part II (coming soon)