A Crash Course in the Java Collections Framework
Wednesday, September 17, 2003

By goongas
TopCoder Member

Introduction
On the heels of a recent article by Yarin describing the C++ Standard Template Library, this article will try to quickly teach how to use the Java Collections Framework (JCF) for common Java programming tasks. It does not mention how things work behind the scenes, or when to use which data structure, but instead gives several small code snippets from which one can learn how to use some parts of the JCF. Many advanced features are omitted. For more detailed information, see the links at the bottom of the article.

The Java Collections Framework is the standard collection of data structures and algorithms for Java. A data structure is an object that holds several elements, which can be the same or different class. (It is not recommended to store elements of different classes in one data strucuture). The containers covered in this article are ArrayList, HashSet/TreeSet, and HashMap/TreeMap. Include the following line at the top of code in which you want to use JCF structures:

import java.util.*;

ArrayList

An ArrayList corresponds to a one dimensional array. An ArrayList is declared and allocated like this:

ArrayList al = new ArrayList();

The ArrayList above has a size of 0. The size of an ArrayList is reduced or expanded automatically if needed. To add elements to an ArrayList, you can use the add method. (Note: you can only add elements that are objects of a class to JCF data structures. To add native data types like ints or chars, you must use the corresponding wrapper classes).

al.add(new Integer(10));

To replace all the elements in an ArrayList with a new value, you can use the fill method from the Collections class:

Collections.fill(al, new Integer(25)); //all existing elements are now 25

Elements in an ArrayList are accessed using the get(int index) method. For example:

int var1 = ((Integer)al.get(0)).intValue();  //retrieves the first element in al and converts it to an int

Other useful methods in the ArrayList class are:

int size();                        //Returns the number of elements in the ArrayList
Object remove(int index);          //Removes the element located at the specified index
boolean contains(Object element);  //Returns true if the ArrayList contains element, otherwise false
int indexOf(Object element)        //Searches for the first instance of element and returns its position, 
                                   //or -1 if it is not found
void clear();                      //Removes all elements from the ArrayList

Sorting an ArrayList

An ArrayList can be sorted in ascending order according to the natural order of the elements by using Collections.sort(), as long as the class of the elements implements Comparable:

  
Collections.sort(al);

To sort in an order you specify and/or to sort classes that do not implement Comparable, you can create a comparator, as in the following example:

public class DescendingComparator implements Comparator{
   public int compare(Object o1, Object o2) /*descending order*/  {
      if (((Integer) o1).intValue() > ((Integer)o2).intValue()) return -1;
      else if (((Integer) o1).intValue() < ((Integer)o2).intValue()) return 1;
      return 0; /*equal*/
   }
}

Collections.sort(al, new DescendingComparator()); //will sort ArrayList of Integers in descending order

HashSet/TreeSet

A set is used to store non-duplicate, as defined by the equals() method of the class, elements. A HashSet is unsorted, while a TreeSet is sorted by the natural ordering of the elements or the rules of a comparator. Examples of declaration and allocation are as follows:

HashSet hs = new HashSet();
TreeSet ts = new TreeSet(); 
TreeSet ts2 = new TreeSet(new DescendingComparator());  //elements will be sorted in descending order

To add, remove and check for single elements in a set:

hs.add(new Integer(7));     //Insert integer 7 in the set
hs.remove(new Integer(5));  //Remove integer 5 (if it exists) from the set
hs.contains(new Integer(7)) //Checks to see if 7 is in the set

To access elements in a HashSet/TreeSet, you can use an iterator to iterate through the set. For example:

Iterator itr = hs.iterator();
int sum = 0;
while (itr.hasNext()) {
   sum += ((Integer)itr.next()).intValue();
}

You can create an ArrayList from an existing set, and vice versa:

ArrayList al = new ArrayList(hs);
HashSet   hs = new HashSet(al);

HashMap/TreeMap

In certain cases, there is a need to store a one-to-one relationship between two elements. The first element is the key, and the second element is the value. For example, we may want to lookup someone's age by their last name. The last name is the key, and the age is the value. TreeMaps are sorted by the keys, while HashMaps are unsorted. Below is the code to setup and use a HashMap (the code for a TreeMap is similar).

  
HashMap hm = new HashMap();
hm.put("Smith", new Integer(20)); //Smith is 20
hm.put("Jones", new Integer(23)); //Jones is 23
hm.put("Smith", new Integer(21)); //Smith is now 21, the Smith-20 relationship was overwritten.
hm.get("Smith")                   //will return Integer 21

To iterate through the HashMap and obtain the sum of the ages, you can do the following:

Iterator itr = hm.keySet().iterator();
int age = 0;
while (itr.hasNext())
   age += ((Integer)hm.get(itr.next())).intValue();  //at end of loop age will contain 41

Other useful methods are containsKey(Object key), containsValue(Object value), and remove(Object key).

More about the Java Collections Framework

More information about the Java Collections Framework can be found at http://java.sun.com/products/jdk/1.2/docs/guide/collections/. The API for Java 1.4.2 can be found here at http://java.sun.com/j2se/1.4.2/docs/api/index.html.

Would you like to write a feature?