12  Java2 Collections

What's in This Set of Notes ?

• Collection Organization
• The Collection Interface and its Class Hierarchy
• The List Classes (Vectors/ArrayLists/LinkedLists/Stacks)
• The Set Classes (HashSet, TreeSet)
• The Map Interface and its Class Hierarchy
• The Map Classes (Hashtable, HashMap, TreeMap)
• The "Collections" Class

• storing videos and customers in a video store
• keeping track of cars for sale, for rent or for servicing
• a personal collection of books, cds, cards, etc...
• remembering products in a shopping cart that customers want to purchase from a website
• even simply storing available tools or utensils in a jar

In this set of notes, we investigate these new java collections.   There are many types of collections and at first, their organization appears a little confusing.   Collections are organized into a hierarchy of Interfaces, rooting at either Collection or Map:

Recall that an interface specifies a list of method signatures...not any code.    Also recall that interfaces can be arranged in a hierarchy just like classes so that interfaces can inherit from each other (e.g., SortedSets inherit from Sets and Collecions).

All collections store objects called their elements.   Note that data types cannot be stored in any kind of collection directly (we can use wrapper classes though).   The collections themselves allow heterogeneous objects to be stored.   That is, the elements in any one collection may be any kind of object and we can mix different kinds of objects within the same collection.   Storing mixed kinds of objects in a Collection is allowed, but not often done unless there is something in common with the objects (i.e., Abstract class or Interface).  Also, we will need to type-cast the value when we take it out of the collection so we need to know what kind of object is in there !

These interface definitions represent a general "type" of collection.   The collections all differ with respect to:

• accessing & modifying restrictions (e.g.,  some operations (such as addFirst() are allowed while others are not))
• accessing & modifying functionality (e.g., add() may work differently (such as doing sorting) depending on the collection)
• storage and efficiency (e.g., storing things in sorted order makes it easy to find them later).

Some collections allow duplicate elements (e.g., lists), while others do not allow duplicates (e.g., sets).   Some collections are ordered (e.g., lists), while some others are not ordered (e.g., sets and maps).   So you can see that there is a certain degree of specialty for each type of collection.   We need to understand what the characteristics of a collection are so as to be able to choose the right one for our application.   Try thinking about issues such as order and duplication for applications that involve:

• banks which keep collections of bank accounts
• companies which keep collections of employees
• airline reservation systems which keep collections of flights, customers, airlines, seating arrangements, etc...

Unlike Arrays, all Java2 collections (in general) are growable.   We will not discuss arrays any further in this set of notes as they are very special kinds of collections that actually have quite special behaviour.

Querying methods (returns some kind of value):

• size() - returns the number of elements in the collection
• isEmpty() - returns whether or not there are any elements in the collection
• contains(Object obj) - returns whether or not the given object is in the collection (uses .equals() method for comparison)
• containsAll(Collection c) - same as above but looks for ALL elements specified in the given collection parameter.

• add(Object obj) - adds the given object as an element to the collection (its location is not specified)
• addAll(Collection c) - same as above but adds ALL elements specified in the given collection parameter.
• remove(Object obj) - removes the given object from the collection (uses .equals() method for comparison)
• removeAll(Collection c) - same as above but removes ALL elements specified in the given collection parameter.
• retainAll(Collection c) - same as above but removes all elements EXCEPT THOSE specified in the given collection parameter.
• clear() - empties out the collection by removing all elements.

Notice that there are 4 abstract classes and 6 concrete classes shown.   There are actually a few more which you can take a peak at in the Java documentation.   Examining the diagram, we notice a few things of interest:

• All classes inherit from AbstractCollection, which contains common behaviour for all collections.
• All classes (or their parents) implement one of the Collection interfaces.
• The classes seem to be split as either having a List behaviour or a Set behaviour, but not both.

The List classes:

• are ordered
• may contain duplicates
• have indexable elements (using zero-based indexing).

There are 4 main List implementations:
 

