CS 112 Lab: Java Iterators

 

Introduction

One of the basic things we want to do with an Abstract Data Type is to examine the data items held inside it. For example, we might want to print out the items, or search for a particular item. Of course, you can write a particular method, such as toString() or member(....), which involves examining data items for some particular purpose, but the idea of listing or enumerating the data items is a basic operation which may be useful in many different contexts.

The first thing you might think of doing is to produce an array or linked list containing all the data items, but this violates the principle of information hiding: we don't want to provide our basic data structures to the client. The way we do this in Java is using an iterator, an object-oriented way for an ADT to enumerate the elements in a collection.

Unlike simply providing all the data at once, with an iterator, you do not need to provide all the elements, and you can pause your enumeration, only list some of the elements, and in general just get the elements "by need" instead of all at once. This is an extremely flexible way to think about enumerating a collection, and characteristic of object-oriented programming.

Enumerating the Data in an ADT using an Iterator

An enumeration is simply a sequence of the keys or elements in a collection. For example, if your collection is the letters { A, B, C }, then an enumeration might be A, B, C, or it might be C, B, A, or it might be B, A, C; the order is not important, but it is important that each element is given at most once.

When a client uses an ADT, it is often useful to be able to list or access the elements in some order, but the client wants to control the timing of the enumeration, and not be forced by the ADT to accept a list of ALL elements all at once.

Here is a silly example, using the idea of a surgeon as a client, and you, her helper, as an ADT.

You are helping a surgeon perform a heart-valve replacement operation. The surgeon has to put together the value using parts that are inserted in a precise order, and your job is to stand at a table with a line of spare heart parts in front of you, and when she asks for the next part, you pick up the next part (from left to right), wipe it off on your shirt and give it to her. Everything has to be done perfectly or the patient will die, so you MUST be ready at each moment for the next request for a part. Here is what your conversation goes like:

Surgeon: "Ok, get ready!" (You pause with your hand over the left-most part);

Surgeon: "Is there a next part?" (You look to see that there is a part to be given to her, there is, so....)

You: "Yes"

Surgeon: "Ok, give it to me" (You hand it to her, then pause with your hand over the next part from left to right.)

(Some time goes by, and then....)

Surgeon: "Is there a next part?"

You: "Yes"

Surgeon: "Ok, give it to me" (You hand it to her, then move your hand to the next part.)

(This goes on for a while, until there is one part left...)

Surgeon: "Is there a next part?" (You look to see that there is a part to be given to her, there is, so....)

You: "Yes"

Surgeon: "Ok, give it to me" (You hand it to her, then stand there with no parts in front of you.)

Surgeon: "Is there a next part?"

You: "No"

Surgeon: "Ok, I guess we're done, thanks!"

The most important thing to realize is that the ADT has to always have some indication of where the next part is (and whether there is a next part), and the surgeon controls the enumeration.

This has all the key components of a iterator:

  1. an initialization step,
  2. a way to check if the iterator has a next element; and
  3. a way to provide the next element.

The Scanner Class as an Example of an Iterator

You have already used an interator when you used the Scanner class to read input from the Console, for example, here we read integers from the Console and simply print them out. We note in the comments the three essential parts of an interator:

 

The Java Interface Iterator<Item>

An iterator is an inner class: a class defined inside your ADT that allows you to perform an iteration over the data in the ADT. There are three methods necessary for an iterator, which can be summarized by the following generic interface:
public interface Iterator<Item> {         

     public boolean hasNext();               // Is there a next element in the enumeration?

     public Item next();                     // Provide the next element in the enumeration

     public void remove();                   // remove the last element enumerated -- optional --  we shall ignore this

}

This interface is provided by importing java.util.Iterator, as shown in the example code List.java, which shows how an inner class is created which then provides the iteration. The first thing to notice is that the inner class is a separate object than List L, but provides access to the private variable A inside List L; it also has its own local variable cursor to move through the array A as we do the enumeration:

    
    private class It implements Iterator<Integer> {
        
        private int cursor;                   // where in the enumeration we are
        
        public It() { 
            cursor = 0;                       // start out the enumeration at 0      
        }
        
        // interface methods required by Iterator interface
        
        public boolean hasNext() {
            return cursor < A.length;
        }
        
        public Integer next() {
            if(hasNext()) {
                return A[cursor++];
            }
            else {
                return null; 
            }
        } 
        
        public void remove() {             // required by interface but we won't implement it
        }
    }

 

Download and look through the example code linked above, and look carefully at the first part of the main method, and in particular notice how the method iterator() returns a class which allows you to access the data without violating the principle of "information hiding." Then look carefully at the "more complex example" and make sure you understand how these two iterators give you different enumerations of the same data.

The Java Interface Iterable<Item>

There is another aspect of Java iterators, and that is that the ADT itself may implement an interface which is provided by java.util.Iterator, and which looks like this:
public interface Iterable<Item> {         

     public Iterator<Item> iterator();               

}

This allows you to use a nice piece of Java syntax in the case that you want to enumerate through the entire ADT:

        for(Integer i : L) {        
            System.out.print(i + " ");   
        }
        System.out.println(); 

Here, L satisfies the Iterable interface, in that it provides public implementation of the method iterator(). Java then knows that it can use a special syntax for for loops (called a "for each" loop).

It is interesting that arrays are considered to be iterable in this sense by default, and so you can do the same trick with arrays (without referring to either of the interfaces):

        char[] B = { 'A', 'B', 'C' };
        
        for(char c : B) {        
            System.out.print(c + " ");   
        }
        System.out.println();
        

The Problem

Now take the former program List.java, and rewrite it so that it uses a linked list instead of an array, and change the name to LinkedList.java. You need to create a linked list holding the same numbers as in the original program; DO NOT CHANGE THE MAIN METHOD (except to change the first line to use LinkedList instead of List), as the point is that we may still do the enumeration, without violating the principle of information hiding.

Hint: Add a private Node class and then create a field head pointing to a list containing the same elements as in the example:

private Node head = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, null)))));

Submit the file LinkedList.java as problem B.1 of HW 06.