Module 1: Iterators

Introduction to Iterators

Iterators are a fundamental design pattern in Java that provide a way to access elements of a collection sequentially without exposing its underlying representation. The Iterator pattern allows for different traversal techniques and provides a common interface for traversing different types of collections.

In Java, the Iterator interface is part of the Java Collections Framework and provides methods to iterate through a collection, check if there are more elements, and retrieve the next element.

Iterators are particularly useful because they give you the ability to safely add and remove elements while iterating through a collection. Without iterators, attempting to modify a collection during a for-each loop would result in a ConcurrentModificationException.

Iterator Methods

The Iterator interface includes three key methods that help you traverse a collection:

• boolean hasNext(): Returns true if the iterator has at least one more element to iterate through.
• E next(): Returns the next element in the collection as long as hasNext() is true. Throws a NoSuchElementException if hasNext() is false.
• void remove(): Removes the current element in the collection and throws an IllegalStateException if called again before calling next().

ListIterator

The ListIterator<E> extends the functionality of Iterator<E> when working with List<E> classes. It provides bidirectional traversal and the ability to add and update elements in addition to the standard iterator operations.

Additional methods in ListIterator include:

• void add(E element): Inserts an object immediately before the current cursor position.
• void set(E element): Replaces the last element returned by next().
• hasPrevious() and previous(): Support traversing backwards through a list.

Understanding Iterators

Iterator<E> is an interface which belongs to the Collections framework and is used to retrieve items one by one. Iterators are useful because they give us the ability to traverse a given collection and access and remove data elements from the collection. The iterator includes certain methods to iterate through the collection and a cursor that keeps track of the current place in the collection. This reading will cover all these points in more detail.

Why use Iterators?

Iterators provide a way to safely add and remove elements while iterating through a collection. Have you ever tried to call add() or remove() on a list while iterating through it with a for-each loop, like the example below?

List<String> letters = Arrays.asList("A", "B", "C");
    
for (String letters : letters) {
    letters.remove("A"); // ConcurrentModificationException thrown!
}

The above code will result in a ConcurrentModificationException being thrown at runtime. Java prevents us from directly adding to or removing from a list while iterating though it. In this reading, you'll learn how to use Iterators to add and remove elements while iterating through a collection.

Iterator Methods

The iterator includes three methods that help us traverse a collection.

• boolean hasNext(): returns true if the iterator has at least one more element to iterate through.
• E next(): returns the next element in the collection as long as hasNext() is true and throws a NoSuchElementException if hasNext() is false. Iterators are defined as a generic class using the type E. So here E represents the type held by the iterator.
• void remove(): removes the current element in the collection and throws an IllegalStateException if the method is called again after it's already removed the current element.

next()

All these methods depend upon the cursor to determine where the iterator currently is within the collection. The cursor functions just as the cursor on your computer does when you type. If you're editing text in an application such as Microsoft Word, the next key you press will appear wherever your cursor is currently located. The next() method functions like hitting the right arrow key--it moves from the current character to the next character, as long as there is another character, which functions like the hasNext() method returning true. If you get to the last character then the cursor no longer moves, which functions like the hasNext() method returning false.

Figure 1. Diagram of calling the next() method on elements: s e n t e n c e. The cursor starts at the beginning of the list.

Each time the next() method is called, it returns the next element in the collection, which is the element it moved over. In the initial step of the above example, next() hasn't been called yet so it hasn't returned any elements. When we call next() the first time, the value returned is the first element, which has value 's'. When we call next() a second time, the value returned is now the second element, which has value 'e'. As next() is called, the cursor also moves so that it is just to the right of the last value it returned.

remove() with next()

The remove() method functions more similarly to deleting elements from an Excel table than a text editing document. Once you delete the contents in a cell, you must press the arrow key to move to the next cell. If you keep pressing the delete key in an empty cell, nothing will happen until you manually move to the next cell using the right arrow key. This is how the remove() method functions---you have to manually use the next() method to give the remove() method another value to delete. This is because the remove() method operates on the last element returned by the next() method. If you don't call the next() method again, there is no element for the remove() method to operate on! The remove() method, however, will return an IllegalStateException if you try to delete the empty cell, instead of just doing nothing.

