An introduction to the Java Collections API (List, Set, and SortedSet)

Overview

Programs must often maintain a single set of data to be acted upon in different ways. This, however, can be a challenge having no perfect solution.

For example, a program may need to maintain a single set of Customer objects. One processing requirement may be to loop through the entire set in order to calculate the total balance due for all accounts. Another requirement may be to find a particular Customer object based upon account number in order to change the customer's address. A third requirement may be to add a new, unique Customer object to the set. While Java provides two simple options for maintaining a set of Customer objects, each has its limitations:

1. An array could be used to hold the Customer objects. Arrays, however, have a fixed number of elements and cannot be expanded.

2. A Vector could be used to hold the Customer objects. A Vector is like an array but permits expansion. It would not, however, solve problems like converting a customer's account number into the index of the corresponding object or preventing duplicate Customer objects from being added.

Assuming that a compromise technique is chosen for maintaining a set of objects, what happens when a new processing requirement forces the program to use a different technique? How much code must be re-written? 

It is to address these types of problems that the Java Collections API (or framework) exists.

The Java Collections API

• Provides tools for maintaining a data container of objects (not to be confused with a GUI container of graphical components). To maintain a collection of primitive data, each primitive value must be wrapped in an object of its appropriate wrapper class (Boolean, Character, Integer, Double, etc.).

• Is an alternative to the creation of custom data structures

• Consists of several interfaces, and classes that implement those interfaces, within the java.util package

• Supports several kinds of collections which can be categorized by:

1. Whether or not the objects within the collection are to be maintained in a particular order. Such collections are said to be ordered. When an object is added to or removed from an ordered collection, the order is automatically maintained.

2. Whether or not the collection allows duplicate objects. If duplicates are not allowed, the collection will automatically reject an attempt to add an object that already exists.

3. Whether or not the collection maps a key to a particular object. Collections that map a key to an object provide a means of quickly locating the object. Such collections do not allow duplicate objects.

• Has several interfaces that indicate the overall behavior of the collection. The most commonly used collection interfaces are as follows:

Interface name	Ordered	Allows duplicates	Maps key to object
Collection	no	yes	no
List	yes	yes	no
Map	no	no	yes
Set	no	no	no
SortedMap	yes	no	yes
SortedSet	yes	no	no

• Has two iterator interfaces that indicate how objects may be serially retrieved from certain collections. The iterator interfaces are as follows:

Interface name	Usage
Iterator	A simple iterator for traversing and retrieving objects in the forward direction within a Set or SortedSet
ListIterator	A bi-directional iterator for traversing and retrieving objects in either the forward or backward direction within a List

An iterator maintains a pointer to a particular object within the collection. When the object is retrieved, the pointer is automatically moved. A complete traversal of the collection is called an iteration.

• Keeps the logical behavior of a collection separate from its internal data structure. The interfaces provide the programmer's view of the collection and say nothing about how objects within the collection are actually stored and retrieved. As a programmer, you don't need to know. Such details are left to the implementing classes (to be covered shortly).

Program

<->

Implementing Class   Interface (Logical Behavior)   Internal Data Structure

<->

Objects

Separating the logical behavior of a collection from its internal data structure reduces program maintenance. If a different internal structure is needed to satisfy some new processing requirement, the implementing class can simply be swapped for another class that implements the same interface.

The Collection interface

• Is the root interface for most of the Java collections hierarchy. It is extended by the List, Set, and SortedSet interfaces, but not by the Map or SortedMap interfaces.

• Has no direct implementing class in the Java. Its required methods, however, are defined by classes that implement the List, Set, and SortedSet interfaces (to be covered shortly). This results in a uniformity of features throughout much of the collections API. 

The Iterator interface

• Provides for the one-way traversal of a Set or SortedSet collection (forward only)

• Has several required methods but the most frequently used are:

Method	Usage
hasNext()	Returns true if the iteration has more elements
next()	Returns the next element in the iteration (as a generic Object)

The precise meaning of these methods varies depending upon the type of collection. Consult the Java API documentation for more details.

The ListIterator interface

