Java Collection Framework

Collection Framework:

An array = indexed collection + fixed number + homogeneous elements

Limitation of Arrays:

1. Arrays are of fixed size.
2. Arrays can hold only homogeneous data elements. However, this can be resolved using Object type arrays.
3. Not much of ready-made methods are available with arrays. This is because, Arrays are not built based on some data structure.

To overcome these issues, Sun introduced the Collections framework.

1. Collections are grow-able in nature dynamically.
2. Collections can hold both homogeneous and heterogeneous objects.
3. Lot of ready-made methods are available.

Disadvantage of Collections framework is performance.

Note:
Memory point of view, Collections are better.
Performance point of view, Arrays are better.

Meaning of Collection or Overall concept:

Group of individual objects going to be referred as a single entity is called Collection.

If we want to represent a group of individuals as a single entity then we should go for Collection.

'Collection' interface is considered as root Interface of Collection framework.

Collection is an interface.
Collections is a utility class in java.util package.

List (Interface) :

1. Duplicates are allowed.
2. Insertion order is preserved.

ArrayList, LinkedList, Vector and Stack are classes from List interface.

Set (Interface) :

1. Duplicates are not allowed
2. Insertion order is not preserved.

HashSet, LinkedHashSet are classes from Set Interface.

Set (I) --> SortedSet (I) --> NavigableSet (I) --> TreeSet (C)

If you want to represent a group of objects as key-value pairs, then we should go for Map.

Map (Interface) :

1. Key and Values are Objects only.
2. Key - should not be duplicate.
3. Values - can be duplicated.

Map is not child interface of Collection.

SortedMap (Interface) :

1. Sorting is based on Keys.
2. SortedMap is child interface of Map.

List of Methods present in Collection Interface:

• boolean add(Object o)
• boolean addAll(Collection c)
• boolean remove(Object o)
• boolean removeAll(Collection c)
• boolean retainAll(Collection c)
• void clear()
• boolean isEmpty()
• int size()
• boolean contains(Object o)
• boolean containsAll(Collection c)
• Object[] toArray()
• Iterator iterator()

List (Interface) :

Duplicates are allowed, insertion order is preserved.
Insertion order is preserved by means of Index.
We can differentiate duplicate objects by using Index. Index place a very important role in List.

• boolean add(int index, Object o)
• boolean addAll(int index, Collection c)
• Object remove(int index)
• Object get(int index)
• Object set(int index, Object new)
• int indexOf(Object o)
• int lastIndexOf(Object o)
• ListIterator listIterator()

ArrayList :

• Insertion order is preserved
• Duplicate objects are allowed
• Heterogeneous objects are allowed
• 'null' insertion is possible, example a.add(null);
• Best suitable for frequent retrievals
• Is not thread-safe.

Constructors:

ArrayList al = new ArrayList()  -- this creates an ArrayList with an initial default capacity of 10.  Once ArrayList reaches its max. capacity, then a new ArrayList object will be created with  newCapacity = (currentCapacity * 3/2) + 1


Example:
import java.util.*;
public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList a = new ArrayList();
        a.add("A");
        a.add(10);
        a.add("A");
        a.add(null);
        System.out.println(a); // [A, 10, A, null]
        a.remove(2);
        System.out.println(a); // [A, 10, null]
        a.add(2, "M");
        a.add("N");
        System.out.println(a); // [A, 10, M, null, N]
    }   
}

Note: In every Collection class, toString() method is overwritten to return its content directly in the following format:
[obj1, obj2, obj3 ..... obj n ]

Usually, we can use Collection to store and transfer objects. To support this requirement, every Collection class implements Serializable and Cloneable interfaces.

Frequent RETRIEVE operation - best choice is ArrayList.

Frequest INSERTION and DELETION - use LinkedList.

Vector is Thread-safe.

Since Vector is thread-safe, the performance is low compared to ArrayList.

If thread-safe is not required, use ArrayList.

How to get Synchronized version of ArrayList????

Use the Collections utility class SynchronizedList() method.

Example:
ArrayList l = new ArrayList();
List l1 = Collections.synchronizedList(l);

LinkedList :

• Insertion order is preserved
• Duplicates are allowed
• Heterogeneous objects are allowed
• null insertion is possible
• Best suitable for frequent insertion and deletion operations
• Not implements RandomAccess interface

 Usually, we can use LinkedLists to implement Stacks and Queues. To support this, LinkedList class defines the following specific methods:

• void addFirst(Object o)
• void addLast(Object o)
• Object removeFirst()
• Object removeLast()
• Object getFirst()
• Object getLast()

import java.util.*;
public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList l = new LinkedList();
        l.add("durga");
        l.add(10);
        l.add(null);
        l.add("durga");
        System.out.println(l); // [durga, 10, null, durga]
        l.set(0, "software"); // set will replace at index.
        System.out.println(l); // [software, 10, null, durga]
        l.add(0, "venky"); // add will add at the index
        System.out.println(l); // [venky, software, 10, null, druga]
        l.removeLast();
        System.out.println(l); // [venky, software, 10, null]
        l.addFirst("ccc");
        System.out.println(l); // [ccc, venky, software, 10, null]
    }   
}

Vector :

