Data Structures in Java: Part 5, The Core Collection Interfaces

The Java Collections Framework defines six core interfaces, in two distinct trees.  Learn the inheritance structure, and the purpose of those interfaces.  Learn how the interfaces declare polymorphic methods that apply to implementations of the interfaces, and learn about the optional methods of the Collection interface.
 

Published:  July 2, 2001
By Richard G. Baldwin

Java Programming, Lecture Notes # 1358


Preface

This is the fifth lesson in a miniseries on Java data structures and the Java Collections Framework.  The first lesson in the miniseries was entitled Data Structures in Java: Part 1, Getting Started.  The previous lesson was entitled Data Structures in Java: Part 4, Purpose of Implementations and Algorithms.

The purpose of this miniseries is to help you learn the essential features of Object-Oriented data structures in Java using the Collections Framework.

Viewing tip

You may find it useful to open another copy of this lesson in a separate browser window.  That will make it easier for you to scroll back and forth among the different listings while you are reading about them.

Supplementary material

I recommend that you also study the other lessons in my extensive collection of online Java tutorials.  You will find those lessons published at Gamelan.com.  However, as of the date of this writing, Gamelan doesn't maintain a consolidated index of my Java tutorial lessons, and sometimes they are difficult to locate there.  You will find a consolidated index at Baldwin's Java Programming Tutorials.

The index on my site provides links to the lessons at Gamelan.com.

Preview

In an earlier lesson, you learned that at least three things are included in a collections framework: The previous two lessons provided a general discussion of the purpose of the interfaces, implementations, and algorithms in the Collections Framework.  This lesson takes that discussion further and illustrates the use of the core collection interfaces.

The Java Collections Framework defines six core interfaces, in two distinct trees.  You will learn the names and the inheritance structure of those interfaces.  You will also learn about their purpose.  You will see how the interfaces declare polymorphic methods that apply to implementations of the interfaces, and you will learn about the optional methods of the Collection interface.

Discussion and Sample Programs

Illustration of core collection interfaces

Letís begin this lesson with a little quiz.  Take a look at the program shown in Listing 1 and see if you can answer the following question.

What output does the program in Listing 1 produce?

import java.util.TreeSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Ap401{
  public static void main(
                        String args[]){
    new Worker().doIt();
  }//end main()
}//end class Ap401

class Worker{
  public void doIt(){
    Collection ref = new TreeSet();
    Populator.fillIt(ref);
    Iterator iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop
    System.out.print(" ");
    
    ref = new ArrayList();
    Populator.fillIt(ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop
    System.out.println();
  }//end doIt()
}// end class Worker

class Populator{
  public static void fillIt(
                       Collection ref){
    ref.add(new Integer(4));
    ref.add(new Integer(4));
    ref.add(new Integer(3));
    ref.add(new Integer(2));
    ref.add(new Integer(1));
  }//end fillIt()
}//end class populator

Listing 1

If you selected the following answer, then you are correct.

E.  1234 44321

The program in Listing 1 illustrates the basic purpose of the core collection interfaces in the Java Collections Framework.  That purpose is to allow collections to be manipulated without regard for how the collections are implemented.

Multiple list implementations

For example, there is more than one way to implement a list.  Two common ways involve arrays and linked structures.  If two lists are implemented in different ways, but both satisfy the requirements of the core collection interfaces, they can each be manipulated the same way regardless of the details of their implementation.

TreeSet and ArrayList

A collection of type TreeSet and a collection of type ArrayList are instantiated in the program in Listing 1.  Each of the collections is viewed as being of the interface type Collection.  A method named add() is used to populate each collection with the same values.

Behavior is different but appropriate

The behavior of the add() method is appropriate, and different in each of the two cases, with the final contents of each collection being determined by the respective behavior of the add() method for that type of collection.

The fillIt() method

The code in the fragment shown in Listing 2 defines a class method named fillIt() of the class named Populator.  This is a class of my own design intended solely to illustrate the primary point of this program.

The method named fillIt() receives an incoming reference to a collection object as type Collection.  The method invokes the add() method on the incoming reference five times in succession to add five elements to the collection.  These elements are added without regard for the actual type or underlying implementation of the collection (in fact, as the method is written, it has no way of knowing the underlying implementation).
 
class Populator{
  public static void fillIt(
                       Collection ref){
    ref.add(new Integer(4));
    ref.add(new Integer(4));
    ref.add(new Integer(3));
    ref.add(new Integer(2));
    ref.add(new Integer(1));
  }//end fillIt()
}//end class populator

Listing 2

The fillIt() method will be used to populate two collections of different types with the same data.

Create and populate a TreeSet object

Consider the code fragment shown in Listing 3.
 
    Collection ref = new TreeSet();
    Populator.fillIt(ref);
    Iterator iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop

Listing 3

The code in Listing 3 instantiates an object of type TreeSet, and passes that object's reference to the fillIt() method as type Collection.  As described above, the fillIt() method adds five elements to the collection, in random order with two of the elements being duplicates.

Display the collection's contents

Then the code in Listing 3 gets an Iterator object on the collection and uses the iterator to display the contents of the collection.

TreeSet object is type SortedSet

The TreeSet class implements one of the core collection interfaces named SortedSet.  SortedSet is a sub interface of Set.  One of the characteristics of a Set object is that it doesn't allow duplicate elements.  One of the characteristics of a SortedSet object is that it maintains its elements in ascending order.  Since the TreeSet class implements both of these interfaces, it is both a Set and a SortedSet, and exhibits the characteristics of both interfaces.

Because the underlying structure of the TreeSet class doesn't allow duplicates, and the underlying structure maintains its elements in ascending order, the code in Listing 3 produces the following text on the screen:

1234

Create and populate an ArrayList object

Now consider the code fragment shown in Listing 4.
 
