Linked lists - Data Structures and Problem Solving Using Java - page 624

Thus, as long as the iterator class defines a few simple operations, we can
iterate over the list naturally. In Section 17.2 we provide its implementation in
Java. The routines are surprisingly simple.
There is a natural parallel between the methods defined in the LinkedList
and LinkedListIterator classes and those in the Collections API LinkedList
class. For instance, the LinkedListIterator advance method is roughly equiva-
lent to hasNext in the Collections API iterators. The list class in Section 17.2 is
simpler than the Collections API LinkedList class; as such it illustrates many
basic points and is worth examining. In Section 17.5 we implement most of
the Collections API LinkedList class.

java implementation

17.2

As suggested in the preceding description, a list is implemented as three sepa-
rate generic classes: one class is the list itself ( LinkedList ), another represents
the node ( ListNode ), and the third represents the position ( LinkedListIterator ).
ListNode was shown in Chapter 16. Next, Figure 17.7 presents the class
that implements the concept of position—namely, LinkedListIterator . The
class stores a reference to a ListNode , representing the current position of the
iterator. The isValid method returns true if the position is not past the end of
the list, retrieve returns the element stored in the current position, and advance
advances the current position to the next position. The constructor for
LinkedListIterator requires a reference to a node that is to be the current
node. Note that this constructor is package-visible and thus cannot be used by
client methods. Instead, the general idea is that the LinkedList class returns
preconstructed LinkedListIterator objects, as appropriate; LinkedList is in the
same package as LinkedListIterator , so it can invoke the LinkedListIterator
constructor.
The LinkedList class skeleton is shown in Figure 17.8. The single data
member is a reference to the header node allocated by the constructor. isEmpty
is an easily implemented short one-liner. The methods zeroth and first return
iterators corresponding to the header and first element, respectively, as shown
in Figure 17.9. Other routines either search the list for some item or change
the list via insertion or deletion, and are shown later.
Figure 17.10 illustrates how the LinkedList and LinkedListIterator
classes interact. The printList method outputs the contents of a list. printList
uses only public methods and a typical iteration sequence of obtaining a start-
ing point (via first ), testing that it has not gone past the ending point (via
isValid ), and advancing in each iteration (via advance ).