• insertion order is preserved
• duplicates are allowed
• heterogeneous objects are allowed
• null insertion is allowed
• best suitable for frequent retrievals.
• it is thread-safe. all methods are synchronized

Vector v = new Vector(); --> creates a vector with initial capacity of 10. Once vector reaches its max capacity, a new Vector object is created with double capacity.
newCapacity = 2 * currentCapacity

Vector has few other methods which are initially added as part of Vector. (Java 1.0). Later, Vector has retrofitted with new methods of List interface to become part of Java Collection framework.

Vector.addElement() method is old one. addElement() is synchronized. add() isn't. In the Java Collections Framework, if you want these methods to be synchronized wrap the collection in Collections.synchronizedList();

Favour the use of the List methods. Like I said, if you want a synchronized List do:

List<String> list = Collections.synchronizedList(new ArrayList<String>());
list.add("hello");

import java.util.*;
public class VectorExample {
    public static void main(String[] args) {
        Vector v = new Vector();
        System.out.println(v.capacity()); // default capacity, 10
        for (int i = 1; i <= 10; i++) {
            v.addElement(i);
        }
        System.out.println(v.capacity()); // 10
        v.addElement("A");
        System.out.println(v.capacity()); // 20 - doubled the capacity
        System.out.println(v); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, A]
    }   
}

Stack :

Child class of Vector, contains only one constructor :
Stack s = new Stack();

methods:

• Object push(Object o)
• Object pop()
• Object peek() - return top of Stack
• boolean empty()
• int search(Object o) - returns offset from top of Stack if object available, else -1

import java.util.*;
public class StackExample {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.push("A");
        s.push("B");
        s.push("C");       
        System.out.println(s.peek()); // top of stack is C
        System.out.println(s); // [A, B, C]
        System.out.println(s.search("A")); // this offset is 3
        System.out.println(s.pop()); // popped element C
        System.out.println(s); // [A, B]
        System.out.println(s.search("Z")); // -1       
    }
}

Cursors :

If we want to get objects one by one from the Collection, we should go for cursor.

3 types or cursors available in Java:

Enumeration - applicable for legacy classes, and is read-only.

Iterator - universal and all operations permitted (read and delete). Forward direction

ListIterator : bi-directional. We can perform replace and addition of new objects in addition to read and remove operations.

ListIterator is only applicable for List objects.

Iterator :

Iterator itr = c.iterator();  // c -- is any Collection class

3 methods:

• public boolean hasNext();
• public Object next();
• public void remove()

HashSet -> is based on HashTable. No duplicates allowed, insertion order is not preserved.

LinkedHashSet -> No duplicates, and insertion order is preserved.

Usage: the application area of LinkedHashSet and LinkedHashMap is implementing cache applications.

SortedSet (Interface) :

To represent a group of individual objects according to some sorting order. 6 specific methods.

• Object first() - returns the first element of sorted set.
• Object last() - returns last element of sorted set
• SortedSet headSet(Object obj) - returns sorted set whose elements are less than obj
• SortedSet tailSet(Object obj) - whose elements are greater than or equal to obj
• Comparator comparator() - returns comparator object which describes underlying sorting technique. For natural sorting order, this will return null.

public class SortedSetTest {

   public static void main(String[] args) {

      // Create the sorted set
      SortedSet set = new TreeSet(); 

      // Add elements to the set
      set.add("b");
      set.add("c");
      set.add("a");

      // Iterating over the elements in the set
      Iterator it = set.iterator();
      while (it.hasNext()) {
         // Get element
         Object element = it.next();
         System.out.println(element.toString());
      }
   }
}

Default natural sorting order for numbers is ascending order.

Default natural sorting order for characters and strings is alphabetical order (dictionary based)

TreeSet (Class) :

• Duplicates are not allowed
• Insertion order is not preserved
• Heterogeneous objects are not allowed, because sorting has to be applied. In this case, ClassCastException is thrown.
• null insertion is not possible for non-empty set. For the empty set, add first element null, insertion is possible. But after inserting null, if we try to add any element, NullPointerException is thrown.

Constructors:

TreeSet t = new TreeSet(); // default natural sorting order

TreeSet t = new TreeSet(Comparator c); // sorting order is based on Comparator object

If we are depending on natural sorting order, compulsorily objects should be homogeneous and comparable, otherwise we will get ClassCastException.

An object is said to be comparable, if the corresponding class implements Comparable Interface.

String class and all wrapper classes already implements Comparable interface where as StringBuffer class does not implement Comparable interface.

import java.util.*;
public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet t = new TreeSet();
        t.add(new StringBuffer("A"));
        t.add(new StringBuffer("B"));
        t.add(new StringBuffer("Z"));
        t.add(new StringBuffer("T"));
        System.out.println(t);
    }
}

This above example will throw ClassCastException as StringBuffer does not implement Comparable interface.

Comparable Interface :

Interface present in java.lang package and contains only one method compareTo.

Any class implementing Comparable Interface has to override this method:

public int compareTo(Object obj);

Comparable meant for natural sorting order.

Comparator meant for customized sorting order.

Comparator Interface :

java.util package.

2 methods:

• public int compare(Object obj1, Object obj2)
• public boolean equals(Object obj)

Whenever we are implementing Comparator interface, compulsory we should provide implementation for compare() method.