Skip to content

Iterators

Jump to bottom Edit New page
Michael Dunn edited this page Oct 10, 2013 · 8 revisions
  • Iterators provide an abstract way of looping over an entire collection of items
  • Basically an object that moves along a list (or other collection)
  • Since collections of items differ in implementation, the details are left up to the implementing class
  • The for-each loop can be used with any collection that implements the Iterable interface
List<String> list = new List<String>();
//...add some values...
for (int i = 0; i < list.size(); i++) {
  System.out.println(list.get(i));  
}

What's the run time of the above example?

Iterator Interface

public boolean hasNext();
public E next();
public void remove();
  • hasNext() returns true while there are still more items in the collection
  • next() returns the next element in the iteration
  • remove() removes the last element returned by next. Can only be called once per next() call
public class LinkedListIterator<E> implements Iterator<E> {
  Node<E> tmpNode = null;
  
  public LinkedListIterator(Node<E> head) {
    this.tmpNode = head;
  }
  
  @Override
  public boolean hasNext() {
    return tmpNode != null;
  }
  
  @Override
  public E next() {
    if (tmpNode == null) {
        throw new NoSuchElementException();
    }
    E data = tmpNode.getData();
    tmpNode = tmpNode.next();
    return data;
  }
  
  @Override
  public void remove() {
    tmpNode.getPrev().setNext(tmpNode.next());
    tmpNode.getNext().setPrev(tmpNode.getPrev());
  }
}

Iterable Interface

  • Any class that we wish to provide an Iterator for needs to implement the Iterable Interface
  • Iterable interface simply specifies that a class can return an Iterator
public Iterator<T> iterator();
  • iterator() returns an Iterator over a set of elements of type T
public class LinkedList<E> implements Iterable<E> {

  ...

  @Override
  public LinkedListIterator<E> iterator() {
    return new LinkedListIterator<E>();
  }
}

Once we've finished with our Iterator and our Iterable interfaces, we can use them as follows:

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);

LinkedListIterator<Integer> iterator = new LinkedListIterator<Integer>();
while(iterator.hasNext()) {
  System.out.println(iterator.next());
}

List Iterators

  • Since lists are so important, Java provides a specialized Iterator for lists
  • ListIterator simply extends Iterator and adds additional functionality
public void add(E e);         // Inserts the specified element into the list (optional).
public boolean hasNext();     // Returns true if this list iterator has more elements when traversing the list in the forward direction.
public boolean hasPrevious(); // Returns true if this list iterator has more elements when traversing the list in the reverse direction.
public E next();              // Returns the next element in the list and advances the cursor position.
public int nextIndex();       // Returns the index of the element that would be returned by a subsequent call to next().
public E previous();          // Returns the previous element in the list and moves the cursor position backwards.
public int previousIndex();   // Returns the index of the element that would be returned by a subsequent call to previous().
public void remove();         // Returns the index of the element that would be returned by a subsequent call to previous().
public void set(E e);         // Replaces the last element returned by next() or previous() with the specified element (optional operation).
The devil is in the details
remove()

Removes from the list the last element that was returned by next() or previous() (optional operation). This call can only be made once per call to next or previous. It can be made only if add(E) has not been called after the last call to next or previous.

  • UnsupportedOperationException - if neither next nor previous have been called, or remove or add have been called after the last call to next or previous
  • IllegalStateException - if neither next nor previous have been called, or remove or add have been called after the last call to next or previous
set(E e)

Replaces the last element returned by next() or previous() with the specified element (optional operation). This call can be made only if neither remove() nor add(E) have been called after the last call to next or previous.

  • UnsupportedOperationException - if the set operation is not supported by this list iterator
  • ClassCastException - if the class of the specified element prevents it from being added to this list
  • IllegalArgumentException - if some aspect of the specified element prevents it from being added to this list
  • IllegalStateException - if neither next nor previous have been called, or remove or add have been called after the last call to next or previous
add(E e)

Inserts the specified element into the list (optional operation). The element is inserted immediately before the element that would be returned by next(), if any, and after the element that would be returned by previous(), if any. (If the list contains no elements, the new element becomes the sole element on the list.) The new element is inserted before the implicit cursor: a subsequent call to next would be unaffected, and a subsequent call to previous would return the new element. (This call increases by one the value that would be returned by a call to nextIndex or previousIndex.)

  • UnsupportedOperationException - if the add method is not supported by this list iterator
  • ClassCastException - if the class of the specified element prevents it from being added to this list
  • IllegalArgumentException - if some aspect of this element prevents it from being added to this list
Implementing a List Iterator over a Double Linked List

Use of inner classes

Inner Class Example

  • Classes can be embedded into other classes
  • Inner class can access everything in outer class (including private members)
  • Only enclosing class can access inner class
  • Best used with very tightly couples objects (iterators, nodes, objects that are specific to a class)
  • Can access as OuterClass.InnerClass
public class LinkedList<E> implements Iterable<E> {
  private class LinkedListIterator implements Iterator<E> {
    public boolean hasNext() {...}
    ...
  }
  
  // Rest of linked list code

  public LinkedListIterator<E> iterator() {
     ... 
  }
}

For-each Loops

  • Can use for-each style loops over any collection of data that implements the Iterable interface
  • This includes the entire Collections API!
  • Can not access index
  • Makes code more readable

Consider the following:

LinkedList<String> list = new LinkedList<>();
ListIterator<String> iterator = ll.iterator();

while(iterator.hasNext()) {
  System.out.println(iterator.next());
}
for(ListIterator<String> iterator = list.iterator(); iterator.hasNext();) {
  System.out.println(iterator.next());
}
for(String s : list) {
  System.out.println(s);
}
Add a custom footer
Add a custom sidebar

Clone this wiki locally