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

Java Programming, Lecture Notes #1358

• Preface
• Preview
• Discussion and Sample Programs
• Summary
• What’s Next

The purpose of this miniseries is to help you learn the essential featuresof 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 separatebrowser window.  That will make it easier for you to scroll back andforth among the different listings while you are reading about them.

Supplementary material

I recommend that you also study the other lessons in my extensive collectionof online Java tutorials.  You will find those lessons published atGamelan.com. However, as of the date of this writing, Gamelan doesn’t maintain a consolidatedindex of my Java tutorial lessons, and sometimes they are difficult tolocate there.  You will find a consolidated index atBaldwin’sJava Programming Tutorials.

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

• interfaces
• implementations
• algorithms

The previous two lessons provided a general discussion of the purpose ofthe interfaces, implementations, and algorithms in the Collections Framework. This lesson takes that discussion further and illustrates the use of thecorecollection interfaces.

The Java Collections Framework defines six core interfaces, in two distincttrees.  You will learn the names and the inheritance structure ofthose interfaces.  You will also learn about their purpose. You will see how the interfaces declare polymorphic methods that applyto implementations of the interfaces, and you will learn about the optionalmethods of the Collection interface.

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

What output does the program in Listing 1 produce?

• A.  Compiler Error
• B.  Runtime Error
• C.  44321 44321
• D.  12344 12344
• E.  1234 44321
• F.  1234 4321
• D.  None of the above.

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 Ap401class 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 Workerclass 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 populatorListing 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 corecollection interfaces in the Java Collections Framework.  Thatpurpose is to allow collections to be manipulated without regard for howthe collections are implemented.

Multiple list implementations

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

TreeSet and ArrayList

A collection of type TreeSet and a collection of type ArrayListare instantiated in the program in Listing 1.  Each of the collectionsis viewed as being of the interface type Collection.  A methodnamed 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 differentin each of the two cases, with the final contents of each collection beingdetermined by the respective behavior of the add() method for thattype of collection.

The fillIt() method

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

The method named fillIt() receives an incoming reference to acollection object as type Collection.  The method invokes theadd()method on the incoming reference five times in succession to add five elementsto the collection.  These elements are added without regard for theactual 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 populatorListing 2

The fillIt() method will be used to populate two collectionsof 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 loopListing 3

The code in Listing 3 instantiates an object of type TreeSet,and passes that object’s reference to the fillIt() method as typeCollection. As described above, the fillIt() method adds five elements to thecollection, 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 collectionand uses the iterator to display the contents of the collection.

TreeSet object is type SortedSet

The TreeSet class implements one of the core collection interfacesnamed SortedSet.  SortedSet is a sub interface of Set. One of the characteristics of a Set object is that it doesn’t allowduplicate elements.  One of the characteristics of a SortedSetobject is that it maintains its elements in ascending order.  Sincethe TreeSet class implements both of these interfaces, it is botha Set and a SortedSet, and exhibits the characteristics ofboth interfaces.

Because the underlying structure of the TreeSet class doesn’tallow duplicates, and the underlying structure maintains its elements inascending order, the code in Listing 3 produces the following text on thescreen:

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 loopListing 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 thesame values as before to the collection.  The added elements are referencesto Integer objects encapsulating the same values as were earlieradded to the TreeSet collection.  Although they are physicallydifferent objects, the result is that essentially the same data is addedto both collections.

Display the collection’s contents

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

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

44321

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

The important point

The important point is that although the fillIt() method invokesthe 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 TreeSetobject (type SortedSet), the duplicate element was eliminated, andthe 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 ArrayListobject (type List), all five elements, including the duplicate elementwere stored in the collection.  Furthermore, they were stored andlater retrieved in the same order in which they were added.

Structure of core the interfaces

Interestingly, the core collection interfaces in the Java CollectionsFramework 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 relationshipamong the interfaces.

• Collection
• Set
• SortedSet
• List
• Map
• SortedMap

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 andthe other rooted by Map.  According to The Java Tutorial fromSun, “a Map is not a true Collection.”  I will have more tosay about this in a future lesson.

Some operations are optional

Every class that implements an interface in the tree rooted in Collectionis 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.  (Seethe list of optional modification methods for the Collection interfacebelow.)

According to the contract for the CollectionsFramework, if a given implementation doesn’t support a specific modificationmethod, it must throw an UnsupportedOperationException.  Theauthor of the implementation is responsible for providing documentationthat identifies the optional operations that the implementation does anddoes not support.  (I have read that this approach has been thesource of some controversy within the Java community, but I haven’t pursuedthat controversy in any detail.)

Support for optional operations

This should not be an issue unless you are eitherdefining your own implementation, or using an implementation defined bysomeone other than the programmers at Sun.  As of JDK 1.3, all ofthe general-purpose implementations from Sun support all of the optionaloperations.

Optional Collection operations

The following list shows the optional operationsin the Collection interface as of JDK 1.3.  Each of these methodshas the ability to modify the contents of the collection.

• add()
• addAll()
• clear()
• remove()
• removeAll()
• retainAll()

Optional Map operations

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

• clear()
• put()
• putAll()
• remove()

Many methods are not optional

In both cases, the interface declares numerousother methods that are not optional.  Generally, the non-optionalmethods don’t have the ability to modify the collection.  For example,theget() method of the Map interface is not optional. Although theget() method receives an incoming key and returnsthe value to which the key maps, the method doesn’t have the abilityto modify the contents of the collection.

• interfaces
• implementations
• algorithms

The Java Collections Framework defines six core interfaces, in two distincttrees.  One tree is rooted in Collection and the other is rootedin Map.

The basic purpose of the core interfaces is to make it possible forcollections 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 ofdifferent types, the behavior of the method is likely to be different foreach collection.  However, in each case, that behavior will be appropriatefor 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 optionalinsofar as being supported by implementing classes.  The optionalmethods all have the ability to modify the contents of the collection. Those implementing classes that don’t support an optional method must throwan UnsupportedOperationException if that method is invoked on anobject 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 thecollection.

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

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

About the author

Richard Baldwinis a college professor and private consultant whose primary focus is acombination of Java and XML. In addition to the many platform-independentbenefits of Java applications, he believes that a combination of Java andXML will become the primary driving force in the delivery of structuredinformation on the Web.

Richard has participated in numerous consulting projects involvingJava, XML, or a combination of the two.  He frequently provides onsiteJava and/or XML training at the high-tech companies located in and aroundAustin, Texas.  He is the author of Baldwin’s Java Programming Tutorials,which has gained a worldwide following among experienced and aspiring Javaprogrammers. He has also published articles on Java Programming in JavaPro magazine.

Richard holds an MSEE degree from Southern Methodist University andhas many years of experience in the application of computer technologyto real-world problems.

baldwin.richard@iname.com