Generic Programming with Collection<T>

Suppose you want one method that prints every item in a collection, no matter how that collection is stored. This article starts with the code that solves that problem, then explains the mechanism behind it. Read the code below first. The variable coll is assumed to be a collection of Strings. Do not worry yet about why each line is needed. Notice only how the loop is structured: it asks the iterator whether anything is left, takes one item, and does something with it.

Each familiar storage form has its own way of being walked. An array is walked with a for loop over its indices. A linked list is walked with a while loop that moves a pointer from node to node. A binary tree is walked with a recursive subroutine that performs an inorder traversal. Because collections can take these and many other forms, a method written for one form cannot simply be reused for another. A loop written for array indices does not describe how to visit the nodes of a tree.

The solution this course uses is the iterator. An iterator is an object whose job is to traverse a collection. Each collection type supplies its own iterator internally, so the details differ from one type to another. What stays constant is how you call the iterator. Once you learn that calling pattern, the same loop shape works for any collection that provides an iterator. The difference between a linked list walk and a tree walk is hidden inside the iterator, and the loop you write never has to see it.

A helpful way to picture an iterator is as a cursor that sits between items. It starts before the first item. Each call to next() moves the cursor forward past one item and hands that item back to you. Because of this, next() both reads and advances. The interface offers no way to peek at an item without consuming the step. Every look at an item is also a step forward.

The diagram shows the cursor after one call to next(). The item red has been returned, and the cursor now sits before null. The next call to next() will return null and advance past it. The remove() method, when available, deletes the item most recently returned by next(). That is why the cursor position matters: remove() always refers to the item just behind the cursor, not the item ahead of it.

The Iterator interface is parameterized, written Iterator<T>, where T is the type of the items. If a collection implements Collection<T> for some type T, then calling coll.iterator() returns an Iterator<T> with that same T. The interface defines exactly three methods, and each one plays a different role in the loop. The first two form the traversal itself, and the third changes the collection during that traversal.

The diagram below shows the order of calls on each pass through the loop. Read it from top to bottom. The collection is asked for an iterator exactly once, before the loop begins. After that, the loop alternates between asking whether items remain and asking for the next one. The removal step is optional, so it appears only on passes where you choose to delete an item.

Two details are easy to miss in the diagram. First, the hasNext() and next() pair repeats once for every item, which is why the loop runs as many times as there are items. Second, the loop never touches the collection's internal storage. Everything it needs passes through the iterator. That is the reason the same loop shape works for arrays, linked lists, and trees alike.

The same general form can be used for other kinds of processing. Suppose the goal is to remove every null value from a collection of Color objects. The removal is performed through the iterator, using iter.remove(), rather than by changing the collection directly during the walk. The source notes that this works as long as the collection supports removal. The following version is an original illustration of that pattern using the same loop shape.