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

Section 16.7 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.

Subsection 16.7.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>.

Let’s reconsider the ArrayList class, which was introduced in Chapter 9. The ArrayList<E> class, which is part of the Java collections framework, has a generic type implementation in Java 5.0. The ArrayList class contains the methods listed in Figure 16.7.1 for storing and retrieving objects, and for accessing objects by their index position within the ArrayList.

Figure 16.7.1. Public methods in the `ArrayList` 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 ArrayList<E> object for storing String objects.

Activity 16.7.1.

Run the following code. Try adding more elements to the ArrayList. How would you get out the last element of the ArrayList?

In effect, the <E> serves as parameter for the type of objects that will be stored in the ArrayList. One benefit that a generic type provides is type checking of method arguments at compile time. If strList is a ArrayList<String> object, then the statement strList.add(new Integer(57)); will generate a compile-time error. By contrast, if strList was just a plain ArrayList 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.

Subsection 16.7.2 The `java.util.Stack<E>` class

The Java collections framework includes the Stack<E> class, implemented as a subclass of the Vector<E> class which has been replaced by the ArrayList<E> class. It contains the methods shown in Figure 16.7.2. For the most part, its methods provide the same functionality as the methods we developed earlier in this chapter.

Figure 16.7.2. The `java.util.Stack<E>` class.

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 ArrayList<E> code.

Activity 16.7.2.

Run the code below. Try pushing more items to the stack and popping two items.

Exercises Self-Study Exercise

1.

Modify the code to use the parameterized java.util.Stack<E> class instead of the Stack class we defined in the earlier sections.

Hint.

Subsection 16.7.3 The `List<E>` interface and the `LinkedList<E>` class

The java.util.LinkedList<E> is an implementation of a linked list (Figure 16.7.3). 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

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

/**
  * testList() creates a list of PhoneRecord objects using the
  * LinkedList constructor and then prints out that list. 
  */
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

Listing 16.7.4. A method that demonstrates the interface List<E> and the class LinkedList<E>.

Activity 16.7.3.

Run the code below. Try adding a new PhoneRecord to the linked list.

import java.util.*;

public class LinkedListOfPhoneRecords {

/**
  * testList() creates a list of PhoneRecord objects using the
  * LinkedList constructor and then prints out that list. 
  */
 public static void testList() {
   List<PhoneRecord> theList = new LinkedList<PhoneRecord>();
   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
  
  public static void main( String argv[] ) {
    testList();
  } // main
} // LinkedListOfPhoneRecords

/** The PhoneRecord class
* Description: Contains a single name and phone number.
* This version of the class implements comparable.
*/
class PhoneRecord implements Comparable{
    private String name;
    private String phone;

/**
    * PhoneRecord constructor
    * Creates an object containing the name and number.
    * @param aName is a person's name.
    * @param aPhone is a phone number for aName.
    */
    public PhoneRecord(String aName, String aPhone){
        name = aName;
        phone = aPhone;
    } // PhoneRecord() constructor

/**
    * toString() overides the toString() of the Object class.
    * @return is a String with this object's name and number.
    */
    public String toString(){
        return name + " " + phone;
    } // toString()

/**
    * getName returns the value of the name variable
    * @return name.
    */
    public String getName(){
        return name;
    } // getName()

/**
    * getPhone returns the value of the phone variable
    * @return phone.
    */
    public String getPhone(){
        return phone;
    } // getPhone()

/**
    * equals() overides the equals() of the Object class.
    * @param ob is a PhoneRecord object.
    * @return is true if the name variable of the two
    * PhoneRecord objects are equal as Strings.
    */
    public boolean equals(Object ob){
        return name.equals(((PhoneRecord)ob).getName());
    } // equals()

/**
    * compareTo() implements the Comparable interface.
    * @param ob is a PhoneRecord object.
    * @return is -1, 0, or +1 if the name variable of
    * this PhoneRecord object is less, equal, or greater
    * than ob.name as Strings. 
    */
     public int compareTo(Object ob){
        return name.compareTo(((PhoneRecord)ob).getName());
    } // compareTo()

/**
    * hashCode() overides hashCode() of the Object class.
    * @param ob is a PhoneRecord object.
    * @return is the hashCode() value of name as a String.
    */
    public int hashCode(){
        return name.hashCode();
    } // hashCode()

} // PhoneRecord

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

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

Principle 16.7.5. 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.

You have attempted of activities on this page.

Prev Top Next