    ref = new ArrayList();
    Populator.fillIt(ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop

Listing 4

The code in Listing 4 instantiates a new collection of type ArrayList, and passes that object's reference to the same fillIt() method, again as type collection.

The code in the fillIt() method adds five elements having the same values as before to the collection.  The added elements are references to Integer objects encapsulating the same values as were earlier added to the TreeSet collection.  Although they are physically different objects, the result is that essentially the same data is added to both collections.

Display the collection's contents

Then, as before, the code in Listing 4 gets an iterator and uses it to access and display the contents of the ArrayList collection.

The ArrayList class implements the List interface, which does not prohibit duplicate elements, and does not maintain its elements in sorted order.  Therefore, in this case, the following text was displayed:

44321

All five element values are displayed, including the duplicate, in the order in which they were added to the list.

The important point

The important point is that although the fillIt() method invokes the same method name (add()) on each of the collection objects, the behavior of that method is different in each case.  In both cases, the behavior is appropriate for the underlying data structure.  Furthermore, the underlying data structure isn't even known to the fillIt() method.

No duplicate elements in ascending order

In the first case, where the underlying data structure was a TreeSet object (type SortedSet), the duplicate element was eliminated, and the elements were stored so as to be accessible in ascending order.

Duplicates allowed with no sorting

In the second case, where the underlying data structure was an ArrayList object (type List), all five elements, including the duplicate element were stored in the collection.  Furthermore, they were stored and later retrieved in the same order in which they were added.

Structure of core the interfaces

Interestingly, the core collection interfaces in the Java Collections Framework do not all extend from a common root interface.

Rather, the inheritance structure of the core interfaces is shown below.  Indentation is used to indicate the superinterface-subinterface relationship among the interfaces.

A Map is not a true Collection

As you can see, that there is no common root interface.  Rather, there are two distinct trees, one rooted by Collection and the other rooted by Map.  According to The Java Tutorial from Sun, "a Map is not a true Collection."  I will have more to say about this in a future lesson.

Some operations are optional

Every class that implements an interface in the tree rooted in Collection is not required to support all of the modification methods (operations) declared in the Collection interface.

Rather, the modification methods (operations) in the Collection interface are designated optional.  (See the list of optional modification methods for the Collection interface below.)

According to the contract for the Collections Framework, if a given implementation doesn't support a specific modification method, it must throw an UnsupportedOperationException.  The author of the implementation is responsible for providing documentation that identifies the optional operations that the implementation does and does not support.  (I have read that this approach has been the source of some controversy within the Java community, but I haven't pursued that controversy in any detail.)

Support for optional operations

This should not be an issue unless you are either defining your own implementation, or using an implementation defined by someone other than the programmers at Sun.  As of JDK 1.3, all of the general-purpose implementations from Sun support all of the optional operations.

Optional Collection operations

The following list shows the optional operations in the Collection interface as of JDK 1.3.  Each of these methods has the ability to modify the contents of the collection.

Optional Map operations

As of JDK 1.3, the following list shows the optional operations in the Map interface.  Each of these methods has the ability to modify the contents of the map.

Many methods are not optional

In both cases, the interface declares numerous other methods that are not optional.  Generally, the non-optional methods don't have the ability to modify the collection.  For example, the get() method of the Map interface is not optional.  Although the get() method receives an incoming key and returns the value to which the key maps, the method doesn't have the ability to modify the contents of the collection.

Summary

A collections framework contains the following: The Java Collections Framework defines six core interfaces, in two distinct trees.  One tree is rooted in Collection and the other is rooted in Map.

The basic purpose of the core interfaces is to make it possible for collections to be manipulated without regard for how they are implemented, so long as the implementation satisfies the contracts of the interfaces.

When the same method name is invoked on references to collections of different types, the behavior of the method is likely to be different for each collection.  However, in each case, that behavior will be appropriate for the type of collection object on which the method is invoked.  This is polymorphic behavior.

Six of the methods declared in the Collection interface are optional insofar as being supported by implementing classes.  The optional methods all have the ability to modify the contents of the collection.  Those implementing classes that don't support an optional method must throw an UnsupportedOperationException if that method is invoked on an object of the class.

Many methods declared in the Collection interface are not optional.  Generally, the non-optional methods don't have the ability to modify the collection.

All of the general-purpose implementation classes of the Collection interface in JDK 1.3 support all of the optional methods.

What's Next?

In the next lesson, I will discuss and illustrate some of the details of the core interfaces and the general-purpose implementations in the Java Collections Framework. For example, I will discuss the difference between a set and a list.  I will also discuss the difference between ordered and sorted.  I will discuss the fact that additional stipulations are applied as you progress down the framework interface hierarchy.  In order to help you learn and retain the material, I will provide a couple of short quizzes.


Copyright 2000, Richard G. Baldwin.  Reproduction in whole or in part in any form or medium without express written permission from Richard Baldwin is prohibited.

About the author

Richard Baldwin is a college professor and private consultant whose primary focus is a combination of Java and XML. In addition to the many platform-independent benefits of Java applications, he believes that a combination of Java and XML will become the primary driving force in the delivery of structured information on the Web.

Richard has participated in numerous consulting projects involving Java, XML, or a combination of the two.  He frequently provides onsite Java and/or XML training at the high-tech companies located in and around Austin, Texas.  He is the author of Baldwin's Java Programming Tutorials, which has gained a worldwide following among experienced and aspiring Java programmers. He has also published articles on Java Programming in Java Pro magazine.

Richard holds an MSEE degree from Southern Methodist University and has many years of experience in the application of computer technology to real-world problems.

baldwin.richard@iname.com

-end-