☕ JavaCollections Framework

ListIterator

ListIterator extends Iterator to provide bidirectional traversal of List elements, along with the ability to add, set, and remove elements during iteration. Where Iterator can only move forward and only remove the current element, ListIterator can move both forward and backward, can query the current index (nextIndex, previousIndex), can replace the last element returned (set), and can insert a new element at the current position (add). ListIterator is specific to List — it is obtained from List.listIterator() and only applies to ordered, indexed collections. This entry covers all ListIterator methods, bidirectional traversal patterns, the state model for set and add, practical use cases, and how ListIterator enables in-place list transformation.

ListIterator Methods — Bidirectional Traversal

ListIterator<T> extends Iterator<T> and adds six methods. The forward traversal methods hasNext() and next() work identically to Iterator. The backward traversal methods hasPrevious() returns true if there are elements before the current position, and previous() returns the previous element and moves the cursor back. The index query methods nextIndex() returns the index of the element that would be returned by the next call to next(), and previousIndex() returns the index that would be returned by the previous call to previous(). These indices are always adjacent: nextIndex() == previousIndex() + 1. When positioned before the first element, previousIndex() returns -1 and nextIndex() returns 0. When positioned after the last element, previousIndex() returns size-1 and nextIndex() returns size. ListIterator maintains a cursor that sits between elements, not on elements. The cursor's position determines what next() and previous() will return. After calling next(), the cursor moves one position to the right — the returned element is now to the left of the cursor. After calling previous(), the cursor moves one position to the left — the returned element is now to the right of the cursor. This means calling next() and then previous() returns the same element twice, which is correct behavior for a cursor-based model. The three modification methods — add(), set(), and remove() — operate on the element most recently returned by next() or previous(). The set() method replaces the last returned element. The remove() method removes the last returned element. The add() method inserts a new element immediately before the cursor position (before what next() would return). These three methods cannot be called in certain combinations, governed by the iterator's state machine.

Java

// ── ListIterator creation ─────────────────────────────────────────────
List<String> list = new ArrayList<>(
    List.of("A", "B", "C", "D", "E"));

// Start from the beginning:
ListIterator<String> it = list.listIterator();

// Start from a specific index:
ListIterator<String> fromMiddle = list.listIterator(2);  // cursor before index 2

// ── Forward traversal ─────────────────────────────────────────────────
while (it.hasNext()) {
    int idx    = it.nextIndex();       // index of next element
    String val = it.next();            // returns element, advances cursor
    System.out.printf("[%d]=%s ", idx, val);
}
// [0]=A [1]=B [2]=C [3]=D [4]=E

// ── Backward traversal ────────────────────────────────────────────────
// it is now positioned after last element — traverse backward
while (it.hasPrevious()) {
    int idx    = it.previousIndex();   // index of previous element
    String val = it.previous();        // returns element, retreats cursor
    System.out.printf("[%d]=%s ", idx, val);
}
// [4]=E [3]=D [2]=C [1]=B [0]=A

// ── Index queries ─────────────────────────────────────────────────────
ListIterator<String> pos = list.listIterator(2);  // cursor before index 2
System.out.println(pos.nextIndex());     // 2 — C would be returned by next()
System.out.println(pos.previousIndex()); // 1 — B would be returned by previous()

pos.next();  // returns C, cursor moves to between C and D
System.out.println(pos.nextIndex());     // 3 — D would be returned by next()
System.out.println(pos.previousIndex()); // 2 — C would be returned by previous()

// ── next() then previous() returns same element ───────────────────────
ListIterator<String> cursor = list.listIterator(1); // before B
String forward  = cursor.next();      // B — cursor now between B and C
String backward = cursor.previous();  // B — cursor now between A and B again
System.out.println(forward.equals(backward));  // true — same element

Modification Methods — add, set, remove

The three modification methods add(), set(), and remove() operate within a state machine. The state starts in "fresh" (no element returned yet). After a successful call to next() or previous(), the state is "element returned." set() and remove() are valid only in "element returned" state — they throw IllegalStateException in "fresh" state or after add() or remove() has already been called without an intervening next() or previous(). After add() or remove(), the state returns to "fresh" for modification purposes. set(element) replaces the element most recently returned by next() or previous(). The cursor position does not change. This is the most efficient way to transform elements in a list in-place — it avoids the overhead of getting and setting by index in linked lists. remove() removes the element most recently returned by next() or previous(). It adjusts the cursor appropriately: if the last call was next(), the element to the left is removed; if previous(), the element to the right. The cursor's logical index adjusts so that the element that would be returned by the next call to next() or previous() is the same as it would have been without the removal. add(element) inserts the new element immediately before the cursor (before what next() would return, after what previous() has just returned). After add(), the new element is to the left of the cursor, so the next call to next() would skip over it (returning what it was going to return before the add), but the next call to previous() would return the newly added element. The cursor's nextIndex() and previousIndex() both increment by 1 after add().

Java

// ── set() — replace during traversal ────────────────────────────────
List<String> list = new ArrayList<>(
    List.of("hello", "world", "java", "iterator"));

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String current = it.next();
    it.set(current.toUpperCase());  // replace with uppercase version
}
System.out.println(list);  // [HELLO, WORLD, JAVA, ITERATOR]

