Java Reference
In-Depth Information
checking for errors is difficult. For example, a user could pass a reference to
something that is a node in a different list. One way to guarantee that this can-
not happen is to store a current position as part of a list class. To do so, we add
a second data member,
current
. Then, as all access to the list goes through the
class methods, we can be certain that
current
always represents a node in the
list, the header node, or
null
.
By storing a cur-
rent position in a list
class, we ensure
that access is con-
trolled.
This scheme has a problem: With only one position, the case of two itera-
tors needing to access the list independently is left unsupported. One way to
avoid this problem is to define a separate
iterator class,
which maintains a
notion of its current position. A list class would then not maintain any notion
of a current position and would only have methods that treat the list as a unit,
such as
isEmpty
and
makeEmpty
, or that accept an iterator as a parameter, such as
insert
. Routines that depend only on an iterator itself, such as the
advance
rou-
tine that advances the iterator to the next position, would reside in the iterator
class. Access to the list is granted by making the iterator class either package-
visible or an inner class. We can view each instance of an iterator class as one
in which only legal list operations, such as advancing in the list, are allowed.
In Section 17.2 we define a generic list class
LinkedList
and an iterator
class
LinkedListIterator
. The
LinkedList
class does not have the same seman-
tics as
java.util.LinkedList
. However, later in the chapter we define a version
that does. To show how the nonstandard version works, let us look at a static
method that returns the size of a linked list, as shown in Figure 17.6. We
declare
itr
as an iterator that can access the linked list
theList
.
We initialize
itr
to the first element in
theList
(skipping over the header,
of course) by referencing the iterator given by
theList.first()
.
The test
itr.isValid()
attempts to mimic the test
p!=null
that would be
conducted if
p
were a visible reference to a node. Finally, the expression
itr.advance()
mimics the conventional idiom
p=p.next
.
An
iterator class
maintains a current
position and typi-
cally is package-
visible or an inner
class of a list (or
other container)
class.
1
// In this routine, LinkedList and LinkedListIterator are the
2
// classes written in Section 17.2.
3
public static <AnyType> int listSize( LinkedList<AnyType> theList )
4
{
5
LinkedListIterator<AnyType> itr;
6
int size = 0;
7
8
for( itr = theList.first(); itr.isValid(); itr.advance() )
9
size++;
10
11
return size;
12
}
figure 17.6
A static method that returns the size of a list
Search WWH ::
Custom Search