Table of Contents
Introduction
The Iterator is an object-oriented behavioral design pattern that focuses on iterating over a Collection of items. The strength of the pattern comes from the fact that it doesn’t matter which kind of collection it is, whether it is a list, stack, queue, tree or something else. Some data structures are not so straightforward when you want to make sure you visit each entry. The iterator pattern offers a consistent interface/method to iterate over any collection of items.
Use Cases
- You want iteration logic decoupled from data structure implementation.
- You want uniform access to iterate over a collection.
Pitfalls
- You need more advanced accessing methods.
- Performance overhead with large and/or complex collections.
Java example
To get a grasp of the iterator pattern, let’s create a custom Collection which we call PriorityList. This class will implement the Java.util.Collection interface and keeps an ArrayList of items with a Low, Normal and/or High priority. We only implement the interface methods which we use for this demonstration.
Because most iterators mainly depend on two methods, hasNext() and next(), we will implement the Iterator interface that Java provides.
PriorityList Class
Because we extends the java.util.Collection interface, we need to override all methods of the interface. In this example, we ignore the content of some of them. Keep in mind that this is still a working example. The Collection interface also wants us to implement: public Iterator<E> iterator() { } as is done in the PriorityList example class.
Under the hood of the class, we keep a HashMap<Integer, ArrayList> where the integer is a stand in for a High, Normal or Low priority list. We can add items of the defined datatype<E> to a priority.
When we return the iterator instance of our class, it makes sure that the items it will iterate over are sorted from highest priority to lowest. So it will iterate over the higher prioritized items first.
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
public class PriorityList<E> implements Collection<E> {
public enum PRIORITY {
HIGH(2),
NORMAL(1),
LOW(0);
private final Integer value;
PRIORITY (final Integer newValue) {
value = newValue;
}
public Integer getValue() {
return value;
}
}
private HashMap<Integer, ArrayList<E>> priorityList = new HashMap<Integer, ArrayList<E>>();
public PriorityList() {
this.priorityList.put(PRIORITY.LOW.value, new ArrayList<E>());
this.priorityList.put(PRIORITY.NORMAL.value, new ArrayList<E>());
this.priorityList.put(PRIORITY.HIGH.value, new ArrayList<E>());
}
@Override
public int size() {
return this.priorityList.keySet().stream().mapToInt(key -> this.priorityList.get(key).size()).sum();
}
@Override
public boolean isEmpty() {
return this.priorityList.keySet().stream().mapToInt(key -> this.priorityList.get(key).size()).sum() == 0;
}
@Override
public boolean contains(Object o) {
return this.priorityList.keySet().stream().anyMatch(key -> this.priorityList.get(key).contains(o));
}
/**
* Add item with normal priority
* @param e
* @return true when succeeds adding item
*/
@Override
public boolean add(E e) {
return add(PRIORITY.NORMAL.value, e);
}
public boolean add(Integer priority, E e) {
try {
ArrayList<E> list = this.priorityList.get(priority);
list.add(e);
return true;
}
catch(Exception exception) {
System.out.println(exception.toString());
}
return false;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int index = 0;
private final List<E> items;
{
items = new ArrayList<>();
priorityList.keySet().
stream().
sorted(Comparator.reverseOrder()).
forEach(priority -> items.addAll(priorityList.get(priority)));
}
@Override
public boolean hasNext() {
return index < size();
}
@Override
public E next() {
return items.get(index++);
}
};
}
@Override
public Object[] toArray() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public <T> T[] toArray(T[] a) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public boolean containsAll(Collection<?> c) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public void clear() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public boolean addAll(Collection<? extends E> c) {
throw new UnsupportedOperationException("Not supported yet.");
}
}
Main Class
In the Main class we instantiate our PriorityList with String as datatype. We then add some High, Normal and Low priority Strings to the list, at random.
When we now ask our class to return the iterator and iterate over the items it holds, it will print them in prioritized order.
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
PriorityList<String> collection = new PriorityList<>();
collection.add("Normal 2");
collection.add(PriorityList.PRIORITY.LOW.getValue(), "Not Important 3");
collection.add(PriorityList.PRIORITY.HIGH.getValue(), "Very Important 1");
collection.add("Normal 4");
collection.add("Normal 3");
collection.add(PriorityList.PRIORITY.HIGH.getValue(), "Very Important 3");
collection.add(PriorityList.PRIORITY.LOW.getValue(), "Not Important 1");
collection.add(PriorityList.PRIORITY.LOW.getValue(), "Not Important 2");
collection.add("Normal 1");
collection.add(PriorityList.PRIORITY.HIGH.getValue(), "Very Important 2");
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
print(iterator.next());
}
}
public static void print(String str) {
System.out.println(str);
}
public static void print(int i) {
System.out.println(""+i);
}
public static void print(boolean b) {
System.out.println(""+b);
}
}
Output:
Very Important 1
Very Important 3
Very Important 2
Normal 2
Normal 4
Normal 3
Normal 1
Not Important 3
Not Important 1
Not Important 2
Class Diagram
The image shows a general way to how the classes are structured. The Collection happens to extend the Iterable interface. This interface expects us to implement the hasNext() and next() methods for our CustomCollection (PriorityList in the example), which implements Collection.
In the code example, the Iterator is implemented as an anonymous inner class in PriorityList.
Conclusion
The iterator design pattern is a way to standardize iterating over / traversing collections, regardless of the underlying structure. In the example, the iteration logic is part of our collection (PriorityList) but could be detached and written separately from it as well.
References
Freeman, E., Bates, B., & Sierra, K. (2004). Head first design patterns.
Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design Patterns: Elements of Reusable Object-Oriented Software.
Wikipedia contributors. (2024). Software design pattern. Wikipedia. https://en.wikipedia.org/wiki/Software_design_pattern