• Extends the Iterator interface to provide for the two-way traversal of a List collection (forward and backward)

• Has several required methods but the most frequently used are:

Method	Usage
hasNext()	Returns true if this list iterator has more elements when traversing the list in the forward direction
hasPrevious()	Returns true if this list iterator has more elements when traversing the list in the backward direction
next()	Returns the next element in the list (as a generic Object)
previous()	Returns the previous element in the list (as a generic Object)

Consult the Java API documentation for more details.

The Set interface

• Is an extension of the Collection interface

• Indicates the behavior of a collection of objects that is unsorted, does not map a key value to an object, and does not allow duplicate objects. Two objects obj1 and obj2 are deemed to be duplicates if

obj1.equals(obj2)

Any attempt to add a duplicate object will be rejected and a false value returned from the add() method (see below).

• Permits a single element to be null

• Has a number of required methods. The following are the most frequently used (all of which are inherited from the Collection interface):

Method	Usage
add()	Adds an object to the collection
clear()	Removes all objects from the collection
contains()	Returns true if a specified object is an element within the collection
isEmpty()	Returns true if the collection has no elements
iterator()	Returns an Iterator object for the collection which may then be used to retrieve an object
remove()	Removes a specified object from the collection
size()	Returns the number of elements in the collection

Many methods return a boolean value that indicates whether the operation was successful. Consult the Java API documentation for more details.

• Example: This program uses a Set implemented as a HashSet to store some String objects and read them back from the collection.

import java.util.*;

public class App {
  public static void main(String[] args) {

    // Use a Set implemented as a HashSet (the actual location of each
    // object will be determined by an internal algorithm).

    Set myObjects = new HashSet();

    // Loop to store String objects in the collection.

    for (int i = 1; i <= 5; i++) {
      myObjects.add(new String("This is object " + i));
    }

    // Display how many objects are in the collection.

    System.out.println("The collection has " + myObjects.size() + " objects");

    // Instantiate an Iterator and loop to display all the objects.

    Iterator pointer = myObjects.iterator();
    while (pointer.hasNext()) {
      System.out.println("\t" + (String) pointer.next());
    }
  }
}

Notes:

1. By importing the java.util package, it is easier to use the classes and interfaces of the Java Collections Framework.

2. Even though myObject is of the Set type (an interface) it is assigned the HashSet object. This is allowed because HashSet implements the Set interface. A programmer doesn't really need to know the internal storage techniques of a HashSet. For the curious, however, a "hashing" algorithm is used to determine the location of each object to be added to the collection. There is no order to the collection.

3. When an object is retrieved from the collection, it is retrieved as a generic Object and must be re-cast as a String.

4. When the program is run, notice that the collection is unordered (in keeping with Set behavior).

The SortedSet interface

• Is an extension of the Set interface

• Indicates the behavior of a collection of objects that is ordered, does not map a key value to an object, and does not allow duplicate objects. The objects within the collection are maintained in their ascending natural order. 

• Does not permit an element to be null

• Has many useful methods. The most frequently used are as follows (with those in red being methods that expand upon those of the inherited Set interface):

Method	Usage
add()	Adds an object to the collection
clear()	Removes all objects from the collection
contains()	Returns true if a specified object is an element within the collection
first()	Returns the first (lowest) element currently in this collection
isEmpty()	Returns true if the collection has no elements
iterator()	Returns an Iterator object for the collection which may then be used to retrieve an object
last()	Returns the last (highest) element currently in this collection
remove()	Removes a specified object from the collection
size()	Returns the number of elements in the collection

Many methods return a boolean value that indicates whether the operation was successful. Consult the Java API documentation for more details.

• Example: This program uses a SortedSet implemented as a TreeSet to store some String objects and read them back from the collection.

import java.util.*;

