CHAPTER 4

The Java Collections Framework

CHAPTER OBJECTIVES

1. Understand what a collection is, and how contiguous collections differ from linked collections.
2. Be able to create and manipulate parameterized collections.
3. Identify several of the methods in the Collection interface.
4. Describe a design pattern in general, and the iterator design pattern in particular.
5. Compare the ArrayList and LinkedList implementations of the List interface.
6. Be able to utilize boxing/unboxing and the enhanced for statement.

4.1 Collections

A collection is an object that is composed of elements. The elements can be either values in a primitive type (such as int) or references to objects. For a familiar example, an array is a collection of elements, of the same type, that are stored contiguously in memory. Contiguous means "adjacent," so the individual elements are stored next to each other¹. For example, we can create an array of five string elements (strictly speaking, each element is a reference to a String object) as follows:

String [ ] names = new String [5];

Here the new operator allocates space for an array of five String references, (each initialized to null by the Java Virtual Machine), and returns a reference to the beginning of the space allocated. This reference is stored in names.

There is an important consequence of the fact that arrays are stored contiguously: an individual element in an array can be accessed without first accessing any of the other individual elements. For example, names [2] can be accessed immediately—we need not access names [0] and names [1] first in order to reach names [2]. This random access property of arrays will come in handy in several subsequent chapters. In each case we will need a storage structure in which an element can be accessed quickly given its relative position, so an array will be appropriate in each case.

There are several drawbacks to arrays. First, the size of an array is fixed: Space for the entire array (of primitive values or references) must be allocated before any elements can be stored in the array. If that size is too small, a larger array must be allocated and the contents of the smaller array copied to the larger array.

Another problem with arrays is that the programmer must provide all the code for operating on an array. For example, inserting and deleting in an array may require that many elements be moved. Suppose an array's indexes range from 0 to 999, inclusive, and there are elements stored in order in the locations at indexes 0 to 755. To insert an element into the location with index 300, we must first move the elements at indexes 300 to 755 into the locations at indexes 301 to 756. Figure 4.1 shows the effect of such an insertion.

FIGURE 4.1 Insertion in an array: to insert "Kalena" at index 300 in the array on the left, the elements at indexes 300, 301,…, 756 must first be moved, respectively, to indexes 301, 302,…, 757

In your programming career up to now, you have had to put up with the above disadvantages of arrays. Section 4.1.1 describes an alternative that is almost always superior to arrays: instances of collection classes.

4.1.1 Collection Classes

Most of what we will do from here on involves collection classes. A collection class is a class in which each instance is a collection of elements, and each element is (a reference to) an object. For example, a string object can be an element, or a FullTimeEmployee object can be an element. Values in a primitive type are not objects, so we cannot create an instance of a collection class in which each element is of type int. But for each primitive type, there is a corresponding class, called a wrapper class, whose purpose is to enable a primitive type to be represented by (that is, wrapped inside) a class. For example, there is an Integer class, and we can create an Integer object from an int j as follows:

new Integer (j)

The new operator returns a reference to an Integer object. Table 4.1 provides several important conversions.

Table 4.1Some Important Conversion Formulas

int i;
Integer myInt;
String s;
Object obj;

The Java Collections Framework includes a number of collection classes that have wide applicability. All of those collection classes have some common methods. For example, each collection class has an isEmpty method whose method specification is:

/**
 * Determines if this collection has no elements.
 *
 * @return true - if this collection has no elements.
 *
 */
public boolean isEmpty()

Suppose myList is an instance of the collection class ArrayList, and myList has four elements. The execution of

System.out.println (myList.isEmpty());

will produce output of

false

Of course, a method specification does not indicate how the method's task will be accomplished. In subsequent chapters, we will investigate some of the details for several collection classes. But we can now introduce a simple classification of collection classes according to the way the elements are stored.

4.1.2 Storage Structures for Collection Classes

Instances of a collection class usually consume memory in proportion to the number of elements in the collection. So the way such a collection is stored in memory can have a substantial impact on the space efficiency of a program. One straightforward way to store a collection instance in memory is to store, in an array, a reference to each element in the collection. That is, an array could be a field in the collection class.

