Java LinkedList ListIterator: edit at a cursor without repeated searches

This complete program targets Java 8. Its displayed output is checked by the tutorial validation script.

Use the cursor as the edit location

A review queue contains Read, Code and Ship. The cursor moves over Read, inserts Test after it, then moves over Code and removes it. Insertion uses the cursor gap; removal uses the last element returned by traversal. The resulting queue is Read, Test, Ship.

After add, remove cannot be called until next or previous establishes a new last-returned element. The second part of the fixture checks that state rule explicitly. A cursor is more than an integer index: its allowed operations depend on the last traversal and edit.

Do not pay for a new search on every step

A loop that repeatedly calls get(index) on a linked list revisits nodes and can take quadratic total time. Once positioned, the iterator can traverse and edit without starting a new search for every element. Obtaining listIterator(index) can still require locating that position.

The fixture has one thread and edits through the iterator itself. External structural mutation invalidates its assumptions; best-effort fail-fast detection cannot protect a shared queue. For concurrent production work, choose the appropriate queue contract and define ownership rather than relying on an exception.

Working program

import java.util.*;
public class ReviewQueueCursor {
    public static void main(String[] args) {
        LinkedList<String> queue = new LinkedList<>(Arrays.asList("Read", "Code", "Ship"));
        ListIterator<String> cursor = queue.listIterator();
        cursor.next(); cursor.add("Test"); cursor.next(); cursor.remove();
        System.out.println(queue);
        cursor.add("Audit");
        try { cursor.remove(); }
        catch (IllegalStateException rejected) { System.out.println("cursor state rejected"); }
    }
}

Output

[Read, Test, Ship]
cursor state rejected

Costs and boundaries

Walking n elements through one cursor takes O(n) time. Positioning at an arbitrary index can take O(n), while cursor-local node edits have constant structural work. Each stored element requires a linked node; this is not evidence that LinkedList beats an array-backed queue for the workload.

Common Mistakes

• Do not call remove immediately after add without a traversal step.
• Avoid indexed loops over a linked list.
• Do not treat fail-fast detection as synchronization.

Read next

Java LinkedList: operations, internals and failure cases, Java Iterator and ListIterator: traversal and controlled edits, Java ArrayDeque for queues and stacks.

Continue with the new boundary checks

Continue with Java LinkedList descendingIterator: inspect and remove from the tail, Java LinkedList fail-fast iterators: a bug signal, not safety.