Figure 2. Diagram of calling the remove() method on the elements: s e n t e n c e. The cursor starts at the beginning of the list.

In the above example, you can see that the cursor starts at the beginning of the list and next() hasn't returned any values. If you called the remove() method now, you would get an IllegalStateException because next() hasn't returned a value to remove. So instead we call the next() method---returning the element with value 's' and moving the cursor between the 's' and the 'e'. Now when we call the remove() method, it will delete the element with value 's' because that's the last element returned by the next() method. Once we've removed the element, the last value next() returned is no longer a valid element, because it's been deleted! So we need to call the next() method again, which returns the element with value 'e' and moves the cursor between the 'e' and 'n'. Finally, we call remove() one more time, which deletes the 'e', since that was the last value returned by the next() method.

ListIterator

The ListIterator<E> is an Iterator<E> which provides additional functionality when working with List<E> classes. It allows you to traverse the list forward or backward and the ability to add and update elements in the list, in addition to the other iterator methods.

The ListIterator<E> includes the following methods to help us traverse a list.

• The three methods previously discussed: hasNext(), next(), and remove()
• void add(E element): inserts an object immediately before the current cursor position. It must be of type E, the type that the iterator has said it holds.
• void set(E element): replaces (updates) the last element returned by next() and throws an IllegalStateException if the method is called before an element has been returned by next().

ListIterator also has the methods hasPrevious() and previous() to support traversing backwards through a list. We will not go over these methods in detail here, but feel free to review their Javadoc!

These methods also use the iterators cursor, which we can relate back to our example of the computer cursor in a text editing software, such as Microsoft Word. The hasNext() and next() methods work just as we described for Iterator.

add()

Figure 3. Diagram of calling the add() method on the elements: s e n t e c e. The cursor starts at the beginning of the list.

If you have the misspelled word 'sentece' and you want to add the 'n' in to spell the word properly, you use the arrow keys to align the cursor before the character 'c'. Then when you press the 'n' key, the character will be added in the correct location. This is the way the add() method works---it adds an element just before the element that is returned by the next() method, which is the 'c' character in our example.

In the initial step of the above example, the ListIterator<E> cursor starts at the beginning of the list. We then call the next() method five times to move the cursor between the 'e' and 'c'. Next, we call the add() method, which inserts the 'n' just before the cursor. This corrects the spelling of our list and gives us the elements: s e n t e n c e. Since we added the 'n' before the cursor, the cursor is now between the newly added 'n' and the 'c'.

set() with next()

Figure 4. Diagram of calling the set() method on the elements: s e n r e n c e. The cursor starts at the beginning of the list.

The set() method works a bit differently. You now have the misspelled word 'senrence' and you want to replace the 'r' with a 't' to spell the word properly. One possible way to fix this is to use the arrow keys to align the cursor before the 'r', hold the shift key and press the right arrow key to highlight the 'r', and then press the 't' key to replace the 'r'. Similar to the remove() method, the set() method in this example operates on the element that is returned by next() (which in this case is 'r'). After calling the set() method in this way the cursor ends up to the right of the updated element.

In the above example, you can see that the cursor starts at the beginning of the list and next() hasn't returned any values. If you called the set() method now, you would get an IllegalStateException because next() hasn't returned a value to update. We call the next() method four times, moving the cursor between the 'r' and 'e'. The last value returned by the next() method is the element with value 'r'. When we call the set() method, we update the 'r' because it's the last element that was returned by the next() method. Our list is now spelled correctly, and we have the elements: s e n t e n c e.

When you call the set() method, the cursor remains in the same position. In this example, where the set() method updated the element using the last element returned by the next() method, the cursor remains between the newly updated 't' and the 'e'. If you call the set() method again, it will continue to update the element with the value 't', because that is still the last element returned by the next() method. The next() method doesn't care what the value is in that element, it only cares about the element itself, which is represented by the box in our drawing. Since the element still exists, the set() method will continue to update that element until the next() method returns a new element to update!

Iterating over a List

