Iterator
In any container, you must have a way to insert elements and fetch them out again. After all, that’s the primary job of a container—to hold things. In a List, add( ) is one way to insert elements, and get( ) is one way to fetch elements.
If you want to start thinking at a higher level, there’s a drawback: You need to program to the exact type of the container in order to use it. This might not seem bad at first, but what if you write code for a List, and later on you discover that it would be convenient to apply that same code to a Set? Or suppose you’d like to write, from the beginning, a piece of general-purpose code that doesn’t know or care what type of container it’s working with, so that it can be used on different types of containers without rewriting that code?
The concept of an Iterator (another design pattern) can be used to achieve this abstraction. An iterator is an object whose job is to move through a sequence and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence. In addition, an iterator is usually what’s called a lightweight object: one that’s cheap to create. For that reason, you’ll often find seemingly strange constraints for iterators; for example, the Java Iterator can move in only one direction. There’s not much you can do with an Iterator except:
1. Ask a Collection to hand you an Iterator using a method called iterator( ). That Iterator will be ready to return the first element in the sequence.
2. Get the next object in the sequence with next( ).
3. See if there are any more objects in the sequence with hasNext( ).
4. Remove the last element returned by the iterator with remove( ).
To see how it works, we can again use the Pets tools from the Type Information chapter:
//: holding/SimpleIteration.java import typeinfo.pets.*; import java.util.*; public class SimpleIteration { public static void main(String[] args) { List<Pet> pets = Pets.arrayList(12); Iterator<Pet> it = pets.iterator(); while(it.hasNext()) { Pet p = it.next(); System.out.print(p.id() + ":" + p + " "); } System.out.println(); // A simpler approach, when possible: for(Pet p : pets) System.out.print(p.id() + ":" + p + " "); System.out.println(); // An Iterator can also remove elements: it = pets.iterator(); for(int i = 0; i < 6; i++) { it.next(); it.remove(); } System.out.println(pets); } } /* Output: 0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster 0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 8:Cymric 9:Rat 10:EgyptianMau 11:Hamster [Pug, Manx, Cymric, Rat, EgyptianMau, Hamster] *///:~
With an Iterator, you don’t need to worry about the number of elements in the container. That’s taken care of for you by hasNext( ) and next( ).
If you’re simply moving forward through the List and not trying to modify the List object itself, you can see that the foreach syntax is more succinct.
An Iterator will also remove the last element produced by next( ), which means you must call next( ) before you call remove( ).4
This idea of taking a container of objects and passing through it to perform an operation on each one is powerful and will be seen throughout this book.
Now consider the creation of a display( ) method that is container-agnostic:
//: holding/CrossContainerIteration.java import typeinfo.pets.*; import java.util.*; public class CrossContainerIteration { public static void display(Iterator<Pet> it) { while(it.hasNext()) { Pet p = it.next(); System.out.print(p.id() + ":" + p + " "); } System.out.println(); } public static void main(String[] args) { ArrayList<Pet> pets = Pets.arrayList(8); LinkedList<Pet> petsLL = new LinkedList<Pet>(pets); HashSet<Pet> petsHS = new HashSet<Pet>(pets); TreeSet<Pet> petsTS = new TreeSet<Pet>(pets); display(pets.iterator()); display(petsLL.iterator()); display(petsHS.iterator()); display(petsTS.iterator()); } } /* Output: 0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug 7:Manx 4:Pug 6:Pug 3:Mutt 1:Manx 5:Cymric 7:Manx 2:Cymric 0:Rat 5:Cymric 2:Cymric 7:Manx 1:Manx 3:Mutt 6:Pug 4:Pug 0:Rat *///:~
Note that display( ) contains no information about the type of sequence that it is traversing, and this shows the true power of the Iterator: the ability to separate the operation of traversing a sequence from the underlying structure of that sequence. For this reason, we sometimes say that iterators unify access to containers.
ListIterator
The ListIterator is a more powerful subtype of Iterator that is produced only by List classes. While Iterator can only move forward, ListIterator is bidirectional. It can also produce the indexes of the next and previous elements relative to where the iterator is pointing in the list, and it can replace the last element that it visited using the set( ) method. You can produce a ListIterator that points to the beginning of the List by calling listIterator( ), and you can also create a ListIterator that starts out pointing to an index n in the list by calling listIterator(n). Here’s an example that demonstrates all these abilities:
//: holding/ListIteration.java import typeinfo.pets.*; import java.util.*; public class ListIteration { public static void main(String[] args) { List<Pet> pets = Pets.arrayList(8); ListIterator<Pet> it = pets.listIterator(); while(it.hasNext()) System.out.print(it.next() + ", " + it.nextIndex() + ", " + it.previousIndex() + "; "); System.out.println(); // Backwards: while(it.hasPrevious()) System.out.print(it.previous().id() + " "); System.out.println(); System.out.println(pets); it = pets.listIterator(3); while(it.hasNext()) { it.next(); it.set(Pets.randomPet()); } System.out.println(pets); } } /* Output: Rat, 1, 0; Manx, 2, 1; Cymric, 3, 2; Mutt, 4, 3; Pug, 5, 4; Cymric, 6, 5; Pug, 7, 6; Manx, 8, 7; 7 6 5 4 3 2 1 0 [Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Manx] [Rat, Manx, Cymric, Cymric, Rat, EgyptianMau, Hamster, EgyptianMau] *///:~
The Pets.randomPet( ) method is used to replace all the Pet objects in the List from location 3 onward.
{Thinking in Java, 286}