Java LinkedList ListIterator: the add, set and remove state machine

Last updated: 30 Sept 20264 min read

tutorial

A LinkedList list iterator can edit around its cursor, but set and remove require a preceding next or previous call.

The cursor sits between nodes

Start between the first and second receipt. add inserts a new receipt before the next node. It leaves the cursor after the inserted node; it does not make that insertion the most recently returned element. Calling set immediately after add therefore fails with IllegalStateException.

After next returns the original second node, set can replace it. remove can then delete that returned node. The result keeps the inserted receipt. This is safer than editing the list directly while the cursor is active. Fail-fast behavior is only a bug signal for competing edits.

Choose cursor work for sequential edits

A listIterator(index) starts at a position, and locating a middle position may traverse links. Once positioned, walking and editing adjacent nodes avoids repeated indexed scans. See indexed traversal cost before writing a loop that calls get(i) on every pass.

Working program

import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;
public class ReceiptCursorEdit {
    public static void main(String[] args) {
        LinkedList<String> receipts = new LinkedList<>(Arrays.asList("R-10", "R-30"));
        ListIterator<String> cursor = receipts.listIterator(1);
        cursor.add("R-20");
        try { cursor.set("invalid"); }
        catch (IllegalStateException rejected) { System.out.println("set requires a returned node"); }
        System.out.println("next=" + cursor.next());
        cursor.set("R-30-reviewed");
        cursor.remove();
        System.out.println(receipts);
    }
}

Output

set requires a returned node
next=R-30
[R-10, R-20]

Costs and boundaries

Initial positioning may take O(n); a full cursor walk takes O(n) time and O(1) cursor state. The fixture checks Java 8 behavior and one invalid transition. It does not make concurrent edits safe.

Common Mistakes

Do not call set or remove immediately after add.
Do not edit the backing list through another path while the cursor is active.
Do not turn sequential edits into repeated get(index) calls.