Iterator Interface

Overview¶

You may access the full list of Java’s Interface Iterator for more detail.

Recap¶

An iterator is a type of object that lets a client efficiently iterate over a data structure using a forEach loop. Whenever we write code like:

for (String item : something) {
    // ...etc...
}

Java will internally convert that code into the following:

Iterator<String> iter = something.iterator();
while (iter.hasNext()) {
    String item = iter.next();
    // ...etc...
}

When you call iter.next for the first time, the iterator will return the first item. If you call it again, it will return the second item.

If the user calls iter.next after the iterator has gone through all items, the method will throw a NoSuchElementException. iter.hasNext helps avoid this by returning true if calling iter.next will safely return a value, and false otherwise.

Implementation Requirements and Notes¶

• You may NOT create any new temporary data structures inside of your iterators.
• Your iterator methods must run in $\mathcal{O}(1)$ time with respect to the size of the map.
• Your iterators may return entries in any order although the easiest approach is to return them in the same order as your map’s internal representation.

• You may assume that the user will not modify your maps while your iterators are in use.

  For example, the following will never happen:

  Iterator<Entry<String, Integer| itr = map.iterator();
  itr.next();
  // the following line should never happen if the same
  // iterator instance is used later
  map.put("hi", "373");
  itr.next();