Iterators

Plugin your collection with Iterators, and feel the magic.

OMAR ELGABRY
Jan 6, 2017 · 4 min read
Insert a quarter and Turn the crank

What’s The Problem?

What if we want to iterate over items in a collection(stack, queue, …), without revealing the implementation, whether we are using an array or a linked list. In Java, it can be done by implementing the “Iterable” Interface.

Iterable & Iterator Interfaces

The Iterable Interface has a method called iterator. This method returns an “Iterator” object.

The Iterator Interface is interface that has next, and hasNext methods. The class implements the iterator interface will be used to iterate over the items in a collection.

Now, to show an example on how to use these interfaces to make a collection iterable, we will use Stacks as an example. But, you can apply the same steps on whatever collection type you have.

How To Make A Stack Iterable?

First, we need to see how a Stack class may look like.

public class Stack<Item> {
private Node first = null;

private class Node {
Item item;
Node next;
}

public void push(Item item) { /* … */ }
public Item pop() { /* … */ }
}

It can be either implemented using a linked list, or an array. Either ways, you are going to follow the same steps:

The Stack class should implement Iterable Interface.

import java.util.Iterator;public class Stack<Item> implements Iterable<Item> { /* … */ }

Notice that Iteratble and Iterator are both generic interfaces. So, Stack class must also be generic class. Because you are going to iterate over the items of a generic type within the stack.

Override the method of Iterable Interface called iterator. It returns an Iterator object of a generic type.

public Iterator<Item> iterator() { return new StackIterator(); }

Now, It’s clear that we need to create a class called “StackIterator”, which needs to implement the Iterator Interface.

Create an inner class which implements Iterator Interface. You’ll need to maintain a reference to the current item the iterator points to.

private class StackIterator implements Iterator<Item> {
private Node current = first;
}
public boolean hasNext()  { return current != null;  }

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}

Again, you’ll follow the same steps. Just some minor changes to work with arrays instead of linked lists.

private class StackIterator implements Iterator<Item> {
private int i = N;
public boolean hasNext() { return i > 0; }

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return s[--i];
}
}

Yes, there are. You can make a collection Iterable by using another Iterable collection.

For example, having a Map, a collection of key-value pairs, where we want to iterate over the keys. We can store all the keys in a stack or a queue(Iterable object), and use that stack or queue to iterate over the keys.

There are two ways to do that, one way is to implement the Iterable Interface in Map class (just same as we did with stack).

The implementation of iterator() method in the Map class is simple; Just return the iterator() method of the chosen Iterable object; whehter a stack, or queue, or any Iterable object. This is exact implementation as we did with stacks.

public class Map<Key, Value> implements Iterable<Key> {
// ...

public Iterator<Key> iterator() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < N; i++)
queue.enqueue(keys[i]);
return queue.iterator(); // return an Iterator object
}
}

Another way is to return the Iterable object itself. Thus, no need for the Map class to implement the Iterable Interface. Just define a method, let’s say keys(), which fills up the Iterable object with the keys, and return it. Now, we can use the returned Iterable object to iterate over the keys.

The downside of this approach is Map is not an Iterable object, since it doesn’t implement the Iterable Interface. We have to use keys() method to get access to an Iterable object, which will be used to iterate over the keys.

public class Map<Key, Value> {
// ...

public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < N; i++)
queue.enqueue(keys[i]);
return queue; // return an Iterable object
}
}

The foreach Loop Vs Iterator

Now, It’s time to taste the outcome of what we’ve done so far. We can write an elegant code to iterate over items in a collection without revealing the implementation.

Stack<Apple> stack = new Stack<Apple>();
stack.push(new Apple());
// ...
Iterator<Apple> it = stack.iterator();
while(it.hasNex()) {
Apple a = it.next();
System.out.println(a);
}

The foreach loop is a shorthand notation for iterating over an iterable collection.

foreach(Apple a: stack)
System.out.println(a);

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

OMAR ELGABRY

Written by

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade