Using Iterators and ListIterators for Speedier Parsing

Iterators (Parts 1 and 2)









Using an iterator to print a list is more efficient because it runs in O(n) time whereas a for loop would run in O(n^2) time. With a Set which is unordered, we cannot print with a simple for loop, so an iterator is handy.

Problems with Iterators


Calling the next method on an iterator at the end of a List/Set does not return null. Instead, it crashes the program.

Also, an underlying object cannot be changed once the iterator is established. Try to figure out why this program crashes:

    public static void main(String [] args) {
        ArrayList<Integer> data = new ArrayList<>();
        data.add(3);
        data.add(9);
        data.add(7);
        data.add(1);
        data.add(2);
       
        Iterator<Integer> it = data.iterator();
        
        data.add(3);
        
        while (it.hasNext())
            System.out.println( it.next() );
    }

ListIterators in Java

A ListIterator in Java is a iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.

A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). An iterator for a list of length n has n+1 possible cursor positions, as illustrated by the carets (^) below:

           Element(0) ^  Element(1) ^  Element(2) ^  ... Element(n-1)

Cursor positions are indicated on the above line by the presence of the carot (^) characters.

ListIterator Methods 

The following methods are taken from the Oracle Docs:
  1. void add(E e)Inserts the specified element into the list (optional operation).
  2. boolean hasNext()Returns true if this list iterator has more elements when traversing the list in the forward direction.
  3. boolean hasPrevious()Returns true if this list iterator has more elements when traversing the list in the reverse direction.
  4. E next() Returns the next element in the list and advances the cursor position.
  5. int nextIndex()Returns the index of the element that would be returned by a subsequent call to next().
  6. E previous()Returns the previous element in the list and moves the cursor position backwards.
  7. int previousIndex() Returns the index of the element that would be returned by a subsequent call to previous().
  8. void remove()Removes from the list the last element that was returned by next() or previous() (optional operation).
  9. void set(E e)Replaces the last element returned by next() or previous() with the specified element (optional operation).
Note: As is the case with Iterators, ListIterators never return null.

Small ListIterator Lab


Directions: Create an ArrayList of Strings. Store the following elements in the ArrayList:

Apple
Pear
Banana
Cherry
Cucumber
Eggplant
Berries

  1. Use a for-loop to parse through the array forwards while deleting all the entries that start with a capital "C". Do not adjust the index after deletions. Then print the resulting list. Note how Cucumber was not deleted because of the shifting problem. Restore the data to the ArrayList.

  2. Now try the same exercise with an iterator. Explain why the shifting problem does not occur. Restore the data to the ArrayList.

  3. Now try the same exercise with an listIterator. Explain why the shifting problem does not occur. Restore the data to the ArrayList.

  4. Use a listIterator to parse the list forwards and print it. Then parse it backwards and print it.


1 point
Will the following code compile and run?
it can be assumed this will be found within a method and it the appropriate location

Iterator.it = new Iterator();