Is it safe to add items to a linked list while iterating

Question

Is it safe to add items to a LinkedList while iterating?

class Worker {

    final LinkedList<Foo> worklist = new LinkedList<>();

    public void work() {

        Iterator<Foo> iterator = worklist.iterator();

        while (iterator.hasNext()) {

            Foo foo = iterator.next();

            doSomethingWith(foo);
        }
    }

    public void doSomethingWith(Foo foo) {

        // do something with foo            

        // and possibly add one (or more) foo's to the worklist
        if (expression) {
            worklist.add(new Foo());
        }
    }
}

If not, how can this behaviour be implemented in a safe and efficient way?

Note that this is not about a List, but specifically about a LinkedList. If it isn't safe, I'm asking about alternatives.

Answer 1

No, it is not safe. The following code will throw a ConcurrentModificationException:

final LinkedList<Foo> worklist = new LinkedList<>();
worklist.add(new Foo());
Iterator<Foo> iterator = worklist.iterator();
while (iterator.hasNext()) {
    Foo foo = iterator.next();
    worklist.add(new Foo());
}

LinkedList does not override iterator() and the default implementation, defined in AbstractSequentialList is to call listIterator(), and LinkedList does override listIterator.

Quoting the documentation of LinkedList.listIterator:

The list-iterator is fail-fast: if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator's own remove or add methods, the list-iterator will throw a ConcurrentModificationException.

What you want is to use explicitely a ListIterator, instead of an Iterator, and use ListIterator.add:

final LinkedList<Foo> worklist = new LinkedList<>();
worklist.add(new Foo());
ListIterator<Foo> iterator = worklist.listIterator();
while (iterator.hasNext()) {
    Foo foo = iterator.next();
    iterator.add(new Foo());
}

The new element is inserted before the element that was returned by next() so subsequent calls to next() are unaffected. If you want to add the new item to the iteration, you can call previous() (and ignore the return value) after adding the element to move the cursor backwards.