Friday, July 29, 2011

Java Collections - A Relative Study

Collection refers to a group of multiple elements kept together to do a specific task of choice. A collection can be of same or different types as per the need but it could be relational. Collection is used to store, retrieve, manipulate and communicate aggregated data. Collections are used to ease our need of implementation of new data structure which has required functionality by reducing our programming effort and also reduces the complexity in terms of space and time by increasing the program speed and quality.


Core Collection Interfaces 

Collection          |         Set          |         List          |         Queue          |         Map

  • Collection - it is the basic root of the collection hierarchy. We doesn't have any direct implementation of this interface but there is more specific sub interfaces, such as Set and List.
  • Set - it cannot contains duplicate. It signifies the mathematical abstraction of set theory, like wise you can add the same element many times but you will see it only once when you iterates the collection. Implemented by HashSet and TreeSet.
  • List - its a kind of sequence, a ordered collection. It can have duplicate elements. It is useful in the terms like positional access, search, iteration and range view. Implemented by ArrayList and Linked List.
  • Map - a object that maps keys to values. A Map cannot contain duplicate keys; each key can map to at most one value. It models the mathematical function abstraction. Implemented by HashMap, TreeMap and LinkedHashMap
  • Queue - is a special collection used to hold multiple elements prior to processing. Queue provides additional insertion, extraction and inspection operations.
    Implementation of Collection Classes with source codes

    1.) ArrayList - Can expand automatically, access to any element O(1), insertions and deletions O(N), have methods for inserting, deleting and searching, can be traversed using foreach loop, iterators or indexes.

    Code Snippet:

    package questions;
    
    import java.util.*;
    /**
     * @author Bharat Verma
     */
    public class ArrayListDemo
    {
            public static void printArrayList (ArrayList p_arraylist)
            {
                    System.out.println("------------------------------------------");
                    System.out.println("Content of ArrayList : "+p_arraylist);
                    System.out.println("Size of ArrayList = "+p_arraylist.size());
                    System.out.println("------------------------------------------");
            }
            public static void main(String[] args)
            {
                    ArrayList<Object> sampleArrayList =new ArrayList<Object>(); // you can specify the object type
    
                    Integer intr = new Integer(729);
                    String str ="Bharat";
                    double dtr = 169.721;
    
                    printArrayList(sampleArrayList);
    
                    sampleArrayList.add(intr);
                    sampleArrayList.add(str);
                    sampleArrayList.add(dtr);
                    printArrayList(sampleArrayList);
    
                    Integer i5=new Integer(50);
                    sampleArrayList.add(3, i5); // using add(int index, object obj)
                    printArrayList(sampleArrayList);
    
                    sampleArrayList.remove(3); // using remove()
                    printArrayList(sampleArrayList);
    
                    Object a=sampleArrayList.clone(); // using clone
    
                    System.out.println("The clone is: " + a);
    
                    printArrayList(sampleArrayList);
    
                    System.out.println(sampleArrayList.contains("Bharat")); // True as it contains
    
                    // iteration using iterator
                    Iterator iter = sampleArrayList.iterator();
                    System.out.println("Using Iterator");
                    while (iter.hasNext())
                    {
                            System.out.println(iter.next());
                    }
    
                    // using for loop and indexes 
                    System.out.println("Using for loop and index");
                    for (int i=0; i<sampleArrayList.size(); i++)
                    {
                            System.out.println(sampleArrayList.get(i));
                    }
            }
    }
    

    2.) Vector - initially it was commonly used in place of arrays just because of their expansion property. The main difference between ArrayList and Vector is the synchronization, ArrayLists are fast as they are unsynchronized as compared to Vectors but less secure in multithreaded environment. Vector can hold objects but not primitive data types (for that wrapper classes is used which is immutable).

    Code Snippet:
    package questions;
    import java.util.*;
    /**
     * @author Bharat Verma
     */
    public class VectorDemo
    {
            public static void printVector (Vector p_vector)
            {
                    System.out.println("------------------------------------------");
                    System.out.println("Content of Vector : "+p_vector);
                    System.out.println("Size of Vector = "+p_vector.size());
                    System.out.println("------------------------------------------");
            }
            public static void main(String[] args)
            {
                    Vector<Object> vector = new Vector<Object>();
                    int primitiveType = 10;
                    Integer wrapperType = new Integer(20);
                    String str = "Bharat Verma";
    
                    vector.add(primitiveType);
                    vector.add(wrapperType);
                    vector.add(str);
                    vector.add(2, new Integer(30));
    
                    printVector(vector);
    
                    System.out.println("The elements at position 2 is: "
                                    + vector.elementAt(2));
                    System.out.println("The first element of vector is: "
                                    + vector.firstElement());
                    System.out.println("The last element of vector is: "
                                    + vector.lastElement());
    
                    vector.removeElementAt(2);
    
                    vector.add(1 , new Integer(10));
                    vector.add(3 , new Integer(10));
                    System.out.println("The last index of 10 : "
                                    + vector.lastIndexOf(10));
    
                    Enumeration e=vector.elements();
                    printVector(vector);
                    while(e.hasMoreElements())
                    {
                            System.out.println("The elements are: " + e.nextElement());
                    }
            }
    }  

    3.) Linked List - it provides insertion of all the elements including NULL. It can be used for implementation of various other associated data structures like Arrays and Queues.

    Code Snippet:
    package questions;
    import java.util.*;
    /**
     * @author Bharat Verma
     */
    public class LinkedListDemo
    {
            public static void printLinkedList (LinkedList p_ll)
            {
                    System.out.println("------------------------------------------");
                    System.out.println("Content of LinkedList : "+p_ll);
                    System.out.println("Size of LinkedList = "+p_ll.size());
                    System.out.println("------------------------------------------");
            }
            public static void main(String[] args)
            {
                    LinkedList link=new LinkedList();
                    link.add("a");
                    link.add("b");
                    link.add(new Integer(10));
    
                    printLinkedList(link);
    
                    link.offerFirst(new Integer(20));
                    printLinkedList(link);
    
                    link.addLast("c");
                    printLinkedList(link);
    
                    link.add(2,"j");
                    printLinkedList(link);
    
                    link.add(1,"t");
                    printLinkedList(link);
                    System.out.println("The Last element : "+link.getLast());
    
                    link.offerLast(new Integer(123));
                    printLinkedList(link);
    
                    link.remove(3);
                    printLinkedList(link);
    
                    System.out.println("The First element : "+link.element());
            }
    }
    

    4.) HashTable -  Hash table similar to HashMap but is synchronized and comes with its cost, only a single thread can accesss it.
    Hash table does not allows NULL for either keys or values.
    Just like Hashmap you can add same or different values to one key but it will be overwrite them and will store only last one.
    Hash table stores only those objects which overrides the hashcode() and equals() methods defined by the Object Class.Fortunately many object comes with the built in implementation of it like String.

    Code Snippet:
    package collection;
    
    import java.util.Enumeration;
    import java.util.HashMap;
    import java.util.Hashtable;
    import java.util.Iterator;
    import java.util.Set;
    /**
     * @author Bharat Verma
     */
    public class HashTableDemo
    {
            public static void printHashTable (Hashtable hashtable)
            {
                    System.out.println("Retrieving all keys from the Hashtable");
                    Enumeration e = hashtable.keys();
    
                    while( e. hasMoreElements() )
                    {
                            System.out.println(e.nextElement());
                    }
                    System.out.println("Retrieving all values from the Hashtable");
    
                    e = hashtable.elements();
    
                    while(e. hasMoreElements())
                    {
                            System.out.println(e.nextElement());
                    }
            }
            public static void main(String[] args)
            {
                    // First Constructor
                    Hashtable<String, Integer> hashtable = new Hashtable<String, Integer>();
                    // 2nd with initial Capacity 
                    Hashtable ht2 = new Hashtable(5);
                    // 3rd with intial capacity and fill Ratio [0.0 - 1.0]
                    //default load factor is 0.75
                    Hashtable ht3 = new Hashtable(10, (float) 0.50);
                    // 4th with initialisation from a Map
                    Hashtable ht4 = new Hashtable (new HashMap());
    
                    hashtable.put("One", new Integer(1));
                    hashtable.put("Two", new Integer(2));
                    hashtable.put("Three", new Integer(3));
                    hashtable.put("Four", new Integer(4));
    
                    // Get the number of key value pairs
                    System.out.println("Hashtable contains " + hashtable.size() + " key value pairs.");
    
                    // Finding the Element using "Contains"
                    if( hashtable.contains(new Integer(1))){
                            System.out.println("Hashtable contains 1 as value");
                    }else{
                            System.out.println("Hashtable does not contain 1 as value");
                    }
                    // Finding the element using the key and "contains key"
                    if(hashtable.containsKey("One")){
                            System.out.println("Hashtable contains One as key");
                    }else{
                            System.out.println("Hashtable does not contain One as value");
                    }
                    // we need to have set-view to use iterators 
                    Set set = hashtable.keySet();
                    Iterator itr = set.iterator();
    
                    String str;
                    while(itr.hasNext())
                    {
                            str = (String) itr.next();
                            System.out.println(str + ": " +hashtable.get(str));
                    }
                    // String Representation of HashTable
                    System.out.println(hashtable.toString());
    
                    System.out.println( hashtable.remove("One") + " is removed from the Hashtable.");
            }
    
    }