Such a class is called a contiguous-collection class. For example, the ArrayList class in Chapter 6 has an array field, and (a reference to) each element in an ArrayList instance is stored in that instance's array. So ArrayList is a contiguous-collection class. We will study contiguous-collection classes in Chapters 6, 8 and 13. For many applications of contiguous-collection classes, the random-access feature of an array is a great asset.

What about the disadvantages, cited earlier, of an array: the size of an array is fixed, and the programmer is responsible for writing all the code that works with the array? With a contiguous-collection class, those are problems for the developer of the class, not for users of the class. Basically, the developer of a contiguous collection class writes the code—once—for methods that manipulate the array. Any user of that collection class simply invokes the appropriate methods for the given application. The user may not even be aware that there is an array field in the class, and by the Principle of Data Abstraction, would not rely on that field anyway.

You probably have not appreciated the random access feature of arrays. That's because you have probably not yet seen an alternative to arrays for storing a collection of elements in memory. We now briefly describe a structure that competes with the array for storing the elements in a collection object.

Instead of a contiguous relationship, the elements are related by links. A link is another name for a reference. Basically, each element is housed in a special object called an entry (sometimes called a node). Within each entry object there will be at least one link to another entry object. In a linked-collection class, the elements in each instance are stored in entries. Figures 4.2-4.4 show parts of three linked collections.

We will explore linked collections in Chapters 7, 10, 12, 14 and 15.

FIGURE 4.2 Part of a linked collection—a singly-linked list—in which each entry contains an element and a reference to the next entry in the linked collection

FIGURE 4.3 Part of a linked collection—a doubly-linked list —in which each entry contains an element, a reference to the previous entry and a reference to the next entry

4.2 Some Details of the Java Collections Framework

In this section we present a little more information about the Java Collections Framework. The Java Collections Framework consists of a thoroughly tested assortment of interfaces and classes. The classes represent widely used data structures and algorithms. For most applications in which a collection is needed, the framework provides the appropriate class. By utilizing the framework classes, you improve your productivity by not "re-inventing the wheel."

One of the impediments to understanding the framework is its sheer size; over 200 methods in the eight classes we will study. Fortunately, there is a lot of duplication. For example, as noted in Section 4.1.1, each of those classes has an isEmpty method. In fact, the definitions of many of the methods are the same in several classes. One of the unifying tools in the framework is the interface, which imposes method headings on implementing classes. Section 4.2.1 introduces another, similar unifying tool: the abstract class.

FIGURE 4.4 Part of a linked collection—a binary search tree—in which each entry contains an element and references to three other entries

4.2.1 Abstract Classes

An abstract class is a class that is allowed to have abstract methods as well as defined methods. The abstract methods must be defined in each subclass (unless the subclass is also abstract). Here is a bare-bones example of an abstract class:

public abstract class Parent
{
      /**
       * Returns the String object "I am".
       *
       * @returns "I am".
       *
       */
       public String getPrefix()
       {
            return "I am";
       } // method getPrefix


      /**
       * Returns a String object.
       *
       * @return a String object.
       *
       */
       public abstract String getClassName();


} // class Parent

An abstract class is denoted by the abstract modifier at the beginning of its declaration. And within an abstract class, each abstract method's heading must include the modifier abstract before the return type, and a semicolon after the method heading. Because the Parent class lacks a definition for one of its methods, we cannot instantiate the Parent class. That is, we cannot define a Parent object:

Parent p = new Parent  ();    // illegal because Parent is an abstract class

We can now declare two subclasses, Childi and Child2, of Parent.

public class Childi extends Parent
{
    /**
    *  Returns the String object  "Childi".
    *
    *  @return the String object  "Childi".
    *
    */
    public String getClassName()
    {
       return "Childi";
    }  // method getClassName

} // class Childi
public class Child2 extends Parent
{
    /**
    *  Returns the String object  "Child2".
    *
    *  @return the String object  "Child2".
    *
    */
    public String getClassName()
    {
        return "Child2";
    }  // method getClassName

} // class Child2

The main benefit of abstract methods is that they promote flexibility (defined methods may be, but need not be, overridden in subclasses) and consistency (abstract-class headings must be identical in subclasses). For example, we can now do the following:

