Writing Iterators

Here is the Set interface. It extends Iterable<T>, so every set must supply an iterator() method:

public interface Set<T> extends Iterable<T> {
  boolean add(T item);       // adds item if it is absent; returns true if the set changed
  boolean remove(T item);    // removes item if it is present; returns true if the set changed
  boolean contains(T item);  // returns true if item is in the set
  int size();                // returns the number of items in the set
  // inherited from Iterable<T>:
  // Iterator<T> iterator(); returns an iterator over the items, in no promised order
}

Here is the Iterator<T> interface:

public interface Iterator<T> {
  boolean hasNext();  // returns true if there are items left to return; does not advance
  T next();           // returns the next item and advances past it;
                      // throws NoSuchElementException if there are no items left
}

ArraySet<T> stores its items in a backing array, at indices 0 through size - 1:

public class ArraySet<T> implements Set<T> {
  private T[] arr;   // the backing array
  private int size;  // how many items the set holds

  // add, remove, contains, and size are already implemented

  @Override
  public Iterator<T> iterator() {
    return null;  // TODO
  }
}

LinkedSet<T> stores its items in a singly linked list:

public class LinkedSet<T> implements Set<T> {
  private Node<T> head;  // the first node, or null when empty
  private int size;      // how many items the set holds

  private static class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
      this.value = value;
    }
  }

  // add, remove, contains, and size are already implemented

  @Override
  public Iterator<T> iterator() {
    return null;  // TODO
  }
}

@Override
public Iterator<T> iterator() {
  return new ArraySetIterator();
}

private class ArraySetIterator implements Iterator<T> {
  private int cursor = 0;  // index of the next item to return

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return arr[cursor++];
  }
}

@Override
public Iterator<T> iterator() {
  return new LinkedSetIterator();
}

private class LinkedSetIterator implements Iterator<T> {
  private Node<T> current = head;  // node holding the next item to return

  @Override
  public boolean hasNext() {
    return current != null;
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    T element = current.value;
    current = current.next;
    return element;
  }
}