The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Java Collection Framework

Collection represents a group of objects stored and manipulated together. Java Collection framework is a set of interfaces and classes which provides a readymade implementation of commonly used data structures ( like list, arrays, maps, etc. ) and algorithms ( like sort, search, insert, delete, etc. ). Thus, we get an architecture where we can perform operations on a set of objects without worrying about how they are stored and the actual implementation of how the operations are performed in the background. For e.g, we can simply store some String objects in a Vector and use the sort algorithm to get the lexicographic order. We can only focus on the actual logic to get some task done. In this module, we will discuss about different data structures and algorithm which comes as a part of Collection Framework.

Collection Classes and Interfaces
This framework consists of interfaces and the concrete classes which implement them. The interfaces are the basic data structures and the classes implement them in different ways. For e.g List is an interface and the different classes which implements List are Linked List and ArrayList. Similarly, Set is an interface which is implemented by HashSet, TreeSet and LinkedHashSet classes. Map interface is implemented by HashMap, TreeMap and LinkedHashMap classes. Now we will see sample programs to demonstrate the use of these classes are used in Java programs.
Note : If you compile the programs shown below, you will get a message indicating the use of deprecated feature since we are not using Generic feature of Java language. You can still run the program but it is recommended to use Generic which we will discuss in the next module. This section aims to introduce you to various classes and interfaces present in Collection framework.

ArrayList class
This class is used as a dynamic array to store elements. It extends the AbstractList class and implements List interface. Elements can be accessed randomly using the index. Insertion and deletion operations are expensive since it requires shifting of other elements. See the program below :

import java.util.*;
public class ArrayListDemo {
   public static void main(String args[]) {
      int size;
      ArrayList alist = new ArrayList(); // create an array list
      /* We can also refer to the object of ArrayList class as :-
       * List alist = new ArrayList();
       */
      /* add elements in the ArrayList */
      alist.add("John");
      alist.add("jack");
      alist.add("Jimmy");
      alist.add("Jerry");
      size = alist.size();
      System.out.println("No. of elements : " + size);
      /* iterate over the elements ( objects of collection )
       * ( using Iterator interface )
       */
      System.out.print("ArrayList elements : ");
      Iterator it = alist.iterator();
      while(it.hasNext()) {
         System.out.print(it.next() + " ");
      }
      System.out.println();
      alist.remove(2); // remove the element at index 2
      alist.add(1, "Jill"); // insert an element at index 1
      /* iterate over the elements ( objects of collection )
       * ( using 'for each' loop )
       */
      System.out.print("ArrayList elements : ");
      for(Object ob : alist) {
         System.out.print(ob + " ");
      }
      alist.clear(); // removes all elements from the list
      System.out.println("\nAll elements removed ... ");
      System.out.println("Now the size of the list is " + alist.size());
   }
}


LinkedList class
This class also extends the AbstractList class and implements List interface. Insertion and deletion are very fast as no shifting is required ( it involves pointer movements ) but it provides sequential access only. Following program illustrates how a linked list is used to store objects of user defined class :

/* In this program we store and manipulate a collection
 * of 'Student' objects where 'Student' is a user-defined class
 */
import java.util.*;
class Student {
   String name;
   int roll;
   float marks;
   Student(String s_name, int s_roll, float s_marks) {
      name = s_name; roll = s_roll; marks = s_marks;
   }
   public void display() {
      System.out.print(name + " Roll : " + roll + " Marks : " + marks);
      System.out.println();
   }
}
public class LinkedListDemo {
   public static void main(String args[]) {
      Student s1 = new Student("John", 7, 73.87f);
      Student s2 = new Student("Jack", 3, 92.53f);
      Student s3 = new Student("Jim", 5, 64.35f);
      LinkedList studlist = new LinkedList();
      studlist.add(s1);
      studlist.add(s2);
      studlist.add(s3);
      Iterator it = studlist.iterator();
      while(it.hasNext()) {
         Student s = (Student)it.next();
         s.display();
      }
   }
}


HashSet class
This class also extends the AbstractSet class and implements Set interface. HashSet contains unique elements only and it uses HashTable to store those elements. HashTable uses a mechanism called hashing in which a hash-code is computed for each element and this code acts as an index for the element in the hash table. Following program shows the use of HashSet :

import java.util.*;
public class HashSetDemo {
   public static void main(String args[]) {
      HashSet hs = new HashSet();
      /* We can also refer to the object of HashSet class as :-
       * Set hs = new HashSet();
       */
      hs.add("Rahul");
      hs.add("Raj");
      hs.add("Ajay");
      hs.add("Rajesh");
      Iterator itr = hs.iterator();
      while(itr.hasNext()) {
         System.out.print(itr.next() + " ");
      }
      System.out.println();
      // another way of display HashSet elements
      System.out.println(hs);
   }
}

Similar to HashSet, there is TreeSet which uses a tree for storage of elements. In TreeSet, all the elements are stored in sorted order. There is also a class called LinkedHashSet which maintains a linked list of elements inserted. All elements are unique in TreeSet and LinkedHashSet.

