[ Data Structures with Java ] Section 12.2 : Collection Iterators

Preface : 
An iterator is an object that accesses the elements in a collection. You can think of it as a "locator" that scan across the entire range of elements in the collection. At any point in the scan, the iterator can access the value of the corresponding element. The below figure illustrates an iterator for a LinkedList object. In (a), the iterator, called iter, references the first element in the list with Integer value 8. In (b), iter has moved forward one position and references Integer value 17. 
 
The generic Interator interface defines the methods that are available to an iterator. Every data structure that implements the Collection interface implements Itarator and provides a method that creates an iterator and positions it at an element in the collection. In a program, we typically create an object by using the operator new and a class constructor. Creating an iterator is a different process. It must be done by method iterator() which is specified in the Collection interface. The method returns an iterator object that references the first element in the collection. The meaning of "first" depends on the collection type and the way it stores elements. For a List collection, the iterator is initially set to reference the element at position 0. 
Create an iterator by first declaring an Iterator reference variable. Then call iterator() for the specific collection that you wish to traverse. For instance, the following statements create an iterator that scans a linked list of integers : 

view plaincopy to clipboardprint?

1. LinkedList aList;   // LinkedList for Integer objects  
2. Iterator iter;        // Iterator for Integer objects  
3. iter = aList.iterator();           // create iterator ; assign to iter  

You cannot create an iterator using operator new. The iterator is not an independent object. Rather, it must be associated with a particular collection because it references the elements in the collection. It makes sense that the collection object should assume the responsibility of creating the iterator because the object knows how it stores the elements and can specify a first element. 
Note: A factory method is a name for a method that instantiates objects. Like a factory, the job of a factory method is to manufacture objects. For more, you can reference here. 

The Iterator Scan Methods : 
An iterator has a series of methods that allow it to scan a collection from its first to its last element and to access each element during the scan. The methodhasNext() specifies wehter the iterator has additional elements to visit. A programmer normally uses the method in a while-loop statement as below : 

view plaincopy to clipboardprint?

1. // continue while there are remaining elements  
2. while(iter.hasNext()) {  
3. ...  
4. }  

The method hasNext() has value true whether the iteration has more elements to scan and the value false when the iteration has completed the scan of all the elements. 
The actual scanning of the list is done by the method next(), which returns the value of next element in the list and moves the iterator forward one position. The method serves a dual purpose. It provides access to the current element referenced by the iterator and then advances the iterator. An attempt to call next() when hasNext() is false results in a NoSuchElementException. 
The following figure illustrates the action that occurs when calling next() with an iterator that currently references the second element in the list. The method first extracts the value Integer 17 from the list, moves the iterator to the third element, and then returns the value : 
 

By combining a statement that initializes an iterator with a while statement that uses hasNext() and next(), we have a template for a forward scan of a list : 

view plaincopy to clipboardprint?

1. // initialize iter to reference the first element in the list  
2. iter = aList.iterator();  
3.   
4. // loop accesses successive elements to the end of the list  
5. while(iter.hasNext()) {  
6.     // obtain the next value and move forward  
7.     value = iter.next();  
8. }  

An Iterator object also has a remove() method that deletes an element while traversing the collection. The problem is to understand which element is deleted. Before executing remove(), the program must have made a prior call to next(). The call accesses the value at the current iterator position and then advances the iterator. It is the accessed value that is deleted by the iterator remove() method. In effect, remove() delete the previous element. A second element cannot be removed by the iterator until there has been an intervening call to next(). In other words, the iterator remove() method must work in tandem with the iterator next() method. 
The figure below illustrates the remove() method. Initially, the iterator references the second element (Integer 17). After a call to next(), the iterator moves forward, and the original element is the target for the remove() operations : 
 

Generic Iterator Methods : 
Iterators provide another mechanism for generic programming. Any collection class that implements the Collection interface must include iterators. The collection object an employ an iterator to scan the elements. An algorithm that relies on traversing elements in a collection and extracting their values can be implemented as a generic method using an iterator. 
The method max() is a good example. It returns the value of the largest element in a collection. A generic form of the method includes a parameter of generic type Collection and returns a value of the specified type. Any collection whose elements implement Comparable can call max() : 

- 函式 max() Implementation :

view plaincopy to clipboardprint?

1. public static extends Comparablesuper T>> T max(Collection c) {  
2.     if(c.isEmpty()) return null;  
3.     Iterator iter = c.iterator();  
4.     T tmpValue = null, maxValue = null;  
5.     while(iter.hasNext()) {  
6.         if(maxValue == null){  
7.             maxValue = iter.next();  
8.             continue;  
9.         } else {  
10.             tmpValue = iter.next();  
11.             maxValue = tmpValue.compareTo(maxValue)>0 ? tmpValue : maxValue;   
12.         }  
13.     }  
14.     return maxValue;  
15. }  

Iterating with an enhanced for Statement : 
In many applications, you use an iterator to scan a collection solely for the purpose of accessing the elements. The "enhanced for" statement ("foreach" statement) makes the compiler take care of the iterator for you. It short-circuits the need to declare an iterator object and use methods hasNext() and next() to access successive elements in the collection. Below is a code with a foreach statement that scans a LinkedList of colors (strings) and outputs the names with length < 5 : 

- Foreach sample code to print out the content of a Collection list :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     String[] colors = {"green", "red", "yellow", "teal", "black"};  
3.     LinkedList list = new LinkedList();  
4.     for(int i=0; i
5.     for(String str: list) {  
6.         if(str.length()<5) {  
7.             System.out.println(str+" ");  
8.         }  
9.     }  
10. }  

A collection class must implement the generic interface Iterable in order to use the enhanced for statement to scan the elements. The interface does not define any methods. It simply allows an object to be the target of the foreach statement. All of the collection classes in this book implement Iterable.