Having a grocery list that's written in a language you don't understand is just as good as no list at all. Likewise, when using a data structure you don't fully understand, not knowing how to iterate over the data can turn an otherwise powerful structure into a useless chunk of ram real estate. To ease the burden on developers when it comes to navigating complex data structures, it helps to implement an iterator design pattern!

Assumptions

What is an Iterator?

In computer science, an iterator is an object that allows a collection of objects to be traversed without exposing the representation of that collection. For instance, a collection can be an array, a list, a tree, and so on.

<div style="width:100%; margin:auto;text-align:center;"><img src="https://www.devmaking.com/img/topics/designpatterns/IteratorPattern_01.png" alt="iterator UML diagram" style="max-width:95%;"> </div>

Key components:

  • Iterator: an interface that defines methods needed to traverse a collection.
  • Concrete Iterator: an implementing class of the iterator. This class is often found inside of the aggregate class.
  • Aggregate: an interface that defines an aggregate class that will make use of an iterator.
  • Concrete Aggregate: an implementation of the aggregate interface which uses an iterator.

If a list and a tree implement the same iterator interface, then the client doesn't need to know how to explicitly traverse a tree or a list, only the iterator!

Conceptualization

Most languages offer built-in support for iterating over a collection, however it is still useful to know how to create one yourself to understand their usefulness. A typical Iterator interface looks like this:

interface Iterator&lt;T&gt; {
   // Is there another element in the collection?
   boolean hasNext();
   // Return the next element in the collection
   T next();
 }

> We won't use this interface for the following example, but this is what a generic, language agnostic iterator interface might take shape of.

To conceptualize a scenario where we would use an iterator, let's represent a book composed of pages that have their own content. Each BookPage object acts like a <a href="https://www.devmaking.com/learn/data-structures/linked-list/" target="_blank" style="color:inherit;">Linked List</a> node, containing a pointer to the next page in the book:

class BookPage {
   String content;
   // Uses a linked-list style for our list:
   BookPage next;
   
   BookPage(String content) {
     this.content = content;
   }
 }

With our book page class defined, let's define our book class that is composed of many book pages:

class Book {
   // Maintains the "root" of the list:
   BookPage coverPage;
   
   // Inserts a new page:
   void addPage(String content) {
     BookPage tmp = coverPage;
     while(tmp.next != null) {
       tmp = tmp.next;
     }
     tmp.next = new BookPage(content);                     
   }
 
     // More methods... 
 }

This is all very basic so far; using a linked-list style, we've defined a custom list called Book. While this is nice for storage needs, we're still missing a way for an outside client to be able to traverse the book page-by-page; after all, what good is a list that cant be iterated?!

Because we're using our own implementation of a linked list here, we'll need to define our own iterator class for the book which we'll define as BookIterator. We'll be implementing method's from the iterator interface briefly touched on above.

Our iterator will start at the root node of our book (coverPage). Each time the next() method is executed, we'll go to the next BookPage in the linked list and return it. By creating a separate class for our iterator, we can easily have multiple iterator objects looking at the same collection without needing to do much work in the collection class. Additionally, since we'd like to not expose the coverPage of our book class, we'll be defining this iterator class inside of the Book class so that the iterator has access:

class Book {
   // code from earlier ...
   
   // Gets a book iterator:
   BookIterator getIterator() {
     return new BookIterator();
   }
   
   /* ... */
   
   // Our iterator implementation as a private class:
   private class BookIterator {
     // The page that the iterator is currently on:
     BookPage currentPage;
     
     BookIterator() {
       // Set the current page to the book's cover page:
       currentPage = coverPage;
     }
     
     boolean hasNext() {
       return currentPage.next != null;
     }
     
     BookPage next() {
       if(!hasNext()) {
         throw Exception("No more elements!");
       }
       else {
         currentPage = currentPage.next;
         return currentPage;
       }
     }
   }
   
 }

The power of an iterator comes into play when a client doesn't want to figure out how to traverse a data structure themselves, and it also allows the iteration to be stopped and resumed at a later time by only moving forward to the next page when the next() method is executed.

Client code:

static void main(String[] args) {
   // Creating our book:
   Book myBook = new Book();
   // Adding a few (short) pages to our book:
   myBook.addPage("My Story");
   myBook.addPage("Chapter 1...");
   myBook.addPage("Chapter 2...");
   myBook.addPage("Epilogue...");
   
   // Getting an iterator for our book:
   BookIterator iterator = myBook.getIterator();
   // While there is another page to read...
   while(iterator.hasNext()) {
     // .. iterate to it and print the contents:
     BookPage page = iterator.next();
     print(page.content);
   }
 }

> Challenge: implement an iterator for a <a href="https://www.devmaking.com/learn/data-structures/binary-search-tree/" target="_blank" style="color:inherit;">Binary Tree</a>!