Collection Framework in Java

The collection framework in java is made up of classes and interfaces that stores and processes data in an efficient manner.

  • The Sun Microsystems has introduced collection framework in Java 2.0

  • The hierarchy of the whole collection framework is given below :

collection hierarchy in java

  • List is an interface that is available in the java.util package.

  • List is used to store a collection of elements and allows duplicates.

  • The term ‘List is ordered’ means that the order is retained in which we add elements, and will get the same sequence while retrieving elements.

  • List interface has three concrete subclasses:

    • ArrayList
    • LinkedList
    • Vector

Remember the following three important methods of List :

  • Boolean add(Object o) ; //Append the specified elements to the end of the list
    • Return type is Boolean
    • Input type is Object

  • Object get(int i); //Return the elements as Object of the specified position in the list
    • Return type is Object
    • Input type is int [index of Arraylist ]

  • int size(); // Return number of elements in the list
    • Return type is int [no of elements exist.]
    • Input type is nothing

ArrayList

The ArrayList extends the AbstractList and implements the List interface. It is usually slower than the other arrays, but is useful where you need to manipulate a lot in programs.

  • Uses Dynamic array for storing the elements

  • Duplicate elements are allowed

  • Maintains insertion order

  • Methods are not synchronised

  • Random access as it works on index basis

  • Manipulation is slow because lot of shifting needs to be done. This means that if the ArrayList has 1000 elements and we remove the 50th element, then the 51st element tries to acquire that 50th position and likewise all elements. So, moving every element consumes a lot of time.


Vector

The vector class ‘implements a growable array of objects. Similar to an array, it contains components that can be accessed using an integer index’. The vector may expand or contract as per the requirements.

  • All methods are synchronised

  • It is slower than an Arraylist

  • Vector is thread-safe as it has synchronised methods

  • It has capacity concept. The default capacity is 10

  • It doubles when it reaches its threshold

  • Size methods returns the number of elements present

  • Capacity method returns the capacity which doubles after reaching the default capacity, which is 10

  • Vector can be iterated by simple for loop, Iterator, ListIterator and Enumeration


Example


Example for vector :

  • Every List interface implementing class has two constructors :
    • Default constructor
    • Constructor which takes java.util.collection

Example of ArrayList


Example of Vector

Iterator Enumeration
  • Iterator can be used to access the elements of six subclasses of collection interface:
    1. ArrayList
    2. Vector
    3. LinkedList
    4. LinkedHashSet
    5. Treeset and HashSet
  • Enumeration can be used for accessing elements of vector only.
  • Using the Iterator methods hasNext() and next(), you can access the elements of collection.
  • Using enumeration method has More Elements() and nextElements(), you can access the elements of vector one by one.
  • Using the Iterator you can remove the elements of collection. Example : Iterator it=al.iterator();
      while(it.hasNext()) {
       String str=it.next().toString();
        if(str.equals("jbk")) {
         it.remove();
      }
    }
  • Enumeration is read only i.e. you can just the read the data from vector but you cannot remove the element from vector using Enumeration.
  1. ListIterator is the sub interface of Iterator and therefore has more features in ListIterator than Iterator.

  2. ListIterator can access elements in forward and reverse directions.

  3. Adding elements by using add method.

  4. Replacement of existing elements with new element by using the set method.

  5. Access index of element.

Iterator ListIterator
  • Using Iterator we can access the elements of collection only in forward direction using the hasNext() & next() methods.
  • Using ListIterator we can access the elements in the forward direction using hasNext() and next() methods and in reverse direction using hasPrevious()and previous() methods.
  • You cannot add elements to collection.
  • You can add the elements collection.
  • You cannot replace the existing elements with new elements.
  • You can replace the existing elements with a new element by using void set(E e).
  • Using Iterator you cannot access the indexes of elements of collection.
  • Using ListIterator you can access indexes of elements of collection using nextIndex() and previousIndex() methods.
  • Using Iterator you can remove the elements of a collection.
  • Using ListIterator you can also remove the elements of collection.
Array ArrayList
  • The size of an Array is fixed, i.e. when you create an array with same size you cannot change dynamically.
  • The size of an ArrayList is grow-able, i.e. once the ArrayList is created you can add any number of elements without restriction.
  • When you create an small Array you can't add more elements and when you create a large sized array, the memory will be wasted when we don't put that.
  • You won't get these problems with an ArrayList.
  • When you have an array with a size 100 and has 10 elements only, then you need to repeat the loop 100 times to access 10 elements which is an unnecessary and time consuming process.
  • When you access elements of ArrayList using iterator you won't face this time wastage problem.
  • Array stores only similar types of elements.You can store primitive and objects in Array
    e.g: int a[]=new int[5];
    Students[] stu=new Student[5];
  • ArrayList store different types of elements You can store only objects in an ArrayList Student s1= new Student();
    e.g. al.add(s1);
    al.add("sri");

Note: Both Array and ArrayList store the elements internally using indexing representation and these elements can be accessed randomly

  • You can access the elements of an Array using index representation
    For example: a [1]
  • You cannot access the elements of an ArrayList using index representation
    For example: al [0] is not allowed but al.get(0) is allowed

Comparison between ArrayList, Vector and LinkedList:

Topic ArrayList Vector LinkedList
Legacy or collection Framework Collection framework class added in java 2 Legacy class but revised in java 2 Collection framework class added in java 2
Synchronised Not Synchronised Synchronised Not Synchronised
Storage Representation Index Representation Index Representation Node Representation
Accessing Elements Iterator. List Iterator Enumeration. Iterator List Iterator Iterator. List Iterator
Access Type Random Access Random Access ----
  • A set is used to store the collection of elements without duplicates.

  • It is an unordered collection which means that order is not maintained while storing elements and while retrieving them, we may not get the same order that we had put them in.

  • A set cannot be iterated by using ListIterator but by Iterator.

  • There are four classes which implement Set interface:
    • HashSet
    • LinkedHashSet
    • TreeSet
    • SortedSet - It uses hash table to store elements. Duplicates are not allowed.

Example: Consider the following program of HashSet


Comparison between HashSet, LinkedHashSet and TreeSet:

Topic HashSet LinkedHashSet TreeSet
Duplicate Not Allowed Not Allowed Not Allowed
Ordering Unordered Maintains insertion order Maintains sorting order
Null Allow Allow Do not allow
Accessing Elements Iterator Iterator Iterator
Thread Safety No No No
  • The Queue is an interface of a subtype of the Collection interface

  • It represents an ordered list of objects just like a List, but its intended use is slightly different.

  • A queue is designed to have elements inserted at the end of the queue, and elements removed from the beginning of the queue. Just like a queue in a supermarket or any shop.

  • Following are the concrete subclasses of the Queue interface:
    • ArrayDeque
    • PriorityQueue
    • PriorityblockingQueue
    • LinkedBlockingQueue

  • Each Queue method exists in two forms:
    • One throws an exception if the operation fails
    • The other returns a special value if the operation fails (either null or false, depending on the operation)


  • Dequeue is a sub-interface of Queue interface

  • A double-ended-queue is a linear collection of elements that supports the insertion and removal of elements at both end points

  • It defines methods to access the elements at both ends of the Deque instance

  • Methods for insertion, removal and retrieval of Deque elements are summarised in the following table:
  • Type of Operation First Element (Beginning of the Deque instance) Last Element (End of the Deque instance)
    Insert addFirst(e)
    offerFirst(e)
    addLast(e)
    offerLast(e)
    Remove removeFirst(e)
    pollFirst(e)
    removeLast(e)
    pollLast(e)
    Examine getFirst(e)
    peekFirst(e)
    getLast(e)
    peekLast(e)
  • A map is used to store the key-value pair

  • It doesn't allow duplicate keys but duplicate values are allowed

  • It has the following concrete subclasses:
    • HashMap
    • WeakHashMap
    • HashTable
    • IdentityHashMap
    • TreeMap
    • LinkedHashMap

