Skip to content

Iteration

Say we want to support iteration over our stack items from the client but we don’t want to reveal the internal representation (array or LinkedList) of the stack. Java provides a nice solution to this called iteration. This can be applied to multiple data structures (no matter which implementation we use).

An Iterable is a class that has a method that returns an Iterator.

public interface Iterable<Item>{
Iterator<Item> iterator();
}

Has methods hasNext() and next(), Java also allows remove however this could lead to insidious debugging problems.

public interface Iterator<Item>{
boolean hasNext();
Item next();
//optional and risky
void remove();
}

Providing an option to make our data structures Iterable ensures we support an elegant and clean approach to our client. A long form of code without an Iterable structure could look like:

Iterator<String> i = stack.iterator();
while (i.hasNext()){
String s = i.next();
StdOut.prinln(s);
}

where as a shorthand version of this could be as simple as:

for(String s: stack){
StdOut.println(s);
}

Stack Iterator: Linked-list implementation

Section titled “Stack Iterator: Linked-list implementation”
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
...
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
public boolean hasNext() { return current != null;}
public void remove() { /* Not Supported */ }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
...
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item>{
private int i = N;
public boolean hasNext() { return i > 0;}
public void remove() { /* Not Supported */ }
public Item next() { return s[--i]; }
}
}

For a lot of clients the order of inserting and removing data into our collection is not important leading us to the bag data structure.

Bag() // create an empty array
void add(Item x) //insert a new item onto bag
int size() number of items in bag
Iterable<Item> iterator() //iterator for all items in bag

The bag API is a simple narrow set of operations not putting any focus on order of items in the collection utilising only add operations. For a stack this would be the same without the pop() operation and for queue this would be the same without the dequeue() operation.