A traversal of a list is an operation that visits all the elements of the list in sequence and performs some operation.

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. The iterator provides methods to check whether there are more elements to be visited, to obtain the next element, and to remove the current element. This makes it easy to traverse a list. Using an iterator helps prevent OBOBs ('Off-By-One-Bugs': attempts to access an element beyond the length of the list) because the iterator knows how big the list is.

In Java, iterators are defined by the library interface, java.util.Iterator.

Iterator defines three basic methods:

Object next()
// Returns the next element in the iteration

boolean 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 using an iterator as follows.

LinkedList <String> list = new LinkedList <String>();
// Add values to the list
...

Iterator <String> iter = list.iterator();
while (iter.hasNext()){
  System.out.println(iter.next());
}

Note that the list provides the iterator.

A limitation of the Iterator interface is that an iterator always starts at the beginning of the list and can only move forward.

A more comprehensive ListIterator object is returned by List’s listIterator method. ListIterator extends Iterator. A ListIterator can start at any specified position in the list and can proceed forward or backward. For example:

ListIterator <String> listIter =
list.listIterator(list.size());
while (listIter.hasPrevious()){
  String value = listIter.previous();
  // process value
  ...
}

Some useful ListIterator methods are summarized below:

Object next()
// Returns the next element in the iteration.

void add(Object x)
// Inserts the argument into the list being iterated over.

void set(Object x)
// Replaces the last element returned by next by the argument.

The following two examples illustrate one of the advantages of iterators.

Example 1:

LinkedList <String> list = new LinkedList <String>();
// Add values to the list

   list.add("John");
   list.add("Ann");
   list.add("Betsy");
   list.add("Nancy");

   for(int i = 0; i < list.size(); i++){
      String value = list.get(i);
      System.out.println(value);
      if(value.equals("Ann"))
         list.remove(i);
   }

Run Output:

John
Ann
Nancy


Example 2:

LinkedList <String> list2 = new LinkedList <String>();
// Add values to the list

   list2.add("John");
   list2.add("Ann");
   list2.add("Betsy");
   list2.add("Nancy");
   Iterator <String> listIter = list2.iterator();
   while (listIter.hasNext()){
      String value = listIter.next();
      System.out.println(value);
      if(value.equals("Ann"))
         listIter.remove();
   }

Run Output:

John
Ann
Betsy
Nancy

In Example 1, the index is external to the list, so after removing Ann, i is incremented but the elements of the list have changed positions and Betsy is skipped. In Example 2, the iterator keeps track of the positions of the elements after Ann is removed and Betsy is not skipped.