Part 5: The Core Collection Interfaces
Data Structures in Java
By Richard Baldwin
The Java Collections Framework defines six core interfaces, in two
distinct trees. Learn the inheritance structure and the purpose of those
interfaces.
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:
- interfaces
- implementations
- algorithms
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
Lets 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?
- 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 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.
- add()
- addAll()
- clear()
- remove()
- removeAll()
- retainAll()
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.
- clear()
- put()
- putAll()
- remove()
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:
- interfaces
- implementations
- algorithms
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.
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. | 