Parent p;

int code;

// Get the value for code;
...

if  (code == i)
        p= new Childi();
else

        p= new Child2();
System.out.println (p.getPrefix() + p.getClassName());

The variable p is a polymorphic reference, so the version of getClassName called depends on the type—Child1 or Child2—of the object referenced by p. The output will be "I am Child1" or "I am Child2", depending on the value of the variable code.

The Java Collections Framework has quite a few abstract classes: AbstractCollection, AbstractList, AbstractSet, and others. Typically, one of these classes will declare as abstract any method whose definition depends on fields in the subclasses, and define any method whose definition does not depend on those fields.

For now, a practical application of abstract classes is developed in Lab 5.

Here are a few more details on the relationship between interfaces, abstract classes and fully defined classes:

1. If a class implements some but not all of the methods in an interface, then the class would have to be declared as an abstract class—and therefore cannot be instantiated.
2. An interface can extend one or more other interfaces. For example, we could have:

   public interface Container extends Collection,  Comparable
   {…

   Container has abstract methods of its own, and also inherits abstract methods from the interfaces Collection and Comparable.

3. A class can extend at most one other class; by default, the Object class is the superclass of every class. Multiple inheritance —the ability of a class to have more than one immediate superclass—is illegal in Java. Multiple inheritance is illegal because of the danger of ambiguity. For example, viewing a teaching assistant as both a student and an employee, we could have a TeachingAssistant class that is the immediate subclass of classes Student and StaffMember. Now suppose classes Student and StaffMember each has its own getHolidays() method. If we define:

   TeachingAssistant teacher = new TeachingAssistant();

   which getHolidays() method does teacher.getHolidays() invoke? There is no way to tell, and that is why Java outlaws multiple inheritance. C++ allows multiple inheritance, but complex rules and disambiguating language are needed to make it work.

4. A class can implement more than one interface. For example, we could have:

   class NewClass implements Interface1,  Interface2
   {…

This feature, especially when combined with feature 3, allows us to come close to achieving multiple inheritance. We can write:

class NewClass extends OldClass implements Interface1,  Interface2
{

There is no ambiguity when a method is invoked because any methods in an interface are abstract, and any non-final superclass method can be explicitly overridden —that is, re-defined—in the subclass. For example, suppose oldClass, Interface1, and Interface2 all have a writeOut() method, and we have

NewClass myStuff = new NewClass();

...

myStuff.writeOut();

Which version of the writeOut method will be invoked? Certainly not the version from Interface1 or Interface2, because those methods must be abstract. If NewClass implements a writeOut() method, that is the one that will be invoked. Otherwise, the version of writeOut defined in (or inherited by) OldClass will be invoked.

4.2.2 Parameterized Types

When collection classes were introduced in Section 4.1.1, we noted that the element type has to be a reference type: primitive types are not allowed. Starting with J2SE (that is, Java 2 Platform, Standard Edition) version 5.0, a class's element type can be specified, in angle brackets, when an instance of the class is declared. For example, suppose we want to declare and initialize an ArrayList object to hold a collection of grade point averages in which each grade point average will be stored as a Double. You don't have to know the details of the ArrayList class: You will learn some of those in Chapter 6. The declaration and initialization of the ArrayList object is as follows:

ArrayList <Double> gpaList = new ArrayList <Double>();

Only elements of type Double can be inserted into gpaList; an attempt to insert a String or Integer element will be disallowed by the compiler. As a result, you can be certain that any element retrieved from gpaList will be of type Double.

Let's see how elements can be inserted and retrieved from gpaList. In the ArrayList class, the add method inserts the element argument at the end of the ArrayList object. For example,

gpaList.add (new Double  (2.7));

will append to the end of gpaList a (reference to a) Double object whose double value is 2.7.

For retrievals, the get method returns the element in the ArrayList object at a specified index. So we can access the element at index 0 as follows:

Double gpa = gpaList.get  (0);

Notice that we don't need to cast the expression on the right-hand side to Double because the element at index 0 of gpaList must be of type Double.

Now suppose we want to add that grade point average to a double variable sum, initialized to 0.0. The method doubleValue() in the Double class returns the double value corresponding to the calling Double object. The assignment to sum is

sum = sum + gpa.doubleValue();

In this example, ArrayList<Double> is a parameterized type. A parameterized type consists of a class or interface identifier followed, in angle brackets, by a list of one or more class identifiers separated by commas. Typically, a parameterized type starts with a collection-class identifier, and the element type is enclosed in angle brackets. A parameterized type is sometimes called a "generic type", and the language feature permitting parameterized types is called "generics".

Parameterized collection classes improve your productivity as a programmer. You don't have to remember what the element type of a collection is, because that type is specified when the collection is declared, as we did with ArrayList<Double>. If you make a mistake and try to insert an element of type String for example, you will be notified at compile-time. Without parameterized types, the insertion would be allowed, but the assignment of (Double)gpaList.get(0) to gpa would generate a ClassCastException at run time. And this exception, if uncaught, could crash a critical program.

In the previous example, the conversions from double to Double and from Double to double are annoyances. To simplify your working with parameterized collection classes, the Java compiler automatically translates primitive values into wrapper objects: the technical term is boxing. For example, the insertion into gpaList can be accomplished as follows:

gpaList.add (2.7);         // instead of gpaList.add (new Double  (2.7));

Unboxing translates a wrapper object into its primitive value. For example, to increment the above double variable sum by the value of the Double object gpa, we simply write

sum = sum + gpa;    // instead of sum = sum + gpa.doubleValue();

Unboxing eliminates the need for you to invoke the doubleValue() method, and that makes your code easier to read.

The general idea behind parameterized types and boxing/unboxing is to simplify the programmer's work by assigning to the compiler several tasks that would otherwise have to be performed by the programmer.

Section 4.2.3 introduces the backbone of the Java Collections Framework: the Collection interface.

4.2.3 The Collection Interface

The Java Collections Framework consists basically of a hierarchy. There are interfaces and abstract classes at every level except the lowest, and the lowest level has implementations of interfaces and extensions of abstract classes. At the top of the hierarchy are two interfaces, Collection and Map.

In this section, we will focus on the Collection interface. For the sake of specificity, Figure 4.5 presents the Collection interface in UML notation, with the methods listed in alphabetical order. Don't worry if some of the method headings are puzzling to you (or make no sense at all). You will learn all you will need to know in subsequent chapters, when we look at implementations of the interface.

As indicated in Figure 4.5, the Collection interface has E—for "element"—as the type parameter. That is, E is replaced with an actual class, such as Double or FullTimeEmployee, in the declaration of an instance of any class that implements the interface. For example, part of the ArrayList heading is

public class ArrayList <E> implements Collection<E> …

Here is an instance of the ArrayList class with FullTimeEmployee elements:

ArrayList<FullTimeEmployee>employeeList = new ArrayList <FullTimeEmployee>();

In this example, FullTimeEmployee is the actual class of the elements: the class that replaces the type parameter E when the ArrayList class is instantiated.

FIGURE 4.5 The Collection interface. In UML, a type parameter—in this case, E—is shown in a dashed rectangle in the upper-right-hand corner of the interface or class

If you wanted to, you could create your own class that fully implements the Collection interface. That is, sort of, what happens in Lab 6. Only a few methods are realistically defined; the others just throw an exception. For example,

public int hashCode()
{
          throw new UnsupportedOperationException();
}

Such definitions satisfy the compiler, so the resulting class, ArrayCollection, is instantiable. That is, we can create and initialize an ArrayCollection object:

ArrayCollection<Integer> collection = new ArrayCollection<Integer>();

4.2.3.1 Iterators

The Collection interface provides a core of methods useful for applications. But each application will almost certainly have some specialized tasks that do not correspond to any method in the Collection interface. Important Note: In the following examples, "Collection object" is shorthand for "object in a class that implements the Collection interface", and "Collection class" is shorthand for "class that implements the Collection interface."

1. Given a Collection object of students, print out each student who made the Dean's List.
2. Given a Collection object of words, determine how many are four-letter words.
3. Given a Collection object of club members, update the dues owed for each member.
4. Given a Collection object of full-time employees, calculate the average salary of the employees.

Surely, we cannot create a class that would provide a method for any task in any application—the number of methods would be limitless. But notice that in each of the four examples above, the task entails accessing each element in a Collection object. This suggests that we need to allow users of a Collection class to be able to construct a loop that accesses each element in a Collection object. As we will see when we look at classes that implement the Collection interface, developers can straightforwardly construct such a loop. Why? Because a developer has access to the fields in the class, so the developer knows how the class is organized. And that enables the developer to loop through each element in the instance.

According to the Principle of Data Abstraction, a user's code should not access the implementation details of a Collection class. The basic problem is this: How can any implementation of the Collection interface allow users to loop through the elements in an instance of that class without violating the Principle of Data Abstraction? The solution is in the use of iterators. Iterators are objects that allow the elements of Collection objects to be accessed in a consistent way without accessing the fields of the Collection class.

Inside each class that implements the Collection interface, there is an iterator class that allows a user to access each element in the collection. Each iterator class must itself implement the following Iterator interface:

public interface Iterator<E>
{
      /**
       * Determines if this Iterator object is positioned at an element in
       * this Collection object.
       *
       * @return true - if this Iterator object is positioned at an element
       *          in this Collection object.
       *
       */
      boolean hasNext ();


      /**
       * Advances this Iterator object, and returns the element this
       * Iterator object was positioned at before this call.
       *
       * @return the element this Iterator object was positioned at when

       *          this call was made.
       *
       *  @throws NoSuchElementException - if this Iterator object is not
       *          positioned at an element in the Collection object.
       *
       */
       E next ();


      /**
       *  Removes the element returned by the most recent call to next().
       * The behavior of this Iterator object is unspecified if the underlying
       * collection is modified - while this iteration is in progress - other
       * than by calling this remove() method.
       *
       * @throws IllegalStateException - if next() had not been called
       *          before this call to remove(), or if there had been an
       *          intervening call to remove() between the most recent
       *          call to next() and this call.
       *
       void remove ();


} // interface Iterator<E>

For each class that implements the Collection interface, its iterator class provides the methods for traversing any instance of that Collection class. In other words, iterators are the behind-the-scenes workhorses that enable a user to access each element in any instance of a Collection class.

How can we associate an iterator object with a Collection object? The iterator() method in the Collection class creates the necessary connection. Here is the method specification from the Collection interface:

/**
 *  Returns an Iterator object over this Collection object.
 *
 *  @return an Iterator object over this Collection object.
 *
 */
Iterator<E> iterator( );

The value returned is (a reference to) an Iterator object, that is, an object in a class that implements the Iterator interface. With the help of this method, a user can iterate through a Collection object For example, suppose that myColl is (a reference to) an instance of a Collection object with String elements, and we want to print out each element in myColl that starts with the letter 'a'. We first create an iterator object:

Iterator<String> itr = myColl.iterator();

The variable itr is a polymorphic reference: it can be assigned a reference to an object in any class that implements the Iterator<String> interface. And myColl.iterator() returns a reference to an Iterator<String> object that is positioned at the beginning of the myColl object.

The actual iteration is fairly straightforward:

String word;
while (itr.hasNext ())
{
      word = itr.next();
      if (word.charAt (0) == 'a')
           System.out.println (word);
} // while

Incidentally, do you see what is wrong with the following?

// Incorrect!
while (itr.hasNext ())
      if (itr.next().charAt (0) == 'a')
               System.out.println (itr.next());

Because of the two calls to itr.next(), if the next word returned during a loop iteration starts with the letter 'a', the word after that word will be printed.

Very often, all we want to do during an iteration is to access each element in the collection. For such situations, Java provides an enhanced for statement (sometimes referred to as a for-each statement). For example, the previous (correct) iteration through myColl can be abbreviated to the following:

for (String word : myColl)
      if (word.charAt (0) == 'a')
              System.out.println (word);

The colon should be interpreted as "in", so the control part of this for statement can be read "For each word in myColl." The effect of this code is the same as before, but some of the drudgery—creating and initializing the iterator, and invoking the hasNext() and next() methods—has been relegated to the compiler.

Here is a complete example of iterating over a Collection object by using an enhanced for statement. You don't have to know the details of ArrayList class, the particular implementation of the Collection interface. You will learn those details in Chapter 6. For the sake of simplicity, ArithmeticException and InputMismatchException are caught in the same catch block.

// Calculates the mean grade-point-average

import java.util.*;

public class EnhancedFor
{
  public static void main  (String  [  ]  args)
  {
    new EnhancedFor().run();
  }  // method main

  public void run()
  {
    final double MIN_GPA = 0.0,

                 MAX_GPA = 4.0,
                 SENTINEL = -1.0;


    final String INPUT_PROMPT = "Please enter a GPA in the range" +
       " from " + MIN_GPA + " to " + MAX_GPA + ", inclusive (or " +
       SENTINEL + " to quit): ";


    final String RANGE_ERROR = "The grade point average must" +
       " be at least " + MIN_GPA + " and at most " + MAX_GPA + ".";


    final String MESSAGE = "
 nThe mean GPA is ";

    final String NO_VALID_INPUT = "

Error: there were no valid " +
       "grade-point-averages in the input.";


    ArrayList<Double> gpaList = new ArrayList<Double>();


    Scanner sc = new Scanner (System.in);


    double oneGPA,
           sum = 0.0;


    while (true)
    {
      try
      {
         System.out.print (INPUT_PROMPT);
         oneGPA = sc.nextDouble();
         if (oneGPA == SENTINEL)
            break;
         if (oneGPA < MIN_GPA || oneGPA > MAX_GPA)
            throw new ArithmeticException (RANGE_ERROR);
         gpaList.add (oneGPA); // inserts at end of gpaList
      } // try
      catch (Exception e)
      {
        System.out.println (e + "
");
        sc.nextLine();
      } // catch Exception
   } // while
   for (Double gpa : gpaList)
       sum += gpa;
   if (gpaList.size() > 0)
       System.out.println (MESSAGE +
                   (sum / gpaList.size()));
   else
      System.out.println(NO_VALID_INPUT);
  } // method run


} // class EnhancedFor

The enhanced for statement simplifies your code, and that makes your programs easier to understand. So you should use an enhanced for statement whenever possible, that is, if you were to use an iterator instead, the only iterator methods invoked would be hasNext() and next(). You cannot use an enhanced for statement if the collection may be modified during the iteration. For example, if you wanted to delete, from gpaList, each grade-point-average below 1.0, you would need to explicitly set up an iterator:

Iterator<Double> itr = gpaList.iterator();
while (itr.hasNext())
       if (itr.next() < 1.0)
                itr.remove();

4.2.3.2 Design Patterns

In Section 4.2.3.1, we stated a problem, namely, how can the developer of a Collection class allow users to loop through one of its instances without violating the Principle of Data Abstraction? The solution to the problem was to employ an iterator. As such, the use of iterators is an example of a design pattern: a generic programming technique that can be applied in a variety of situations. As we will see in subsequent chapters, the iterator pattern plays an important role in an assortment of applications.

Throughout the text, we will identify several design patterns and corresponding applications. The basic idea is that each design pattern provides you with a problem that occurs frequently and the outline of a solution. You may have to "tweak" the solution for a particular instance of the problem, but at least you will not be re-inventing the wheel.

In Section 4.2.4, we briefly introduce an extension of the Collection interface and three classes that implement that extension.

4.2.4 The List Interface

Java Collection Framework's List interface extends the Collection interface by providing some index-related methods. For example, there is a get method that returns the element at a given index. In any List object, that is, in any instance of a class that implements the List interface, the elements are stored in sequence, according to an index. For example, a List object pets might have the elements arranged as follows: "dog", "cat", "iguana", "gerbil", "cat". Here "dog" is at index 0, "gerbil" is at index 3. Duplicate elements are allowed: "cat" appears at index 1 and at index 4.

When viewed as a language-independent entity, a list is an abstract data type. Within Java, the List interface is abstract in the sense that it is not tied down to any particular implementation. In fact, in the Java Collections Framework, the List interface is not directly implemented. Instead, the abstract class AbstractList partially implements the List interface, and leaves the rest of the implementation to subclasses, namely, ArrayList and LinkedList. See Figure 4.6.

The ArrayList class implements the List interface with an underlying array², and the LinkedList class implements the List interface with the underlying linked structure shown in Figure 4.3. We will get to the details in Chapters 6 and 7, respectively. To give you an idea of some of the methods in both classes, the following class creates and manipulates a List of random Integer objects.

import java.util.*;

public class RandomList

{
  public static void main (String[ ] args)
  {
      new RandomList ().run();
  } // method main


  public void run()
  {
     final int SEED = 111;


     List<Integer> randList = new ArrayList<Integer>();


     Random r = new Random (SEED);


     // Insert 10 random integers, in the range 0...99, into randList:
     for (int i = 0; i < 10; i++)
             randList.add (r.nextInt(100));   // insertion


     // Print out randList:
     System.out.println (randList);


     // See if 22 is in randList:
     if (randList.contains (22))
             System.out.println ("Yes, 22 is in randList.");
     else
             System.out.println ("No, 22 is not in randList.");


     // Print out the Integer at index 3:
     System.out.println (randList.get (3) + "is at index 3");


     // Remove the Integer at index 6:
     randList.remove (6);


     // Insert a new random Integer at index 5:
     randList.add (5, r.nextInt (100));


     // Print out randList.
     System.out.println (randList);


     // Remove all even Integers:
     Iterator<Integer> itr = randList.iterator();
     while (itr.hasNext())
            if (itr.next() % 2 == 0)
                      itr.remove();


     // Print out randList;
     System.out.println (randList);
  } // method run


} // class RandomList

FIGURE 4.6 Part of the Java Collections Framework hierarchy dealing with the List interface. In UML, an abstract-class identifier is italicized

The line

System.out.println (randList);

is equivalent to

System.out.println (randList.toString());

The toString method returns a String representation of randList. Every class in the Java Collections Framework has a toString() method, so all the elements in an instance of one of those classes can be output with a single call to println.

Because an ArrayList object stores its elements in an underlying array, when the element at index 6 is removed, each element at a higher index is moved to the location at the next lower index. So the element that was at index 7 is then at index 6, the element that was at index 8 is then at index 7, and so on. When a new element is inserted at index 5, each element located at that index or higher is moved to the next higher index. So the element that was at index 5 is then at index 6, the element that was at index 6 is then at index 7, and so on.

The output is

[93, 70, 57, 97, 9, 20, 84, i2, 97, 65]
No,  22 is not in randList.
97 is at index 3

[93, 70, 57, 97, 9, 60, 20, 12, 97, 65]
[93, 57, 97, 9, 97, 65]

We could not use an enhanced for statement to iterate over randList because we needed to remove some of that object's elements, not merely access them.

In the program, randList is declared as a polymorphic reference and then immediately initialized as a reference to an ArrayList object. To re-run the program with a LinkedList object, the only change is the constructor call:

List<Integer> randList = new LinkedList<Integer>();

How do the two versions compare? Part of the program—printing the Integer at index 3—is executed more quickly with an ArrayList object because of the random-access ability of the underlying array. And part of it—removing all even Integer elements—is executed more quickly with a LinkedList object. That's because an entry in a linked list can be removed by adjusting links: no movement of elements is needed. In general, there is no "best" implementation of the List interface.

SUMMARY

A collection is an object that is composed of elements. The elements may be stored contiguously, that is, at consecutive locations in memory. Another option is a linked structure, in which each element is stored in a special object called an entry that also includes a reference to another entry.

A collection class is a class of which each instance is a collection. The Java Collections Framework, part of the package java.util, includes a number of collection classes that have wide applicability. Each of those classes can be parameterized, which means that the element class is specified when the collection-class object is created. And for any instance of one of those classes, an iterator can be defined. An iterator is an object that allows an instance of a collection class to loop through the elements in that class without violating the Principle of Data Abstraction.

To simplify the programmer's work of inserting elements into an instance of a parameterized class, Java automatically boxes primitive values into the corresponding wrapper elements. Similarly, wrapper elements retrieved from a parameter-class instance are automatically unboxed into the corresponding primitive value. A further simplification of Java is the enhanced for statement, which automates most of the routine code to access each element during an iteration.

The Collection interface consists of 15 method specifications for accessing and manipulating an instance of a class that implements the Collection interface.

The List interface adds several index-related methods to the Collection interface. The List interface is partially implemented by the AbstractList class, and fully implemented by the ArrayList and LinkedList classes.

CROSSWORD PUZZLE

CONCEPT EXERCISES

4.1 What is a collection? What is a collection class? What is a Collection class? Give an example of a collection that is not an instance of a collection class. Programming Project 4.1 has an example of a collection class that is not a Collection class.

4.2 An array is a collection, even though there is no array class. But an array of objects can be converted into an instance of the ArrayList class. Look in the file Arrays.java in the package java.util to determine the generic algorithm (that is, static method) that converts an array of objects into an ArrayList of those objects. How can that ArrayList then be printed without a loop?

4.3

1. Identify each of the following as either an interface or a class:

   Collection
   LinkedList
   Iterator
   AbstractList

2. What is the difference between an interface and an abstract class?
3. Of what value is an abstract class? That is, to what extent can an abstract class make a programmer more productive?

4.4 What is a list?

PROGRAMMING EXERCISES

4.1 For each of the following, create and initialize a parameterized instance, add two elements to the instance, and then print out the instance:

1. an ArrayList object, scoreList, of Integer objects;
2. a LinkedList object, salaryList, of Double objects;

4.2 Develop a main method in which two ArrayList objects are created, one with String elements and one with Integer elements. For each list, add three elements to the list, remove the element at index 1, add an element at index 0, and print out the list.

4.3 Find an ArrayList method, other than a constructor, that is not also a method in the LinkedList class. Find a LinkedList method, other than a constructor, that is not also a method in the ArrayList class.

4.4 Suppose we have the following:

LinkedList<String> team = new LinkedList<String>  ();
team.add ("Garcia");
Iterator<String> itr = team.iterator();
Integer player = itr.next  ();

What error message will be generated? When (at compile-time or at run-time)? Test your hypotheses.

4.5 Use the ArrayList class three times. First, create an ArrayList object, team1, with elements of type String. Add three elements to team1. Second, create team2, another ArrayList object with elements of type String. Add four elements to team2. Finally, create an ArrayList object, league, whose elements are ArrayList objects in which each element is of type String. Add team1 and team2 to league.

/**
 * Initializes this Sequence object to be empty, with an initial capacity of ten
 *  elements.
 *
 */
 public Sequence()


/**
 * Initializes this Sequence object to be empty, with a specified initial
 *  capacity.
 *
 * @param capacity - the initial capacity of this Sequence object.
 *
 *  @throw IllegalArgumentException - if capacity is non-positive.
 *
 */
 public Sequence (int n)


/**
 *  Returns the number of elements in this Sequence object.
 *
 *  @return the number of elements in this Sequence object.
 *
 */
 public int size()


/**
 * Appends a specified element to this Sequence object.
 *
 *  @param element - the element to be inserted at the end of this
 *         Sequence object.
 *
 */
 public void append (E element)


/**
 * Returns the element at a specified index in this Sequence object.
 * The worstTime(n) is constant, where n is the number of elements in this
 * Sequence object.
 *
 * @param k - the index of the element returned.
*
 *
 * @return the element at index k in this Sequence object.
 *
 *  @throws IndexOutOfBoundsException - if k is either negative or greater
 *          than or equal to the number of elements in this Sequence
 *          Sequence object.
 *
 */


 public E get (int k)


/**
 * Changes the element at a specified index in this Sequence object.
 * The worstTime(n) is constant, where n is the number of elements in this
 * Sequence object.
 *
 * @param k - the index of the element returned.
 * @param newElement - the element to replace the element at index k in
 *         this Sequence object.
 *
 *  @throws IndexOutOfBoundsException - if k is either negative or greater
 *          than or equal to the number of elements in this Sequence
 *          object.
 *
 */
 public void set (int k, E newElement)

protected E [ ] data;

protected int size; // the number of elements in the Sequence, not the // capacity of the data array

¹ Actually, all that matters is that, to a user of an array, the elements are stored as if they were contiguous, so an element can be accessed directly from its index.

² The Stack class also implements the List interface with an underlying array, but the definition of a stack severely restricts access to the array, so we will ignore the Stack class in this discussion.