16.5: From the Java Library: The Java Collections Framework and Generic Types

THE JAVA CLASS LIBRARY

contains implementations of some abstract data types. The Java utility package, java.util.*, contains a good number of classes and interfaces designed to facilitate storing and manipulating groups of objects. This family of related interfaces and classes is called the Java collections framework. It contains structures that correspond to the ADTs that we have just discussed, plus other data structures. Java 5.0 has reimplemented the Java collections framework using generic types that allow a programmer to specify a type for the objects that are stored in the structure.

16.5.1 Generic types in Java

Generic types

Declaring classes that use the generic type construct introduced in Java 5.0 generic types involves using new syntax to refer to the class name. Such classes and interfaces, including those in the collections framework, use angle brackets containing one or more variables (separated by commas) to refer to unspecified type names. For example, you would use <E> or <K, V> to refer to unspecified type names. Thus, names of classes or interfaces implemented with generic types are written with the syntax ClassName<E>.

Figure 16.28: The java.util.- Vector class is implemented with a generic type in Java 5.0.

Let’s reconsider the Vector class, which was introduced in Chapter 9. The Vector class, which is part of the Java collections framework, has a generic type implementation in Java 5.0. Figure 16.28 describes the Vector<E> class. Notice that the E refers to an unspecified type name, that is, the name of a class or interface. This type is specified when a corresponding variable is declared. The type must also be included after a constructor’s type name when an object is instantiated and assigned to the variable. The following code demonstrates how to create a Vector<E> object for storing String objects.

Vector<String> strVec = new Vector<String>();

strVec.addElement("alpha");

strVec.addElement("beta");

String str = strVec.elementAt (0);

In effect, the <E> serves as parameter for the type of objects that will be stored in the Vector. Java 5.0 still allows the use of the unparameterized Vector class which is equivalent to instantiating a Vector<Object> object. If you use a Vector object, the above code would be written as follows.

Vector strVec = new Vector();

strVec.addElement(”alpha”);

strVec.addElement(”beta”);

String str = (String)strVec.elementAt (0);

 

One benefit a generic type provides is type checking of method arguments at compile time. If strVec is a Vector<String> object, then the statement 

strVec.addElement(new Integer(57));

 

will generate a compile-time error. By contrast, if strVec was just a plain Vector object, no error would be found at compile time. Thus, if a programmer wishes to create an array of String objects, using generic types will help guarantee that the objects being stored are actually of type String. In this way, using generic types helps to reduce the number of programming errors and thereby makes programs safer and more robust.

A second benefit of using generic types is that the return type of objects retrieved from the data structure will be of the specified type rather than of type Object. If you compare the last statement in each of the two code segments above, you can see that using a generic type eliminates the need to cast an Object to a     . This is a big convenience for the programmer, because forgetting to cast objects from one type to another is a common programming error.

The java.util.Stack<E> class

Figure 16.29: The java.util.- Stack<E> class is a subclass of Vector<E>.

The Java collections framework includes the Stack<E> class, implemented as a subclass of the Vector<E> class. It contains the methods shown in Figure 16.29. For the most part, its methods provide the same functionality as the methods we developed earlier in this chapter. Note that the methods provide the functionality of a stack ADT but the details of its implementation are hidden from the user. An object of this class can be declared, instantiated, and used in a manner like the Vector<E> code.

Stack<String> stk = new Stack<String>();

stk.push("alpha");

stk.push("beta");

String str = stk.pop();

SELF-STUDY EXERCISE

Exercise 16.11

Write a class with only a main() method that modifies Figure 16.23 so that it uses the parameterized java.util.Stack<E> class instead of the Stack class used there.

16.5.2 The List<E> interface and the LinkedList<E> class

Figure 16.30: The LinkedList<E> class implements the List<E> interface. Only a partial list of methods are shown.

The java.util.LinkedList<E> is an implementation of a linked list (Fig. 16.30). Like our implementation earlier in this chapter, it contains methods that can be used to define the standard stack and queue methods.

Many of the standard list-processing methods are defined as part of the java.util.List<E> interface. The advantage of defining list operations as an interface is that they can be implemented by a number of data structures. Code for using the list methods can be written to work independently of the data structure being used.

For example, the collections framework contains LinkedList<E> and ArrayList<E>, both of which implement the List<E> interface. In this section, we will demonstrate how to make appropriate use of the List<E> interface and data structures that implement it.

Suppose that a programmer is developing an application to track activity of employees working at a small company’s phone-in help desk. The programmer has decided to use the LinkedList<E> data structure to store objects of the PhoneRecord class that was defined earlier in this chapter and will use methods of the List<E> interface to manipulate the data. A list seems to be an appropriate structure for this problem since

• An unknown (but relatively small) amount of data will be involved.
• The company wants the data stored in the order it is generated.
• The main use of the data will be to print out the list’s phone records.

The programmer might write a short method like that in Figure 16.31 to demonstrate how the List<E> and LinkedList<E> structures will be used.

Figure 16.31: A method that demonstrates the interface List<E> and the class LinkedList<E>.

Note that the statement

List <PhoneRecord> theList = new LinkedList<PhoneRecord>();

declares a variable theList of interface type List<E> but assigns an object of class type LinkedList<E>.This is appropriate because the class implements the interface and the code uses only methods from the interface. The class ArrayList<E> in the collections framework also implements the List<E> interface. It uses an array rather than a linked list to store elements and has a constructor with an int parameter that sets the size of the array. If the programmer knew that theList would contain close to, but always less than, 100 elements, then it might be better to declare:

List<PhoneRecord> theList = new ArrayLis t <PhoneRecord> (100);

The for–each loop

Also note the unusual looking for loop at the end of the method. This is a new feature of Java 5.0 which can be used to simplify the coding of loops that iterate through every object in a collection of objects. The statement

for (PhoneRecord pr : theList) {***}

should be thought of as executing the enclosed statements for each PhoneRecord object, pr, in the theList data structure. In previous versions of Java, an interface named Iterator had to be used to enumerate all the elements in a collection. The Iterator approach is more flexible — for example, it allows you to iterate through just some of the members of the collection— and will therefore still have to be used for more complex loops.

The output of the method will be:

Roger M 090−997−2918

Jane M 090−997−1987

Stacy K 090−997−9188

Gary G 201−119−8765

J ane M 090−997−1987

In the next section we will examine two other structures in the collections framework, the Set interface and the Map interface.

JAVA EFFECTIVE DESIGN

Code Reuse.

Given the relative difficulty of writing correct and efficient list-processing algorithms, applications that depend on lists should make use of library classes whenever possible.