[ Data Structures with Java ] Section 12.1 : The Iterator Concept

Preface : 
Applications use a collection object to store elements dynamically. At points in the application, there is a need to identify the objects that are currently being stored. The ability to scan the elements in a collection is key to many data structures algorithms. The task is made simple and efficient for an ArrayList collection that can use the get() and set() methods to access and update an element by index. This allows for an array-like scan of the elements. A LinkedList collection implements List and so has access to the same get() and set() methods. In this case, however, the methods have running time O(n) and so a scan of all of the elements is very inefficient. 

Guidelines for scanning elements in Collection : 
The Bag class poses a different problem. Our discussion of that class focused on operations to add and remove elements but did not provide tools to scan the collection. We would have to modify the implementation to make the data visible. The Bag class stores the elements in a fixed-length array. By making the bagArr and the size variable bagSize public, we could use an index to scan the elements in the range 0 to bagSize-1. The strategy works at the price of exposing the underlying storage structure, which violates the principle of information hiding. The problem promises to be even more difficult with set and map collections that store elements by value in a tree or a hash table. Even if the data was public, scanning the elements would require very different algorithms and notation. 
The design of a collection type must address the problem of scanning its elements. We can identify a clear set of guidelines that should apply : 
- Guideline 1 : 

A collection must define an efficient scanning mechanism consist with good object-design principles. Requiring the implementation to make the data public is not a solution. The mechanism should follow a design pattern so that general scanning algorithms apply to all collection types.

- Guideline 2 : 

A collection should provide an object, call it an iterator, that has methods which allow a scan of a collection similar to the scan of an array with an index.The object type of an iterator should implement an iterator pattern that can be uniformly used with all collections. While there can be different designs, methods should allow for a loop to scan the elements sequentially. For instance, a design may view elements in a collection as a sequence over the range from begin() to end() and provide methods to initialize and update an iterator. In this case, the following would be a loop that scans the elements :

view plaincopy to clipboardprint?

1. // scan elements in collection c with the iterator iter  
2. for(iter = c.begin(); iter != c.end(); iter.goNext)   
3.     iter.getValue();  

- Guideline 3 : 

Each collection class is responsible for implementing iterator methods on the basic of its storage strategy. After all, the collection class understands its storage strategy and so should be responsible for scanning the data.

Modern research in data structures evolved the concept of an iterator that meets these three guidelines. Languages such as C++ and Java employ different object-oriented design approaches to implement iterators and a different way to specify the operations. In the next section, we will introduce the Java Collections approach to iterators. The Iterator interface defines methods associated with an Iterator. 

Supplement : 
* [OO 設計模式] Iterator Pattern : 反覆器/迭代器