Iterator

Suppose you want a single method that prints every item in a collection, no matter how that collection is stored. The difficulty is that each familiar storage form has its own way of being walked. An array is walked with a for loop over its indices. A linked list is walked with a while loop that moves a pointer from node to node. A binary tree is walked with a recursive subroutine that performs an inorder traversal. Because collections take these and many other forms, a method written for one form cannot simply be reused for another.

The solution this course uses is the iterator. An iterator is an object whose job is to traverse a collection. Each collection type supplies its own iterator internally, so the details differ from one type to another. What stays constant is how you call the iterator. Once you learn that calling pattern, the same loop shape works for any collection that provides an iterator. This article starts with the calling pattern, then explains the cursor model behind the more powerful ListIterator used for lists.

The Iterator interface is parameterized, written Iterator<T>, where T is the type of the items. If a collection implements Collection<T> for some type T, then calling coll.iterator() returns an Iterator<T> with that same T. The interface defines exactly three methods that matter for a basic traversal, and each plays a different role in the loop. The method hasNext() reports whether any items remain. The method next() returns the next item and advances the iterator. The method remove() deletes the item most recently returned by next().

Read the loop from top to bottom as a conversation between the loop, the iterator, and the collection. The collection is asked for an iterator exactly once. After that, the loop alternates between asking whether items remain and asking for the next one. The loop never touches the collection's internal storage. Everything it needs passes through the iterator, which is why the same loop shape works for arrays, linked lists, and trees alike.

Lists keep their elements in a definite order, and many tasks need to move both forward and backward, or to insert and replace items at a chosen spot. For that reason Java provides a richer kind of iterator for lists. The method list.listIterator() returns a ListIterator<T>, an interface that extends Iterator<T>. Everything an ordinary iterator can do, a ListIterator can also do, and it adds more.

The most useful mental model is to stop thinking of an iterator as sitting on an item. Instead, think of it as pointing to a position. That position is either at the very beginning of the list, at the very end, or in the gap between two neighboring elements. Items are never under the iterator in this model; the iterator sits in the spaces between them. A list with n items always has n plus 1 possible cursor positions. For the three fruits apple, mango, and plum, there are four positions: before apple, between apple and mango, between mango and plum, and after plum. Keeping this count in mind makes insertion behavior predictable.

The cursor structure is practical because of how LinkedList<T> stores its items. Its nodes are doubly linked: each node holds a pointer to the next node and a pointer to the previous node. Because of those two pointers, the iterator can step forward and backward through the nodes without restarting from the front. LinkedList also keeps a tail pointer that marks the last node, which speeds up addLast() and getLast(), but that tail pointer is not needed for iterator movement itself.

Every method acts relative to the cursor's current gap. The two movement methods cross one item and hand that item back to you. The method next() moves one space to the right and returns the item it just passed. The method previous() moves one space to the left and also returns the item it passed. Both return values are what you can inspect while traversing.

The editing methods are where beginners most often get confused, because remove() and set() act on the item the cursor passed most recently, not on the gap itself. The method remove() deletes that most recently passed item, whether it was passed by next() or previous(). The method set(obj) replaces that same item instead of deleting it. The method add(obj) behaves differently: it inserts obj at the cursor's current gap, either between two existing items or at the front or end of the list. Remove and set need a recently passed item to act on, while add needs only the gap. That is why the sorted-insertion technique uses add() after the cursor has been positioned, and does not need next() immediately before it.

The sorted-insertion technique keeps a list in ascending order. The idea is to start the iterator at the front and walk forward past every item that is smaller than the new string. When the iterator reaches the first item that should come after the new string, it has found the right gap, and add() places the new string there. The only step that needs care is the comparison. The rule is simple: if newItem.compareTo(item) gives zero or a negative number, newItem belongs before item.

Follow the two directions the routine allows. If the new string is bigger than the current item, the loop keeps advancing. If the new string is less than or equal to the current item, the routine steps the iterator back one space with previous(), so the cursor sits in the gap just before that item, and then leaves the loop. The other exit happens when hasNext() is false, which means every item was smaller. The iterator is then already at the end, so add() appends the new string.

The routine is short, so each mistake usually shows up as a subtle wrong position rather than a crash. The mistakes below are the ones most likely to produce an insertion that is almost right but out of order.

The same general loop can also remove items. Doing the removal through the iterator, with iter.remove(), keeps the traversal consistent. Changing the collection directly during the walk bypasses the iterator's bookkeeping about its position. The example below removes every null value from a collection of Color objects.