HashMap class
This class extends AbstractMap class and implements Map interface. HashMap is used to store key-value pairs in a hash table. It stores unique elements and each element is accessed using the key. See the program below :

import java.util.*;
public class HashMapDemo {
   public static void main(String args[]) {
      HashMap hm = new HashMap();
      /* add key-value pairs in the HashMap where
       * key -> Roll No. and value -> Name
       */
      hm.put(1, "Anjali");
      hm.put(2, "Rahul");
      hm.put(3, "Tina");

      /* find the student with roll no. 2 */
      String stud = (String)hm.get(2);
      System.out.println("Student name : " + stud);

      /* find all the students and their roll no. */
      System.out.println("Students data :- ");
      Set s = hm.entrySet();
      Iterator it = s.iterator();
      while(it.hasNext()) {
         Map.Entry m = (Map.Entry)it.next();
         System.out.println(m.getKey() + " " + m.getValue());
      }

      hm.remove(3); /* Remove the student with roll no. 3 */
      hm.put(2, "Aman"); /* Replace the student with roll no. 2 */

      System.out.println("Modified Students data :- ");
      it = s.iterator();
      while(it.hasNext()) {
         Map.Entry m = (Map.Entry)it.next();
         System.out.println(m.getKey() + " " + m.getValue());
      }
   }
}

Similar to HashMap, there is TreeMap which stores the key-value pairs which are sorted according to keys. There is also a class called LinkedHashMap which maintains the order in which elements were inserted. There is another class called HashTable which can be used for same purpose as HashMap and related data structures.

Vector Class
Vector is a dynamic array of objects. Vector was a part of Java even before Collection framework was introduced. So it contains many legacy methods that are not a part of Collections framework. Following program illustrates the use of Vector class :

import java.util.*;
public class VectorClassDemo {
   public static void main(String[] args) {
       Vector v = new Vector();
       v.addElement(new Double(3.4));
       v.addElement(new Double(4.7));
       v.addElement(new Double(2.9));
       v.addElement(new Double(5.1));
       System.out.println("Last element is " + v.firstElement());
       System.out.println("Last element is " + v.lastElement());
       v.removeElement(0);
       Enumeration venum = v.elements();
       System.out.print("Elements in vector : ");
       while(venum.hasMoreElements()) {
            System.out.print(venum.nextElement() + ", ");
       }
       System.out.println();
   }
}


Stack Class
Stack is a Last-in-First-out ( LIFO ) type data structure i.e element which is inserted first will be removed last. Following program demonstrates the use of Stack class :

import java.util.*;
public class StackDemo {
   public static void main(String[] args) {
      Stack s = new Stack();
      s.push(new Integer(7));
      s.push(new Integer(3));
      s.push(new Integer(9));

      // get top value from stack
      System.out.println("\nTop Value : " + s.peek());
      // remove the top value
      System.out.println("Remove the Top value : " + s.pop());
      System.out.println("Now Top Value : " + s.peek());
   }
}


Queue Interface
Queue is a First-in-First-out ( FIFO ) type data structure i.e element which is inserted first will be removed first. In the following program, we implement the Queue interface using LinkedList class :

import java.util.*;
public class QueueDemo {
   public static void main(String[] args) {
      Queue q = new LinkedList();
      q.add("Anjali");
      q.add("Rahul");
      q.add("Tina");

      System.out.println("Size of Queue : " + q.size());
      System.out.println("Queue elements :- ");
      Iterator it = q.iterator();
      while(it.hasNext()) {
         System.out.print((String)it.next() + " ");
      }

      // get first value from queue
      System.out.println("\nFirst Value : " + q.peek());
      // remove the first value
      System.out.println("Delete the first value : " + q.poll());
      // get first value and remove that object from queue
      System.out.println("Now the size of the queue is : " + q.size());
   }
}


PriorityQueue Class
PriorityQueue is similar to Queue but elements are processed according to their priority. The priorities can be assigned to elements by providing a comparator ( discussed below ) at the time of instantiation of the PriorityQueue. If no priorities are assigned, the by default elements are stored by their natural ordering as per Heap data structure ( Priority Queue is implemented using Heap ). See the program below :

import java.util.*;
public class PriorityQueueDemo {
   public static void main(String[] args) {
      PriorityQueue pq = new PriorityQueue();
      pq.add(new Integer(5));
      pq.add(new Integer(11));
      pq.add(new Integer(7));
      pq.add(new Integer(9));
      pq.add(new Integer(4));
      System.out.println("Queue Head : " + pq.peek());
      System.out.print("Queue Elements : ");
      Iterator it = pq.iterator();
      while(it.hasNext()) {
         System.out.print(it.next() + " ");
      }
      System.out.println("\nRemove Head element : " + pq.poll());
      System.out.println("Remove Head element : " + pq.poll());
      pq.add(new Integer(33)); // add another element
      System.out.print("Queue Elements : ");
      it = pq.iterator();
      while(it.hasNext()) {
         System.out.print(it.next() + " ");
      }
      System.out.println();
   }
}