public class App {
  public static void main(String[] args) {

    // Use a SortedSet implemented as a TreeSet (which maintains the
    // collection in ascending element order).

    SortedSet myObjects = new TreeSet();

    // Loop to store String objects in the collection.

    for (int i = 1; i <= 5; i++) {
      myObjects.add(new String("This is object " + i));
    }

    // Display how many objects are in the collection.

    System.out.println("The collection has " + myObjects.size() + " objects");

    // Display the first and last objects.

    System.out.println("First object: " + (String) myObjects.first());
    System.out.println("Last object: " + (String) myObjects.last());

    // Instantiate an Iterator and loop to display all the objects.

    Iterator pointer = myObjects.iterator();
    while (pointer.hasNext()) {
      System.out.println("\t" + (String) pointer.next());
    }
  }
}

Notes:

1. The TreeSet class implements both the SortedSet and Iterator interfaces and maintains its objects in ascending order within the collection.

2. When the program is run, notice that the collection is ordered (in keeping with SortedSet behavior).

The List interface

• Is an extension of the Collection interface

• Indicates the behavior of a collection of objects that is ordered, does not map a key value to an object, and allows duplicate objects. Even though the interface does not map key values, the user has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements within the list.

• Permits one or more elements to be null

• Has many useful methods. The most frequently used are as follows (with those in red being methods that expand upon those of the inherited Collection interface):

Method	Usage
add()	Adds an object to the collection
clear()	Removes all objects from the collection
contains()	Returns true if a specified object is an element within the collection
get()	Returns the element at the specified index position in this collection
isEmpty()	Returns true if the collection has no elements
listIterator()	Returns a ListIterator object for the collection which may then be used to retrieve an object
remove()	Removes the element at the specified index position in this collection
size()	Returns the number of elements in the collection

Many methods return a boolean value that indicates whether the operation was successful. Consult the Java API documentation for more details.

• Example: This program uses a List implemented as a LinkedList to store some String objects and read them back from the collection.

import java.util.*;

public class App {
  public static void main(String[] args) {

    // Use a List implemented as a LinkedList (which maintains the
    // collection as a two-way list with each object pointing to
    // both the previous and next object).

    List myObjects = new LinkedList();

    // Loop to store String objects in the collection.

    for (int i = 1; i <= 5; i++) {
      myObjects.add(new String("This is object " + i));
    }

    // Display how many objects are in the collection.

    System.out.println("The collection has " + myObjects.size() + " objects");

    // Instantiate a ListIterator and use loops to display all
    // the objects in both the forward and backward directions.

    ListIterator pointer = myObjects.listIterator();
    System.out.println("Reading forward:");
    while (pointer.hasNext()) {
      System.out.println("\t" + (String) pointer.next());
    }
    System.out.println("Reading backward:");
    while (pointer.hasPrevious()) {
      System.out.println("\t" + (String) pointer.previous());
    }
  }
}

Notes:

1. The LinkedList class implements both the List and ListIterator interfaces and maintains its objects as a two-way linked list in which each object has a pointer to both the next and the previous object within the collection.

2. The ListIterator allows for reading objects from the collection in both the forward and backward directions.

3. The implementing class can be changed to Vector or ArrayList and the program run the same. The internals of how the collection is stored, however, will be different. The choice of which implementation to use depends on many factors (such as how much the collection may grow and how many insertions and deletions are anticipated).

Lab exercise for Ferris students

E-mail your answers to this assignment no later than the due date listed in the class schedule.

Review questions

1. Which of the following can be used to instantiate a one-way, ordered collection?  (choose two)

1. Set stuff = new HashSet();

2. Set stuff = new TreeSet();

3. SortedSet stuff = new TreeSet();

4. SortedSet stuff = new HashSet();

5. List stuff = new Vector();

2. Which of the following permit an element within the collection to be a null object reference?  (choose three)

1. List

2. SortedSet

3. Set

4. HashSet

5. TreeSet

3. Which of the following permit duplicate elements within a collection?  (choose three)

   1. List

   2. SortedSet

   3. Set

   4. LinkedList

   5. Vector

4. Assume that a collection contains Customer objects and that x is the reference for a ListIterator. Which one of the following statements correctly retrieves the Customer object that precedes the one currently pointed to within the collection and assigns it to a Customer object reference named current?

1. current = x.previous();

2. current = (Customer) x.previous();

3. current = x.next();

4. current = (Customer) x.next();

5. x.previous(Customer);