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.

http://stackoverflow.com/questions/3362018/is-linkedlist-thread-safe-when-im-accessing-it-with-offer-and-poll-exclusively Being able to change values within a list while iterating is also a property associated with multithreading. General rule if a list can use a iterator it isn't thread safe — Ya Wang, Oct 06 '15 at 12:50
If you change the list while iterating over it, it will throw ConcurrentModificationException. — YoungHobbit, Oct 06 '15 at 12:56
Why not to use ListIterator and add element with help of iterator? We can access it with worklist.listIterator() — Ivan Bochko, Oct 06 '15 at 12:56
Possible duplicate of [Java: adding elements to a collection during iteration](http://stackoverflow.com/questions/993025/java-adding-elements-to-a-collection-during-iteration) — pelumi, Oct 06 '15 at 13:26

Tunaki · Accepted Answer · 2015-10-06T13:16:42.843

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.

But I have to iterate over the added element too. I've edited the code example in the question. — Tim, Oct 06 '15 at 13:04
@Tim see my edit, you can call `previous()` to add the element to the current iteration. — Tunaki, Oct 06 '15 at 13:17

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

1 Answers1