HashMap:

  • A HashMap is class which implements the Map interface

  • It stores values based on key

  • It is unordered, which means that the key must be unique

  • It may have null key-null value

  • For adding elements in HashMap we use the put method

  • Return type of put method is Object

  • It returns the previous value associated with key or null if there was no mapping for key


Example:


LinkedHashMap:

  • A LinkedHashMap is a ‘hastable and linked list implementation of the map interface with a predictable iteration order.

  • It is the same as HashMap except it maintains an insertion order i.e. ordered
    Consider the same above programs using LinkedHashMap. Observe the output. Change one line in the above example.


In above program,


TreeMap:

  • The TreeMap is a class which implements NavigableMap interface which is the sub- interface of SortedMap.

  • It stores values based on key

  • It is ordered but in an Ascending manner

  • Keys should be unique

  • It cannot have null key at run time but can have null values because the interpreter will not understand how to sort null with other values

  • Consider the program of storing elements using TreeMap


Example:


Hashtable:

  • Hashtable is a class which implements Map interface and extends Dictionary class.

  • It stores values based on key

  • It is unordered and the key should be unique

  • It cannot have null keys or null values. It gives runtime error if we try to add any null keys or values but will not show an error at compile time.

  • It has synchronised methods and slower than hashmap

  • Consider the program of storing elements using Hashtable


Example:


Comparison between HashMap, LinkedHashMap, TreeMap and HashTable:

Topic HashMap LinkedHashMap TreeMap HashTable
Duplicate Key Not Allowed Not Allowed Not Allowed Not Allowed
Ordering Unordered Maintains insertion order Maintains in Accessing order Unordered
Null (Key Value) Allow Allow key Not allowed but value is Iterator Not Allowed
Accessing Elements Iterator Iterator Iterator Iterator
Thread Safety No No No Yes

It can be used to get properties from xml file or to store data in xml file.

  • All methods of this class are synchronised, So it is a thread-safe class

  • It is since jdk 1.0

  • It is the subclass of HashTable

  • It stores the key-value pair, but both as string

  • It can be used to get property value based on property key

  • It can also be used to get properties of system

  • It provides easy maintenance

Example:


An XML file is created as shown below in the D drive that we have just printed in above Program
Example:



  • All methods of this class are static. Constructor is private

  • This class has methods to give extra features to Collection Hierarchy. For example: sort, binary Search, reverse, finding min value, max Value and making list read only.

  • Those collection classes which are not synchronised will be synchronised by using methods - synchronizedList (), synchronizedMap ()

Example:


Note:

  • To sort custom objects. For example: One student having age and location We add students in Arraylist and we want to sort these students on the basis of their ages If we use only Collections, it will sort by addresses of the students’ object, which we don't want.

  • This is not possible with the ordinary sort method. For that we need to use Comparable or Comparator interface, where we need to specify our sorting criteria. Then we can pass that criteria into the sort method.

Comparable Interface:

Comparable interface is primarily used to sort out lists or arrays of custom objects. It contains only one method.

  • The class whose object has to be compared has to implement Comparable interface and has to override compareTo () method in the following format.

  • public int compareTo(Object 0bj).

  • Comparable provides only one way of comparison.

  • You can sort the elements on based on single data member only. For instance it may be rollno, name, age or anything else.


Example:
Consider the following program of sorting students on the basis of age:


Comparator interface is used when you have to order user-defined class objects and contains two methods.

  • We need to write separate class by implementing Comparator interface by overriding the following method:
    public int compare(Object o1,Object o2)

  • You can write multiple comparators to compare objects in different ways
    To use compare() method of Comparator interface for sorting, use following method:
    Collections.sort(al , new NameComparator());


The following table gives the properties of derived classes:

properties of derived classes in java