Iterating over Collections

Often we will want to be able to iterate over an abstract data type -- like a stack -- but we will want to do so in a way the doesn't betray anything about the particular implementation of that abstract data type.

A convenient way to do this is through the use of a "for-each" loop. Suppose we want to be able to iterate over the items of a stack of strings, printing each string as it is visited. Some code that can accomplish this -- provided the Stack class supports it -- can be seen below.

Stack<String> collection = new Stack<String>();
...
for (String s : collection)
   System.out.println(s);
}

We often read this code in the following way: "for each string s in the collection, print s". Being able to type a for loop in this way is actually a bit of "syntactic sugar" provided to us by the compiler. In truth, the following code is what is really being executed in it's place:

Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {                       
    String s = iterator.next();
    System.out.println(s);
}

More generally, suppose Adt is any abstract data type that represents a collection of items of generic type, and we have defined a variable named collection to be a reference to an Adt object using the type Item:

Adt<Item> collection = new Adt<Item>();
Then, the code on the left below is equivalent to the code on the right:

for (Item item : collection) {
    // do something with item
}


Iterator<Item> iterator = collection.iterator(); 
while (iterator.hasNext()) {                       
    Item item = iterator.next();
    // do something with item
}

Returning to the idea the the stack or abstract data type in question must support this type of for-each loop -- one might notice in the above code that our abstract data type class must have a method named iterator(). To this end, we require the abstract data type class implements the Iterable interface, seen below:

public interface Iterable<Item> {
  Iterator<Item> iterator();
}

Further, since the iterator() method must return something of type Iterator, we must also have connected in some way to the abstract data type class, a class that implements the Iterator interface, which for reference is given below:

public interface Iterator<Item> {
   boolean hasNext();
   Item next();
   void remove();  // <-- you might want to avoid using this method (i.e., don't even define it) 
                   //     as it mixes iteration with alteration of the ADT
                   //     Fortunately, this is legal, as it has a default implementation.
}

Note, by creating the class that implements the Iterator interface as an inner class, we can easily provide access to the instance fields and methods of the outer abstract data type class.