As you may remember, there are two types of for loops in Java, and either one can be used to go through a variety of lists. Consider the following two implementations of the same method: A simple method to print out the contents of an ArrayList.
public static void printItemsTraditional(ArrayList<String> myList) {
for(int i = 0; i < myList.size(); i++) {
String item = myList.get(i);
System.out.println(item);
}
}public static void printItemsForEach(ArrayList<String> myList) {
for(String item: myList) {
System.out.println(item);
}
}In this set of notes, we’ll talk about how you can modify your own data structures so that the for-each loop can be used on them. We’ll also discuss why this loop can be more efficient in some cases.
Iteratorhttps://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
The for-each loop is a Java shortcut for using something called an Iterator. When you use a for-each loop, what Java is doing is this:
public static void printItemsActualForEach(ArrayList<String> myList) {
Iterator<String> it = myList.iterator();
while(it.hasNext()) {
String item = it.next();
System.out.println(item);
}
}Iterator?An Iterator is an object returned from a collection (such as an ArrayList) that you can use to go through the list sequentially. You use the hasNext method to determine if there are any other items in the collection and you call the next method to get the next item.
Let’s go through the last code example. To iterate over an ArrayList we get an Iterator for the list by calling myList.iterator(). We then loop over that Iterator, using hasNext to determine if there are more items and call next to get the next item. This may look familiar: It is very similar to how we read in lines from a file in the notes on files.
Iterator is an InterfaceIterator is an interface that requires you to implement three methods.
// Returns true if the iteration has more elements.
// (In other words, returns true if next() would return an element rather than throwing an exception.)
public boolean hasNext();
// Returns the next element in the iteration.
// Throws the NoSuchElementException if the iteration has no more elements
public Object next();
// Removes from the underlying collection the last element returned by this iterator (optional operation).
// This method can be called only once per call to next().
// The behavior of an iterator is unspecified if the underlying collection is modified while the iteration
// is in progress in any way other than by calling this method.
// Note: If you don't want to support remove, then throw the UnsupportedOperationException instead of
// actually removing anything.
public void remove();So, the call myList.iterator() returns an object that implements the iterator interface.
The data structure you want to iterate over does not implement the Iterator interface. Instead, it has a method that returns a different object that implements the Iterator interface. (Yes, this is a bit strange at first glance.)
Iterable Interfacehttps://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html
One more note before we get to a code example: If you want your data structure to be able to be used as a for-each loop, then it needs to implement the Iterable interface. (Notice this is different from the Iterator interface.) The Iterable interface requires only one method:
// Returns an iterator over elements of type T.
public Iterator<T> iterator();This method simply returns an Iterator for the data structure.
Let’s do an example to make things more clear.
Consider the following Roster class that uses a basic array to store people. It should be fairly straight-forward:
public class Roster {
private static final int MAX_STUDENTS = 5;
private Person[] studentList;
private int end;
public Roster() {
studentList = new Person[MAX_STUDENTS];
end = 0;
}
/**
* Get the number of people in the roster
*
* @return The size of the roster
*/
public int getSize() {
return this.end;
}
/**
* Add a person to the roster
*
* @param p The person to add to the roster
*/
public void addStudent(Person p) {
if (end < MAX_STUDENTS) {
studentList[end++] = p;
}
}
/**
* Get a person from the roster based on index
*
* @param i The index of the person to get
* @return The person at that index or null if the index is not valid
*/
public Person getStudent(int i) {
if (i < end) {
return studentList[i];
} else {
return null;
}
}
}Right now if I want to loop through a roster I would do something like the following:
Roster r = new Roster();
r.addStudent(new Person("Bob"));
r.addStudent(new Person("Fred"));
r.addStudent(new Person("John"));
for (int i = 0; i < r.getSize(); i++) {
System.out.println(r.getStudent(i));
}If I want to be able to use an Iterator to properly go over the Roster, then I need to add a method that returns an Iterator. I’ll add the following new method to my Roster class:
public Iterator<Person> iterator() {
// What do I do now?
}Remember, this method needs to return an Iterator that operates over my Roster. Given that Iterator is an interface, that means I need to declare a new class that implements that interface and then return an instance of one. So, let’s create a new, inner class that implements the Iterator interface:
public class RosterIterator implements Iterator<Person> {
// Pointer to the current element the iterator is pointing to
private int cur = 0;
// Return true if there is another element, and false otherwise.
public boolean hasNext() {
return (cur < end);
}
// Return the next item in the Roster and then increment cur
// If there is no next item, then throw an exception.
public Person next() {
if (hasNext()) {
return studentList[cur++];
} else {
throw new NoSuchElementException();
}
}
// I decided not to implement this, so we throw an appropriate exception.
public void remove() {
throw new UnsupportedOperationException();
}
}This class is declared inside of the Roster class. When we declare one class inside of another, we call it an inner class. One advantage of inner classes is that they can access all of the instance variables and methods of the class they are inside of. Here, for example, RosterIterator can access both the end and studentList instance variables from the Roster class.
We also fill in our iterator method from above to return an instance of our new RosterIterator.
public Iterator<Person> iterator() {
return new RosterIterator();
}IterableNow that we have implemented all of the required methods, our last step is to make the Roster class Iterable:
public class Roster implements Iterable<Person> {
...Since we have already implemented the interator() method required by this interface, there is nothing else for us to do.
Here is the final code for our Roster class:
public class Roster implements Iterable<Person> {
private static final int MAX_STUDENTS = 5;
private Person[] studentList;
private int end;
public Roster() {
studentList = new Person[MAX_STUDENTS];
end = 0;
}
/**
* Get the number of people in the roster
*
* @return The size of the roster
*/
public int getSize() {
return this.end;
}
/**
* Add a person to the roster
*
* @param p The person to add to the roster
*/
public void addStudent(Person p) {
if (end < MAX_STUDENTS) {
studentList[end++] = p;
}
}
/**
* Get a person from the roster based on index
*
* @param i The index of the person to get
* @return The person at that index or null if the index is not valid
*/
public Person getStudent(int i) {
if (i < end) {
return studentList[i];
} else {
return null;
}
}
/**
* Get an iterator for the Roster
*
* @return The iterator
*/
public Iterator<Person> iterator() {
return new RosterIterator();
}
public class RosterIterator implements Iterator<Person> {
// Pointer to the current element the iterator is pointing to
private int cur = 0;
// Return true if there is another element, and false otherwise.
public boolean hasNext() {
return (cur < end);
}
// Return the next item in the Roster and then increment cur
// If there is no next item, then throw an exception.
public Person next() {
if (hasNext()) {
return studentList[cur++];
} else {
throw new NoSuchElementException();
}
}
// I decided not to implement this, so we throw an appropriate exception.
public void remove() {
throw new UnsupportedOperationException();
}
}
}Using this Roster, we can finally do the for-each loop:
Roster r = new Roster();
r.addStudent(new Person("Bob"));
r.addStudent(new Person("Fred"));
r.addStudent(new Person("John"));
for (Person p : r) {
System.out.println(p);
}So, why is this useful? Here are a few reasons:
There is a uniform way to go through (iterate over) all of the elements of a variety of data structures.
For-each is frequently more readable and faster to write.
For some data structures, having this sort of control over iteration can make things more efficient. Consider a linked list: A traditional for loop going through a linked list and using get(i) is \(O(N^2)\) because get(i) is \(O(N)\) and is being called from a loop over \(N\) items. With a properly written iterator, however, a for-each loop through a linked list can be \(O(N)\).