// ── remove() — remove during traversal ───────────────────────────────
List<Integer> numbers = new ArrayList<>(
    List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

ListIterator<Integer> remover = numbers.listIterator();
while (remover.hasNext()) {
    int n = remover.next();
    if (n % 2 == 0) {
        remover.remove();  // remove even numbers
    }
}
System.out.println(numbers);  // [1, 3, 5, 7, 9]

// ── add() — insert during traversal ──────────────────────────────────
List<String> words = new ArrayList<>(
    List.of("Java", "is", "cool"));

ListIterator<String> adder = words.listIterator();
while (adder.hasNext()) {
    adder.next();
    adder.add("*");  // insert "*" after each word
}
System.out.println(words);  // [Java, *, is, *, cool, *]

// ── State machine: what is allowed when ─────────────────────────────
// State "fresh" (before first next/previous, or after add/remove):
//   next() — OK
//   previous() — OK
//   set() — IllegalStateException
//   remove() — IllegalStateException
//   add() — OK (inserts before cursor, state stays "fresh")
//
// State "element returned" (after next() or previous()):
//   next() — OK
//   previous() — OK
//   set() — OK (replaces last returned, state stays "element returned")
//   remove() — OK (removes last returned, state → "fresh")
//   add() — OK (inserts at cursor, state → "fresh")

// ── Demonstrating state transitions ──────────────────────────────────
List<String> demo = new ArrayList<>(List.of("A", "B", "C"));
ListIterator<String> state = demo.listIterator();

// state = "fresh":
// state.set("X");  // IllegalStateException

state.next();        // returns "A" — state = "element returned"
state.set("Alpha"); // replaces A — state still "element returned"
state.next();        // returns "B" — state = "element returned"
state.remove();      // removes B — state = "fresh"
// state.remove();   // IllegalStateException — must call next/previous first
// state.set("X");   // IllegalStateException — must call next/previous first

System.out.println(demo);  // [Alpha, C]

Practical Patterns — In-Place Transformation

ListIterator enables several practical patterns that are difficult or impossible with basic Iterator or index-based loops. In-place transformation replaces each element with a computed value without creating a new list. ListIterator.set() is the correct mechanism. The alternative — iterating by index and calling list.set(i, transform(list.get(i))) — works for RandomAccess lists (ArrayList) but is O(n) per element for LinkedList because list.get(i) requires traversal. ListIterator traversal is always O(1) per element regardless of the list implementation. In-place reversal of a sublist uses two ListIterators — one starting from the front and one starting from the back — swapping elements until they meet. This is O(n) time and O(1) space, in-place, and works on any List including LinkedList. Bidirectional scanning is needed for algorithms that process a list in both directions, like palindrome checking or windowed algorithms. A single ListIterator starting in the middle can scan outward in both directions using alternating next() and previous() calls. The most impactful practical use: processing a linked list with modification. ArrayList allows efficient index-based access, so a simple indexed for loop works well. But for LinkedList, index-based access is O(n) per element, making a simple loop O(n²). ListIterator on a LinkedList is always O(1) per element — it advances through the internal node references directly — making it essential for efficient LinkedList processing.

Java

// ── In-place transformation ───────────────────────────────────────────
public static void squareAll(List<Integer> numbers) {
    ListIterator<Integer> it = numbers.listIterator();
    while (it.hasNext()) {
        int n = it.next();
        it.set(n * n);   // replace with square — O(1) per element
    }
}

// Works efficiently for both ArrayList and LinkedList:
List<Integer> arrayList  = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3, 4, 5));

squareAll(arrayList);
squareAll(linkedList);
System.out.println(arrayList);   // [1, 4, 9, 16, 25]
System.out.println(linkedList);  // [1, 4, 9, 16, 25]

// ── Insert between every pair of elements ─────────────────────────────
public static <T> void intersperse(List<T> list, T separator) {
    ListIterator<T> it = list.listIterator();
    if (!it.hasNext()) return;
    it.next();   // advance past first element
    while (it.hasNext()) {
        it.add(separator);  // insert before current position
        it.next();           // advance past the original next element
    }
}

List<String> words = new ArrayList<>(List.of("a", "b", "c", "d"));
intersperse(words, "-");
System.out.println(words);   // [a, -, b, -, c, -, d]

// ── Reverse a sublist in-place ─────────────────────────────────────────
public static <T> void reverseSubList(List<T> list, int from, int to) {
    // ListIterator from both ends, swap until they meet
    ListIterator<T> fwd = list.listIterator(from);
    ListIterator<T> rev = list.listIterator(to);

    while (fwd.nextIndex() < rev.previousIndex()) {
        T front = fwd.next();
        T back  = rev.previous();
        fwd.set(back);
        rev.set(front);
    }
}

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7));
reverseSubList(nums, 2, 5);  // reverse indices [2, 5)
System.out.println(nums);     // [1, 2, 5, 4, 3, 6, 7]

// ── Efficient LinkedList processing — O(n) total ──────────────────────
// WRONG for LinkedList — O(n²) total:
List<String> bigLinked = new LinkedList<>(/* 10000 elements */);
for (int i = 0; i < bigLinked.size(); i++) {
    String s = bigLinked.get(i);    // O(n) traversal for each index
    bigLinked.set(i, s.trim());     // O(n) traversal again
}   // Total: O(n²) — catastrophically slow

// CORRECT for LinkedList — O(n) total:
ListIterator<String> efficient = bigLinked.listIterator();
while (efficient.hasNext()) {
    String s = efficient.next();    // O(1) — follows node.next reference
    efficient.set(s.trim());        // O(1) — modifies current node
}   // Total: O(n) — fast

ListIterator

ListIterator Methods — Bidirectional Traversal

Modification Methods — add, set, remove

Practical Patterns — In-Place Transformation

Related Topics in Collections Framework