Object oriented program strives to decouple a classes implementation from its functionality. In brief, a List could be implemented using an array, a linked list, a binary search tree, or a hashtable, and function in the same way. This is effectively managed through the use of interfaces.
But if a class is a container, and its functionality is de-coupled from its implementation, then how will our users now how to traverse that container? Enter the iterator pattern.
Iterators and the Iterator Pattern
If your familiar with how the C++ STL works then you know it is HEAVILY reliant on the iterator pattern for navigating its containers. Java too implements iterators and it is the key to its for each loop.
So what is an iterator? An iterator is an object that tracks a pointer into the container, and returns the data held at said point in the container. Lets use a linked list to demonstrate the basic strategy.
Java offers us the interfaces Iterable, and Iterator. Any class that implements Iterator must provide the following methods:
- hasNext() – a boolean value denoting if we have reached the end of the container or not.
- next() – returns the data held at the current position in the container , and then advances the position by one.
- remove() – this method is optional to implement, but must be declared to fulfill the contract of implementing Iterator.
To illustrate our point lets build. a simple container that supports two operations: add an item to the list, and traverse the list.
public class LNode<E> {
private E info;
private LNode<E> next;
public LNode(E i) {
info = i;
}
LNode<E> getNext() { return next; }
E getInfo() { return info; }
}
public class LList<E> {
private LNode<E> head;
private int N;
public LList() { }
public void add(E info) {
LNode<E> t = new LNode<E>(info);
t.setNext(head);
head = t;
N++;
}
}
With our Node class and LList class, we have the necessary pieces to build a list, but how do we access the list to traverse it without exposing its internal implementation? This of course is the focus of this article, and is accomplished in very straight forward way thanks to the previously discussed iterators.
The first think we need to do, is import the iterator package into our LList class, and have our LList class implement the Iterable interface. To satisfy the Iterable contract, we must implement the iterator() method for it:
import java.util.Iterator;
public class LList<E> implements Iterable<E> {
private LNode<E> head;
private int N;
public LList() { }
public void add(E info) {
LNode<E> t = new LNode<E>(info);
t.setNext(head);
head = t;
N++;
}
public Iterator<E> iterator() {
return new ListIterator<E>(head);
}
}
And now we implement our actual iterator class, implementing the methods needed to fulfill the Iterator interface contract:
import java.util.Iterator;
public class ListIterator<E> implements Iterator<E> {
private LNode<E> curr;
public ListIterator(LNode<E> c) {
curr = c;
}
public boolean hasNext() { return curr != null; }
public E next() {
E ret = curr.getInfo();
curr = curr.getNext();
return ret;
}
public void remove() { }
}
With these simple changes to our list implementation we can now use Javas built in for-each construct to traverse our list as if it was an array, a HashSet or any other traversable container:
public class LLClient {
public static void main(String[] args) {
LList<Integer> list = new LList<>();
for (int i = 1; i < 11; i++)
list.add(i);
for (int n : list) {
System.out.print(n + " ");
}
}
}
[Running] cd "c:\Users\mgoren\algex\" && javac LLClient.java && java LLClient
10 9 8 7 6 5 4 3 2 1
[Done] exited with code=0 in 1.046 seconds
And there you have it: the Iterator pattern. I hope this gives your another tool for your toolbox to help take your coding to the next level, and as always, Happy hacking!