There are many situations where you may need to iterate. For example, you may want to print all the values, or add together the numeric values in a list, etc. Iterators not only helps us traverse a collection, but you can also update (add/remove/set) values in the collection, which you can't do using a normal for loop.

While the Iterator<E> can be used on any Collection, for the rest of this reading we will be discussing the ListIterator<E>, since it has additional methods and functionality.

You can iterate over a list using either a for loop or a while loop. Here's what it looks like using a for loop:

//Iterating over List list using ListIterator
for (ListIterator<String> iterator = list.listIterator(); iterator.hasNext();) {
    System.out.println(iterator.next() + " ");
}

The for loop uses the hasNext() method to continue iterating until hasNext() is false, meaning there are no more values in the list. Inside the loop, we're just printing out the values using the next() method.

Here's what the code looks like using a while loop:

//ListIterator to traverse the list
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()){
    System.out.print(iterator.next() + " ");
}

You will likely see a while loop used to iterate over the list instead of the for loop. This is because the hasNext() method returns a boolean value and therefore has the perfect condition for the while loop.

Manipulating a List

You're creating a grocery list app that allows you to add, remove, and update items on the list using a ListIterator<E>. We're going to walk through using the add(), remove(), and set() methods on a list.

Adding an Element to a List

To add a grocery item to the list, you would do the following:

List<String> groceryList = new ArrayList<>();
ListIterator<String> groceryIterator = groceryList.listIterator();
groceryIterator.add("apples");
groceryIterator.add("bananas");

If you printed out this list, it would look like:

apples bananas

It's important to remember that each item is added before the cursor. Once you add 'apples' to the list, the cursor is after 'apples', so when you add 'bananas', it is placed after 'apples'. You can add as many items to your list as you want, and you can also add duplicates. You could put apples on your list 60 times, if you want!

Updating an Element in a List

We've added apples and bananas to our list, which now looks like this:

apples bananas

You've decided that you've eaten enough apples in the past few weeks and you want to update the list to have oranges, instead.

To update the first element in a list, you could do the following:

ListIterator<String> groceryIterator = groceryList.listIterator();
if (groceryIterator.hasNext()) {
    groceryIterator.next();
    groceryIterator.set("oranges");
}

In this code snippet, we're checking to make sure hasNext() returns true, and if so, we're going to that next() value and then updating the value to 'oranges'. Since we're creating a new instance of ListIterator<String>, the cursor is currently at the beginning of the list, which means the element returned by next() is 'apples'. The set() method therefore updates 'apples' to 'oranges' and our list now looks like this:

oranges bananas

The set() method can only be used, if we've called next() after calling remove() or add(). If remove() or add() have just been called, we need to then use next() so that the set() method knows which element to update.

Remove an Element from a List

You need to be able to delete items from your grocery list as you shop. Let's recreate our shopping list:

List<String> groceryList = new ArrayList<>();
ListIterator<String> groceryIterator = groceryList.listIterator();
groceryIterator.add("oranges");
groceryIterator.add("bananas");

Our list currently looks like this:

oranges bananas

Now, let's delete the oranges from our list:

ListIterator<String> groceryIterator = groceryList.listIterator();
if (groceryIterator.hasNext()) {
    groceryIterator.next(); // returns the element with the value oranges
    groceryIterator.remove();
}

Our list now looks like this:

bananas

Similar to the set() method, the remove() method deletes the element last returned by the next() method. The remove() method can only be called once before you need to call next() again, otherwise you will be attempting to remove the element you just removed and it will throw an IllegalStateException.

Summary

In this reading, we've covered how to use the Iterator<E> and the ListIterator<E> to traverse a given collection and safely access and remove data elements from the collection. Iterator<E> allows you to traverse through any type of collection, although you can only do so in one direction (forward). ListIterator<E> only works for lists, but it's bi-directional so you can traverse a list forward and backwards. Both iterators use a cursor to keep track of your current place in the collection. There are lots of real-world applications for the Iterator<E>--we can use it to maintain a HashMap<K, V> collection of flashcards or use a ListIterator<E> to implement and maintain a grocery list!

Guided Project