Vector a general kind of list with many useful accessing/modifying/searching methods a synchronized class
ArrayList also general like Vectors an unsynchronized class (faster than Vectors)
LinkedList methods for double-ended access, no direct access from the middle  (you'll see more on this in your data structures course)
Stack accessable from one end only (the top).

Vectors/ArrayLists are perhaps the most-used collection class.   They are simple and intuitive to use.

Here are two ways of making one and storing it in a variable:

Vector     aVector = new Vector();
Vector     aVector = new Vector(Collection col);

ArrayList  anArrayList = new ArrayList();
ArrayList  anArrayList = new ArrayList(Collection col);

Notice that the Vector and ArrayList are used the same way once created !!!   If you do not care about synchronization, use ArrayList instead of Vector.

When extracting elements from a Vector or an ArrayList (or in fact ANY collection at all), the element is returned as type Object.

• it is as if Java forgot what kind of object was put in there
• we need to “type-cast” the value to an appropriate type.

String[]  names = {“Al”, “Zack”, “Sally”, “Mel”};
Vector v = new Vector(); //can use ArrayList v = new ArrayList(); instead
for(int i=0; i<names.length; i++) {
    Customer c = new Customer();
    c.setName(names[i]);
    v.add(c);
}

for (int i=0; i<v.size();i++) {
   Customer c = (Customer)v.get(i);
   System.out.println(c.getName());
}

A Linked List is very basic and general data structure.   It is actually used as a low-level data structure for implementing more complex data types such as stacks, queues, deques, trees, etc...   You will learn much more about linked lists in your 2nd year data structures course.

Linked lists allow direct operations to the front and the back of the list.  Such operations to the front and back of the list are typically quick whereas operations to access or modify an inner element of the list are typically very slow, requiring a linear search:

The elements of the list are still kept in order and so operations such as adding and removing from any position in the list is possible.   These operations are slower though.   It is more efficient to use these methods instead:

addFirst(Object obj) - add the given object to the front of the list
addLast(Object obj) - add the given object to the end of the list
removeFirst() - remove and return the first object from the list
removeLast() - remove and return the last object from the list
getFirst() - return the first object in the list
getLast() - return the last object in the list

We all know that a stack is a collection of items that are placed or "stacked" on top of one another.  The very definition of a stack implies a last-in-first-out protocol
when accessing the items.  That is, when placing items in the stack, we put them at the top and when removing them, we always take the top one off.

What do we use a stack for ?

• useful for recording the state of a computation as it unfolds
• evaluation of expressions that involve precedence and nesting
• can be used for reversing items

Stack myStack = new Stack();

• push(Object obj) - place the given object on the top of the stack and return a reference to it.
• pop() - remove and return the top element of the stack.   If there are no elements in the stack, an error occurs.
• peek() - return the top element of the stack without removing it.  If there are no elements in the stack, an error occurs.
• empty() - return whether or not there are any elements in the stack.
• search(Object obj) - return the distance of the given object from the top of the stack.  The topmost element has position 1.  If the object is not found in the stack, -1 is returned.   If duplicates exist, the position of the topmost one is returned.

Here is an example that determines if the brackets match in a given mathematical expression which is stored as a String.  When encountering an openning bracket
we'll increment a counter.  When encountering a closing bracket, we'll decrement the counter.

     "((23 + 4 * 5) - 34) + (34 - 5))" //does not match since there is one extra bracket
     "((23 + 4 * 5) - 34) + ((34 - 5)" //does not match since there is too may opening brackets.

import java.util.Stack;
public class Brackets {
    public static boolean bracketsMatch(String aString) {
        Stack     aStack = new Stack();

        //Go through the characters of the String and look for brackets
        for (int i=0; i<aString.length(); i++) {
           char aCharacter = aString.charAt(i);
           if (aCharacter == '(') {
             //We must convert the char data type to an Object (wrapper)
                aStack.push(new Character(aCharacter));
            }
           else
             if (aCharacter == ')') {
                 if (aStack.empty())
                     return(false);
                 else
                        aStack.pop();
                }
            }
           //Now check if there are open brackets still in the stack
           return aStack.empty();
        }

    public static void main(String args[]) {
        String aString;
        do {
            System.out.println("Please enter the expression: (just <cr> to quit)");
            aString = KeyboardPrompter.getString();

           //Now do the bracket matching
           if (bracketsMatch(aString))
                System.out.println("The brackets match");
           else
                System.out.println("The brackets do not match");
        } while (aString.length() > 0);
    }
}

Here are the testing results:
 

Please enter the expression: (just <cr> to quit) (1 + 3) The brackets match Please enter the expression: (just <cr> to quit) (1+(2+(3))) + (4+(5+(6))) The brackets match Please enter the expression: (just <cr> to quit) ( The brackets do not match Please enter the expression: (just <cr> to quit) ) The brackets do not match Please enter the expression: (just <cr> to quit) () The brackets match Please enter the expression: (just <cr> to quit) )( The brackets do not match Please enter the expression: (just <cr> to quit) Hello The brackets match Please enter the expression: (just <cr> to quit) The brackets match

Example

The example above is not very difficult, but what if we have 3 kinds of brackets (, [, and { ?    Maybe we can keep 3 counters ?  Nope.  We need to know the
order that the openning brackets are encountered.   We'll use a Stack to maintain this order.  When encountering an openning bracket we'll place it on the stack.
When encountering a closing bracket, we'll pop an openning bracket off the stack.

"[(23 + 4 * 5) - 34} + {34 - 5})" //does not match since there is one extra bracket
"[{23 + 4 * 5} - 34] + [(34 - 5)" //does not match since there is too may opening brackets.
 

Here is the code:

public static boolean bracketsMatch(String aString) {
    Stack     aStack = new Stack();
    char      aCharacter;

    //Go through the characters of the String and look for brackets
    for (int i=0; i<aString.length(); i++) {
        aCharacter = aString.charAt(i);
        switch(aCharacter) {
           case '(':
           case '[':
           case '{': aStack.push(new Character(aCharacter));
                   break;
           case ')': if ((aStack.empty()) || (((Character)aStack.pop()).charValue() != '('))
                   return(false); break;
           case ']': if ((aStack.empty()) || (((Character)aStack.pop()).charValue() != '['))
                   return(false); break;
           case '}': if ((aStack.empty()) || (((Character)aStack.pop()).charValue() != '{'))
                   return(false); break;
        }
    }
    //Now check if there are open brackets still in the stack
    return (aStack.empty());
}

The Set classes are much like Lists, except that they do not allow duplicates.

• there cannot be two elements e1 and e2 such that e1.equals(e2)
• any modifications to the elements that affect the equality results in unspecified behaviour
• attempts to add duplicates are not satisfied

HashSet elements are not kept in any particular order adding/removing operations are fast searching for a particular element is slow elements MUST implement .equals() and .hashCode()
TreeSet elements are kept in sorted order, but not indexable ordered is user defined order (default is ascending) adding is slow since it takes longer to find the proper location searching is fast now since items are in order

Consider this code that adds some BankAccounts to an ArrayList:

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
ArrayList aCollection = new ArrayList();

// Fill up the collection
for(int i=0; i<names.length; i++)
    aCollection.add(names[i]);

// Now print out the elements
for(int i=0; i<aCollection.size(); i++) {
    System.out.println(aCollection.get(i));
}

Can we simply replace the collection type to be HashSet and run this code ?  Well all the code works except for the call to get(i) in the second for loop.   Why ?  Because sets are non-indexable, so we cannot ask for particular elements from the set.   Instead, we must call the iterator() method for Sets that returns an iterator which we can then use to traverse through the elements:

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
HashSet aCollection = new HashSet();

// Fill up the collection
for(int i=0; i<names.length; i++)
    aCollection.add(names[i]);

// Now print out the elements
Iterator it = aCollection.iterator();
while (it.hasNext()) {
    Object anElement = it.next();
    System.out.println(anElement);
}

Now we only get the unique names coming out on the console window...so there are no duplicates :).
But hold on!   This is not the order that we added the names into the collection!!   Well...recall that the elements are not kept in any kind of order, and in fact, Java has its own pre-determined order based on hashcode values of the elements in which we added.   What about a TreeSet ?   Shouldn't that keep an order ?   Let's see:

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
TreeSet aCollection = new TreeSet();

// Fill up the collection
for(int i=0; i<names.length; i++)
    aCollection.add(names[i]);

// Now print out the elements
Iterator it = aCollection.iterator();
while (it.hasNext()) {
    Object anElement = it.next();
    System.out.println(anElement);
}

Notice that the items are sorted now alphabetically.   We'll see later how we can specify how to sort differently here (e.g., descending).

What if we want to store Team objects instead of simply strings ... where two teams are considered equal if they have the same name (see the Team class from the Array notes).

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
HashSet aCollection = new HashSet();
for(int i=0; i<names.length; i++) {
    Team c = new Team(names[i]);
    aCollection.add(c);
}

public boolean equals(Object obj) {
    if (!(obj instanceof Team))
        return false;
    return getName().equals(((Team)obj).getName());
}

public int hashCode() {
    return name.hashCode() + wins + losses + ties;
}

So...using a HashSet or TreeSet is one way of eliminating duplicates in a collection.
 
 

• storing many items by category (e.g., a video store is organized by sections (comedy/action/drama)).
• phonebooks where a value (e.g., number) is associated with a particular key (e.g., name).
• dictionaries where a value (e.g., definition) is associated with a particular key (e.g., word).

All Maps store a group of object pairs called entries.
 

Each map entry has a  key - identifies values uniquely (maps cannot have duplicate keys) value - accessed by their keys (each key maps to at most one value)

So, the key MUST be used to obtain a particular value from the Map.

The Map interface defines many messages:

Querying methods (returns some kind of value):

• size() - returns the number of elements in the map
• isEmpty() - returns whether or not there are any elements in the map
• containsKey(Object key) - returns whether or not the given object is a key of the map (uses .equals() method for comparison)
• containsValue(Object val) - returns whether or not the given object is a value in the map (uses .equals() method for comparison)
• getKey(Object key) - returns the value (as type Object) in the map that is associated with the given key
• values(Object key) - returns the a collection (as type Collection) of all the values in the map
• keySet(Object key) - returns a set (as type Set) of all the keys in the map
• entrySet(Object key) - returns a set (as type Set of Map.Entry objects) of all the key/value pairs in the map

• put(Object key, Object val) - adds a new entry in the map with the given key and value.  The key MUST be unique, otherwise this method replaces the value that was previously there by the given value
• putAll(Map m) - adds to the receiver map all entries that are in the given map
• remove(Object key) - removes the given key/value entry from the map based on the key only
• clear() - empties out the map by removing all elements

Here is the hierarchy showing most of the Map classes:

Consider this code:

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
HashMap aMap = new HashMap();

// Fill up the collection
for(int i=0; i<names.length; i++) {
    Team c = new Team(names[i]);
    aMap.put(names[i], c);
}
// Now print out the elements
Iterator it;
System.out.println("Here are the keys:");
it = aMap.keySet().iterator();
while (it.hasNext())
    System.out.println("   " + it.next());

System.out.println("Here are the values:");
it = aMap.values().iterator();
while (it.hasNext())
    System.out.println("   " + it.next());

System.out.println("Here are the key/value pairs:");
it = aMap.entrySet().iterator();
while (it.hasNext())
    System.out.println("   " + it.next());

Notice that there are only 4 keys, even though we added many items....this is because one key overwrites another when we call the put method more than once with the same key.

If we replace the HashMap with a TreeMap in the above code, the code still works, we just get the items in sorted ored according to the keys:
 

Here are the keys:    Al    Mel    Sally    Zack Here are the values:    The Al has 0 points and played 0 games.    The Mel has 0 points and played 0 games.    The Sally has 0 points and played 0 games.    The Zack has 0 points and played 0 games. Here are the key/value pairs:    Al=The Al has 0 points and played 0 games.    Mel=The Mel has 0 points and played 0 games.    Sally=The Sally has 0 points and played 0 games.    Zack=The Zack has 0 points and played 0 games.

Using WeakHashMap, you won't notice a difference.   We will not talk about this class further.
 

Here are two VERY useful ones:

• max(Collection coll)- returns the maximum element in the given collection
• min(Collection coll) - returns the minimum element in the given collection

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally"};
ArrayList aCollection = new ArrayList();
for(int i=0; i<names.length; i++)
    aCollection.add(names[i]);

Object max, min;
max = Collections.max(aCollection);
min = Collections.min(aCollection);
System.out.println("Max = " + max + ", Min = " + min);

Note that this will work as well if we had collections of wrapper class objects such as Integers.   But what about arbitrary objects ?  How does Java know how to compare arbitrary objects for max and min ?   For example, what if we had stored Team objects in the ArrayList:

      for(int i=0; i<names.length; i++)
          aCollection.add(new Team(names[i]));

If we try to find the max or min this way, we get a ClassCastException.  This is because Java assumes that for the max and min methods to work (as well as many other Collections class methods), the objects in the collection MUST implement the Comparable  interface which is defined as follows:

public interface Comparable {
    public int compareTo(Object o);
}

public class Team implementsComparable {
    ...
}

• sign(x.compareTo(y)) == -sign(y.compareTo(x)) for all x and y
• (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.
• x.compareTo(y)==0 implies that sign(x.compareTo(z)) == sign(y.compareTo(z)), for all z.
• (x.compareTo(y)==0) == (x.equals(y)).

public int compareTo(Object obj) {
    if (!(obj instanceof Team))
        throw new ClassCastException();
    Team t = (Team)obj;
    if (this.totalPoints() < t.totalPoints())
        return -1;
    if (this.totalPoints() > t.totalPoints())
        return 1;
    return 0;
}

public Team firstPlaceTeam() {
    return (Team)Collections.max(getTeams());
}
public Team lastPlaceTeam() {
    return (Team)Collections.min(getTeams());
}

public int compareTo(Object obj) {
    if (!(obj instanceof Team))
        throw new ClassCastException();
    return (totalPoints() - ((Team)obj).totalPoints());
}

public int compareTo(Object obj) {
    if (!(obj instanceof Team))
        throw new ClassCastException();
    return (getName().compareTo(((Team)obj).getName));
}

These are some more useful methods for re-organizing a list:

• reverse(List l)
• shuffle(List list)
• sort(List list) - returns a list containing the items in sorted order according to a specified Comparator

String[]  names = {"Al", "Zack", "Sally", "Al", "Mel", "Zack", "Zack", "Sally", "Jim", "Orson", "Ash"};
ArrayList aCollection = new ArrayList();
for(int i=0; i<names.length; i++)
    aCollection.add(names[i]);

System.out.println(aCollection);
Collections.reverse(aCollection);
System.out.println(aCollection);
Collections.shuffle(aCollection);
System.out.println(aCollection);
Collections.sort(aCollection);
System.out.println(aCollection);

Wow!   These sure are useful methods.   Guess what ?   The sort method requires that the objects all be comparable.  So, we can sort our Teams again according to the criteria specified in the implementation of the compareTo() method.

As you will see in a later course, searching a sorted list can be done much quicker by using a binary search rather than a linear search.  The following method allows you to search for a particular item (the key) in a sorted list (it assumes that the list has already been sorted previously).  It is actually VERY fast.   The method returns the index of the item within the list, unless it is not there, in which case -1 is returned.

• binarySearch(List list, Object key)

• copy(List dest, List src)
• fill(List dest, Object o)

• enumeration(Collection c)

• singleton(Object o)
• singletonList(Object o)
• singletonMap(Object key, Object value)