Comparable and Comparator Interfaces
Comparable interface is used to order the elements ( objects ) stored in a data structure. This interface contains only one method compareTo( object ob ) which can be overridden to decide the order of the elements. Suppose we have a class called Employee. An object of this class contains information about an employee. We can sort the employees based on single data member of the class ( in this case employeeID ).
Comparator interface is similar to Comparable interface but in this case, we can define multiple ordering sequence ( for e.g, we can first sort the Employees based on employeeID and then based on salary ).
The programs shown below illustrates the use of these two interfaces :

Use of Comparable Interface
import java.util.*;
class Employee implements Comparable {
   int emp_id;
   String emp_name;
   Employee(int eid, String ename) {
      emp_id = eid; emp_name = ename;
   }

   void display() {
      System.out.println(emp_id + " " + emp_name);
   }

   public int compareTo(Object ob) {
      Employee e = (Employee)ob;
      if(emp_id > e.emp_id)
         return 1;
      else
         return -1;
   }
}

public class ComparableDemo {
   public static void main(String[] args) {
      List l = new ArrayList();
      l.add(new Employee(701, "Rahul"));
      l.add(new Employee(548, "Anjali"));
      l.add(new Employee(635, "Tina"));
      Collections.sort(l);
      Iterator it = l.iterator();
      while(it.hasNext()) {
         Employee e = (Employee)it.next();
         e.display();
      }
   }
}

Use of Comparator Interface
import java.util.*;
class Student {
   int roll;
   String name;
   float marks;
   Student(int r, String n, float m) {
      roll = r; name = n; marks = m;
   }
   void display() {
      System.out.println(roll + " " + name + " " + marks);
   }
}

class RollComparator implements Comparator {
   public int compare(Object s1, Object s2) {
      Student stud1 = (Student)s1;
      Student stud2 = (Student)s2;
      if(stud1.roll > stud2.roll)
         return 1;
      else
         return -1;
   }
}

class MarksComparator implements Comparator {
   public int compare(Object s1, Object s2) {
      Student stud1 = (Student)s1;
      Student stud2 = (Student)s2;
      if(stud1.marks == stud2.marks)
         return 0;
      else
      if(stud1.marks < stud2.marks)
         return 1;
      else
         return -1;
   }
}

public class ComparatorDemo {
   public static void main(String[] args) {
      List l = new LinkedList();
      l.add(new Student(7, "Rahul", 85.43f));
      l.add(new Student(9, "Anjali", 95.27f));
      l.add(new Student(5, "Tina", 87.64f));
      System.out.println("Sort student data by Roll no. :-");
      Collections.sort(l, new RollComparator());
      Iterator it = l.iterator();
      while(it.hasNext()) {
         Student s = (Student)it.next();
         s.display();
      }
      System.out.println("Sort student data by Marks :-");
      Collections.sort(l, new MarksComparator());
      it = l.iterator();
      while(it.hasNext()) {
         Student s = (Student)it.next();
         s.display();
      }
   }
}


Collection Algorithms
The Collection framework contains several standard algorithms ( search, sort, shuffling, etc. ) which can be applied to the data structures ( list, map, set, etc. ) described so far. Following program illustrates the use of some of these algorithms :

import java.util.*;
public class AlgorithmsDemo {
   static List al = new ArrayList();

   static void printlist() {
      Iterator it = al.iterator();
      while(it.hasNext()){
         System.out.print(it.next() + " ");
      }
   }

   public static void main(String[] args) {
      al.add(new Integer(5));
      al.add(new Integer(3));
      al.add(new Integer(7));
      al.add(new Integer(1));

      System.out.print("Current List : ");
      printlist();

      Collections.reverse(al); // reverse the list
      System.out.print("\nAfter Reversing the list : ");
      printlist();

      Collections.sort(al); // sort the list
      System.out.print("\nAfter Sorting the list : ");
      printlist();

      // Binary search must be performed on a sorted list
      int ele = 3;
      int pos = Collections.binarySearch(al, ele);
      if(pos != -1) {
         System.out.println("\nElement " + ele + " found at position " + pos);
      }
      else {
         System.out.println("\nElement not found ");
      }

      Comparator comp = Collections.reverseOrder();
      Collections.sort(al, comp);
      System.out.print("Sorting the list in reverse order : ");
      printlist();

      int max_val = (Integer)Collections.max(al); // find max element
      int min_val = (Integer)Collections.min(al); // find min element
      System.out.print("\nMaximum Value : " + max_val);
      System.out.print("\nMinimum Value : " + min_val);

      Collections.shuffle(al); // shuffle or randomize the list
      System.out.print("\nAfter Shuffling the list : ");
      printlist();

      System.out.println();
   }
}


Conclusion
We have introduced different interfaces and classes which are a part of Collection framework. We haven't described in detail about all the methods of each class and interface but you need not remember them as they can be found from class documentation as and when required. The most important factor is to decide which class or data structure present in the framework is to be used depending on the problem definition.

Back | Next