A traversal of a list is an operation that visits all the elements of the list in sequence and performs some operation. For example, the following loop can be used to traverse a linked list:
ListNode node = first; // start from the first node
while (node != null)
{
SomeClass value = (SomeClass)node.getValue();
// process value
...
}
When the linked list is implemented as an encapsulated class, first is no longer directly accessible. To provide access to the elements of a list and maintain the protection afforded by encapsulation, the Java library supplies an Iterator
type.
An iterator is an object associated with the list. When an iterator is created, it points to a specific element in the list, usually the first. We call the iterator's methods to check whether there are more elements to be visited and to obtain the next element.
In Java, the iteration concept is expressed in the library interface java.util.Iterator
. The Iterator
interface is used by classes that represent a collection of objects such as a list, providing a way to move through the collection one object at a time. The Iterator
interface is not used to represent the list itself, it merely represents a way to move through the elements of the list.
An Iterator
object provides three basic methods:
Object next()
// Returns the next element in the iteration
Object hasNext()
// Returns true if the iteration has more elements
void remove()
// Removes the last element returned by next from the list
A list traversal would be implemented with an iterator as follows:
LinkedList list = new LinkedList()
// Add values to the list
...
Iterator iter = list.iterator();
while (iter.hasNext())
{
Object obj = iter.next()
System.out.println(obj);
}
Note that the list itself provides an iterator when its iterator()
method is called.
A limitation of the Iterator
interface is that an iterator always iterates from the beginning of the list and only in one direction.
A more comprehensive ListIterator
object is returned by List
"s listIterator
method. ListIterator
extends Iterator
. A ListIterator
can start iterations at any specified position in the list and can proceed forward or backward. For example:
ListIterator listIter = list.listIterator(list.size());
while (listIter.hasPrevious())
{
SomeClass value = (SomeClass)listIter.previous();
// process value
...
}
Some useful ListIterator
methods are summarized below
Object next()
// Returns the next element in the iteration
Object hasNext()
// Returns true if the iteration has more elements
Object previous()
// Returns the previous element in the iteration
Object hasPrevious()
// Returns true if the previous element in the list is
// is available, false otherwise
void add(Object obj)
// Inserts the element obj into the list immediately after
// the last element that was returned by the next method
void set(Object obj)
// Replaces the last element returned by next or pervious
// with the element obj
void remove()
// Removes the last element returned by next or previous
// from the list