Section 16.6. From the Java Library: The Java Collections Framework and Generic Types

[Page 791 (continued)]

16.6. 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 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 stored in the structure.

java.sun.com/docs

16.6.1. Generic Types in Java

Declaring classes that use the generic type construct introduced in Java 5.0 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>.

Generic types

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. Note 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.

Figure 16.28. The java.util. Vector class is implemented with a generic type in Java 5.0. (This item is displayed on page 792 in the print version)

Vector<String> strVec = new Vector<String>(); strVec.addElement("alpha"); strVec.addElement("beta"); String str = strVec.elementAt(0); 

---

[Page 792]

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 code shown above 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 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 String. 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

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.

Figure 16.29. The java.util.Stack<E> class is a subclass of Vector<E>. (This item is displayed on page 793 in the print version)

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 much the same manner as the Vector<E> code.

---

[Page 793]

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.6.2. The List<E> Interface and the LinkedList<E> Class

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.

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

---

[Page 794]

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 the activities 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 because

• 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 the one 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>.

public static void testList() {    List<PhoneRecord> theList = new LinkedList<PhoneRecord>();    // new ArrayList?phonerecord?(); could also be used.    theList.add(new PhoneRecord("Roger M", "090-997-2918"));    theList.add(new PhoneRecord("Jane M", "090-997-1987"));    theList.add(new PhoneRecord("Stacy K", "090-997-9188"));    theList.add(new PhoneRecord("Gary G", "201-119-8765"));    theList.add(new PhoneRecord("Jane M", "090-997-1987"));    System.out.println("Testing a LinkedList List");    for (PhoneRecord pr : theList)       System.out.println(pr); } // testList() 

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 only uses 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 ArrayList<PhoneRecord>(100); 

---

[Page 795]

The unusual-looking for loop at the end of the method is a new feature of Java 5.0 that simplifies the coding of loops that iterate through every object in a collection of objects. The statement

The for--each loop

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 flexiblefor example, it allows you to iterate through just some of the members of the collectionand 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 Jane 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.

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.