Iterators - Data Structures and Abstractions with Java - page 368

the list. As the iteration progresses, the iterator returns entry after entry. Once next has returned the
last entry in the collection, a subsequent call to it causes a NoSuchElementException .

FIGURE 15-1

The effect of a call to next on a list iterator

(a) Before

Joe Jen Jess

Iterator cursor

(b) After returns Jen

Joe Jen Jess

Iterator cursor

The method remove removes the entry that next just returned. Contrast this with the ADT list
operation remove , which removes the entry at a given position within the list. When you imple-
ment the Iterator interface, you do not have to provide a remove operation—it is optional—but
you do need to define a method remove , because it appears in the interface. Such a method should
throw the exception UnsupportedOperationException if the client invoked it.

Programming Tip: All of the exceptions mentioned in the interface Iterator are run-
time exceptions, so no throws clause is necessary in any of the methods' headers. In addition,
you do not have to write try and catch blocks when you invoke these methods. However,
you will need to import NoSuchElementException from the package java.util . The other
exceptions are in java.lang , so no import statement is necessary for them.

Using the Interface Iterator
15.5

Some details of using an iterator depend on the approach used to implement the iterator methods.
A possible, but not optimal, way to provide an ADT with traversal operations is to define them as
ADT operations. For example, if ListInterface extends Iterator , a list object would have iter-
ator methods as well as list methods. Although such an approach provides efficient traversals, it
has disadvantages, as you will see.
A better way is to implement the iterator methods within their own class. In one approach, this
class is public and separate from the class that implements the ADT in question. The two classes
must, of course, interact in some way. We will call an instance of such an iterator class a separate
class iterator . Alternatively, the iterator class can be a private inner class of the class that imple-
ments the ADT. We'll call an instance of this inner class an inner class iterator . As you will see, an
inner class iterator is usually preferable. This chapter will discuss both approaches.
But first, let's focus on how the methods in the interface Iterator behave. A separate class iter-
ator of a list and an inner class iterator of a list are objects distinct from the list. Both of these iterators
invoke their methods in the same way. The following examples arbitrarily use a separate class iterator.

15.6

Example. Let's look at an example of how the methods hasNext and next of the interface Iterator
work with the ADT list. Suppose we create a list of names. We will use strings for the names, but we
could instead use instances of the class Name that Appendix B presented. The following Java state-
ments create such a list:

ListInterface<String> nameList = new LList<String>();
nameList.add("Jamie");