Iteration

Iteration

The act of iterating through a data structure in order to examine or operate on each element is fundamental in computer science and shows up again and again. You have done this many times already. For example, in Java, if you have an ArrayList<Integer>, you can iterate through it and sum all of the elements.

ArrayList<Integer> list = new ArrayList<Integer>();
int sum = 0;
// Add some elements to the list.
for (int i = 0; i < list.size(); i++) {
    sum += list.get(i);
}

Although this approach works quite well with an ArrayList, it really breaks down when we switch data structures to something like a LinkedList. In lab 4, you will be implementing your own LinkedList. The problem comes from the list.get(i) method. Recall that a linked list stores a pointer to the head of the list (and perhaps a pointer to the tail of the list). In order to get to the element at index i, the implementation of get() has to start at the head of the list and walk through the linked list of nodes. This code would look something like

public E get(int index) {
    Node node = this.head;
    while (index > 0) {
        node = node.next;
        index--;
    }
    return node.data;
}

(This isn’t the whole thing. We’d need to handle reaching the end of the list before index hit 0 and throw an exception.)

In contrast, the ArrayList.get() method need only return the ith element of its underlying array.

public E get(int index) {
    return this.data[index];
}

Fortunately, Java (and most other programming languages) provides a way to deal with this problem: iterators.

Using Iterators

An Iterator<E> is an interface with two key methods:

  • boolean hasNext() which returns true if the iterator is able to return a next value; and
  • E next() which returns the next element; this element has type E.

All Java collection classes (including ArrayList<E> and LinkedList<E>) have a method iterator() which returns a class which implements Iterator<E>.

Open the provided file UsingIterators.java, which creates and fills an ArrayList, and then calls its iterator method.

The way you work with an iterator is usually by writing a loop.

while (iter.hasNext()) {
    E obj = iter.next();
    // Do something with obj
}

The paradigm of calling iterator() on a collection and then using iter.hasNext() and iter.next() in a loop is so common in Java, that there is special syntax for it, sometimes called a “for-each” loop.

for (E obj : collection) {
    // Do something with obj.
}

This is the same as

Iterator<E> iter = collection.iterator();
while (iter.hasNext()) {
    E obj = iter.next();
    // Do something with obj.
}

Add the following code to the UsingIterators main method and modify it to print out every item in the ArrayList

for (Integer i : al) {
    // Do something with i.
}