Java ListIterator

ListIterator<E> extends Iterator<E> with everything a list can support that a generic iterable cannot: walking backwards, asking for the current index, and adding or replacing elements during iteration. It's available on every List<E> via list.listIterator() and list.listIterator(int startAt).

If you're iterating a Set or a Queue, this chapter doesn't apply — those collections have no positions. For List, ListIterator is the cursor that does everything the plain Iterator does, plus the four list-specific operations.

What ListIterator adds

public interface ListIterator<E> extends Iterator<E> {
  // inherited:
  boolean hasNext();
  E next();
  void remove();
  // new:
  boolean hasPrevious();
  E previous();
  int nextIndex();
  int previousIndex();
  void set(E e);
  void add(E e);
}

Three new capabilities:

1. Bidirectional walk. hasPrevious() / previous() move the cursor backwards. previous() throws NoSuchElementException past the start.
2. Position reporting. nextIndex() returns the index next() would return; previousIndex() returns the index previous() would return. They differ by 1.
3. In-place edits. set(e) replaces the element most recently returned by next or previous. add(e) inserts a new element between the previous and next cursor positions.

The cursor model

The trick to understanding ListIterator is to picture the cursor as sitting between elements, not on them:

       [ "a"   "b"   "c" ]
        ^     ^     ^     ^
        0     1     2     3      <- nextIndex() values

next() returns the element to the right of the cursor and advances. previous() returns the element to the left and moves back. Just after next() returns "b":

       [ "a"   "b"   "c" ]
                    ^
              previousIndex()=1, nextIndex()=2

A subsequent set("B") replaces "b". A subsequent add("x") inserts "x" between "b" and "c". A subsequent remove() deletes "b". Only one of set, add, or remove can be called once per next/previous — calling two in a row, or calling any of them without an intervening next/previous, throws IllegalStateException.

Bidirectional traversal

List<String> letters = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> it = letters.listIterator();
while (it.hasNext()) System.out.print(it.next() + " ");      // a b c
while (it.hasPrevious()) System.out.print(it.previous() + " "); // c b a

Both loops use the same iterator. After the forward loop ends, the cursor is past "c"; the backward loop starts there and walks home. You can flip direction mid-walk too — call next() then previous() and you get the same element back both times, because the cursor moved past it and then back over it.

In-place editing during iteration

This is the headline reason to use ListIterator instead of a plain Iterator:

List<String> words = new ArrayList<>(List.of("alpha", "beta", "gamma"));
ListIterator<String> it = words.listIterator();
while (it.hasNext()) {
  String w = it.next();
  if (w.startsWith("a")) it.set(w.toUpperCase());     // replace in place
  if (w.equals("beta"))  it.add("BETA-extra");        // insert after beta
}
// words is now [ALPHA, beta, BETA-extra, gamma]

set is the only safe way to replace an element during iteration. add is the only safe way to insert an element during iteration. Both update the iterator's internal expected-modification count, so neither triggers a ConcurrentModificationException.

add deserves a second look: it inserts at the cursor — between the most recent next result and the next next result. After the insertion, the cursor is past the new element, so the very next it.next() returns the original next element, not the one you just added. That's almost always the behaviour you want when you're "expanding" an element in place.

A common gotcha: previous() returns the same element you just returned with next()

ListIterator<String> it = letters.listIterator();
it.next();      // "a", cursor between a and b
it.previous();  // "a" again, cursor between (start) and a

This trips people up. The cursor's position changes after next, but previous walks back over the same element. If you want the element before the current one, you have to call previous twice — once to step back over what you just returned, once to actually read the previous.

Starting at a specific index

ListIterator<String> it = list.listIterator(3);    // start with cursor before index 3

The two-arg form positions the cursor before the given index. it.nextIndex() returns 3, it.previousIndex() returns 2, and the very first next() returns list.get(3). Useful when you've already located a starting point with indexOf or binarySearch and want to walk from there in either direction.

LinkedList vs ArrayList: same interface, different cost

Both expose ListIterator. The cost profile differs:

• ArrayList — next/previous are O(1); add/remove during iteration are O(n) because they shift the array tail. The set operation stays O(1).
• LinkedList — next/previous are O(1) (the iterator caches the node); add/remove via the iterator are O(1) because no shifting happens. The same operations via index on a LinkedList are O(n) — index lookups walk the chain.

If you find yourself iterating a LinkedList and calling list.add(index, ...) inside the loop, you're walking the chain twice per insertion. Use the ListIterator and you're paying O(1) per operation, which is the whole reason LinkedList exists.

A worked example: bidirectional walk, in-place edits, index reporting, costed ops

The program below walks a list forwards and backwards on the same iterator, replaces and inserts elements in-place, reports indices as it goes, and times the difference between iterator-based and index-based modification on a LinkedList.

What to take from the run:

• The forward and backward walks happen on the same ListIterator. Once the forward loop exhausts hasNext, the cursor is past the last element and hasPrevious becomes true.
• set replaced "alpha" with "ALPHA" and add("BETA-extra") inserted a new element right after "beta" — and the iterator survived both modifications without a ConcurrentModificationException.
• next() then previous() returned the same element. The cursor moved past it and then back over it; what looked like two reads of "different" elements is actually one element traversed twice.
• On a LinkedList, the iterator-based version of "drop every other element" was dramatically faster than the index-based version. Index lookup on a linked list is O(n); the iterator caches its node and the deletion is O(1).

What's next

Iterator and ListIterator handle the traversal side of working with collections. The other half of "doing things with elements" is ordering them: telling Java when one element is less than, equal to, or greater than another. That's what Comparable and Comparator cover — natural order baked into the type itself, and external orderings you supply per operation. They're the foundation everything else in this part of the book rests on, including the sort and search utilities.

Practice