Iteration

The interface Collection<T> defines some basic generic algorithms, but the situation may arise where you want to write your own, eg: to print out every item in a collection. To accomplish you would need some way of going through an arbitrary collection, accessing each item in turn. It is simple enough to do this for specific data structures:

  • array: use a for loop to iterate through all the array indices
  • linked list: use a while loop to advance a pointer along the list
  • binary tree: use a recursive function to carry out an inorder traversal

All of these, and many others, are collections. Can we devise a single generic method that will work for collections that are stored in dramatically different forms. The solution is to use iterators, objects that can be used to traverse a collection. Different types of collections implement iterators in different ways, but all iterators serve the same purpose. An algorithm that uses an iterator to traverse a collection is generic, since the same technique can be applied to any type of collection.

The interface Collection<T> defines a method for obtaining an iterator for any collection. If coll is a collection, then coll.iterator() returns an iterator that can be used to traverse it. The iterator acts as a pointer that starts at the beginning of the collection and moves along the collection from one item to the next. Iterators are defined by a parameterized interface named Iterator<T>, so if coll implements the interface Collection<T> for some specific type T, then coll.iterator() returns an iterator of type Iterator<T>, with the same type T as its type parameter. The interface Iterator<T> defines just three methods. If iter refers to an object that implements Iterator<T>, then we have:

  • iter.next() – returns the next item, and advances the iterator. The return value is of type T. This method lets you look at one of the items in the collection. There is no way to look at an item without advancing the iterator past that item. If this method is called when no items remain, it will throw a NoSuchElementException.
  • iter.hasNext() – returns a boolean value indicating whether there are more items to be processed. Youshould test this before calling iter.next().
  • iter.remove() – if you call this after calling iter.next(), it will remove the item that you just saw from the collection. This method has no parameter. It removes the item that was most recently returned by iter.next(). This might produce an UnsupportedOperationException, if the collection does not support removal of items.

Using iterators, we can write code to print all the items in any collection. Suppose, for example, that coll is of type Collection<String>. In that case, the value returned by coll.iterator() is of type Iterator<String>, and we can say:


Iterator <String> iter;        // Declare the iterator variable.
iter = coll.iterator();        // Get an iterator for the collection.
while ( iter.hasNext() ) {
   String item = iter.next();  // Get the next item.
   System.out.println(item);
}

The same general form will work for other types of processing, eg: the following code will remove all null values from any collection of type Collection<JButton> as long as that collection supports removal of values:


Iterator <JButton> iter = coll.iterator();
while ( iter.hasNext() ) {
   JButton item = iter.next();
   if (item == null)
      iter.remove();
}

When Collection, Iterator, or any other parameterized type is used in actual code, they are always used with actual types such as String or JButton. 

An iterator is often used to apply the same operation to all the elements in a collection. Sometimes it is possible to avoid the use of iterators by using a for-each loop, eg: with enumerated types or with arrays. A for-each loop can also be used to iterate through any collection. For a collection coll of type Collection, a for-each loop takes the form:


for ( T x : coll ) {
   // for each object x, of type T, in coll
   // process x
}

Here, x is the loop control variable. Each object in coll will be assigned to x in turn, and the body of the loop will be executed for each object. Since objects in coll are of type T, x is declared to be of type T. For example, if namelist is of type Collection, we can print out all the names in the collection with:


for ( String name : namelist ) {
   System.out.println( name );
}

This for-each loop could be written as a while loop using an iterator, but the for-each loop is much easier to follow.

Next: Lists and Sets