Iterating the Keys

Here is the Map interface:

public interface Map<K, V> {
  boolean put(K key, V value);  // stores value under key, replacing any old value;
                                // returns true if the key was not present before
  V get(K key);                 // returns the value stored under key, or null if key is absent
  boolean remove(K key);        // removes key and its value if key is present;
                                // returns true if the map changed
  boolean containsKey(K key);   // returns true if key is in the map
  int size();                   // returns the number of key-value pairs in the map
}

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
}

ArrayMap<K, V> stores its pairs in a backing array of entries, at indices 0 through size - 1:

public class ArrayMap<K, V> implements Map<K, V> {
  private Entry<K, V>[] arr;  // the backing array
  private int size;           // how many pairs the map holds

  private static class Entry<K, V> {
    K key;
    V value;
  }

  // the Map operations are already implemented
}

LinkedMap<K, V> stores its pairs in a singly linked list, one node per pair:

public class LinkedMap<K, V> implements Map<K, V> {
  private Node<K, V> head;  // the first node, or null when empty
  private int size;         // how many pairs the map holds

  private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;
  }

  // the Map operations are already implemented
}

public interface Map<K, V> extends Iterable<K> {
  // the five operations as before
}

@Override
public Iterator<K> iterator() {
  return new KeyIterator();
}

private class KeyIterator implements Iterator<K> {
  private int cursor = 0;  // index of the entry whose key comes next

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

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

@Override
public Iterator<K> iterator() {
  return new KeyIterator();
}

private class KeyIterator implements Iterator<K> {
  private Node<K, V> current = head;  // node whose key comes next

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

  @Override
  public K next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    K key = current.key;
    current = current.next;
    return key;
  }
}