Inner classes and implementation of ArrayList - Data Structures and Problem Solving Using Java - page 585

implementation of
ArrayList with an iterator

15.5

The various ArrayList classes shown in Part One were not iterator-aware. This
section provides an implementation of ArrayList that we will place in
weiss.util and includes support for bidirectional iterators. In order to keep the
amount of code somewhat manageable, we have stripped out the bulk of the
javadoc comments. They can be found in the online code.
The implementation is found in Figures 15.13 to 15.16. At line 3 we see
that ArrayList extends the AbstractCollection abstract class, and at line 4
ArrayList declares that it implements the List interface.
The internal array, theItems , and collection size, theSize , are declared at
lines 9 and 10, respectively. More interesting is modCount , which is declared
at line 11. modCount represents the number of structural modifications ( add s,
remove s) made to the ArrayList . The idea is that when an iterator is con-
structed, the iterator saves this value in its data member expectedModCount .
When any iterator operation is performed, the iterator's expectedModCount
member is compared with the ArrayList 's modCount , and if they disagree, a
ConcurrentModificationException can be thrown.
Line 16 illustrates the typical constructor that performs a shallow copy of
the members in another collection, simply by stepping through the collection
and calling add . The clear method, started at line 26, initializes the ArrayList
and can be called from the constructor. It also resets theItems , which allows
the garbage collector to reclaim all the otherwise unreferenced objects that
were in the ArrayList . The remaining routines in Figure 15.13 are relatively
straightforward.
Figure 15.14 implements the remaining methods that do not depend on
iterators. findPos is a private helper that returns the position of an object that
is either being removed or subjected to a contains call. Extra code is present
because it is legal to add null to the ArrayList , and if we were not careful, the
call to equals at line 60 could have generated a NullPointerException . Observe
that both add and remove will result in a change to modCount .
In Figure 15.15 we see the two factory methods that return iterators, and
we see the beginning of the implementation of the ListIterator interface.
Observe that ArrayListIterator IS-A ListIterator and ListIterator IS-A Iter-
ator . So ArrayListIterator can be returned at lines 103 and 106.
In the implementation of ArrayListIterator , done as a private inner class,
we maintain the current position at line 111. The current position represents
the index of the element that would be returned by calling next . At line 112 we
declare the expectedModCount member. Like all class members, it is initialized