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

  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.

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

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.

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

 

The Iterator interface

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

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

obj1.equals(obj2)

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

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.

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

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.

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

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.

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();

  1. Set stuff = new TreeSet();

  2. SortedSet stuff = new TreeSet();

  3. SortedSet stuff = new HashSet();

  4. List stuff = new Vector();

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

  1. List

  1. SortedSet

  2. Set

  3. HashSet

  4. TreeSet

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

    1. List

    1. SortedSet

    2. Set

    3. LinkedList

    4. Vector

  1. 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);