Applied Design Patterns with Java

Behavioral :: Iterator (257) {C ch 19}

Intent
Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

As Known As
Cursor

Motivation
An aggregate object such as a list should have a way to access its elements without exposing its internal structure, and to traverse the list in different ways, but without bloating the interface with operations for different traversals. The Iterator pattern allows this. The key idea in this pattern is to take the responsibility for access and traversal out of the list object and put it into an Iterator object. The Iterator class defines an interface for accessing the list's elements. An Iterator object is responsible for keeping track of the current element; that is, it knows which elements have been traversed already. For example, a List class would call for a ListIterator with the following relationship between them:

Before instantiating ListIterator, supply the List instance to traverse, then access the list's elements sequentially. The CurrentItem operation returns the current element in the list, First initializes the current element to the first element, Next advances the current element to the next element, and IsDone tests whether traversal has advanced beyond the last element.

Separating the traversal mechanism from the List object allows defining Iterators for different traversal policies without enumerating them in the List interface. I.e.: FilteringListIterator might provide access only to those elements that satisfy specific filtering constraints. Note that the Iterator and the list are coupled, and the client must know that it is a list that's traversed as opposed to some other aggregate structure. Hence the client commits to a particular aggregate structure. It would be better to change the aggregate class without changing client code, by generalizing the Iterator concept to support polymorphic iteration.

As an example, consider a SkipList implementation of a list. A skiplist is a probabilistic data structure with characteristics similar to balanced trees. The code should work for both List and SkipList objects. Define an AbstractList class that provides a common interface for manipulating lists. Define an abstract Iterator class for a common iteration interface. Define concrete Iterator subclasses for the different list implementations. Thus, the iteration mechanism becomes logically independent of concrete aggregate classes; this is crucial to how the pattern works.


The remaining problem is how to create the Iterator. The code should be independent of the concrete List subclasses, so don't instantiate a specific class. Instead, make the list objects responsible for creating their corresponding Iterator. This requires an operation like CreateIterator through which clients request an Iterator object. CreateIterator is an example of a Factory Method (107). It is used here to let a client ask a list object for the appropriate Iterator, giving rise to two class hierarchies, one for lists and another for Iterators. The CreateIterator Factory Method "connects" the two hierarchies.

Catalog Behavioral Prev Next