Java - Add elements to an ArrayList while browsing it

Question

The problem is that I have this method createNode() that creates a node in a tree, and then if it's a leave node it adds it into an ArrayList<Tree> treeLeaves, and I make the call of this method while browsing the treeLeaves ArrayList like this :

    Iterator<Tree> iter = treeLeaves.iterator();
    while (iter.hasNext()) {
        iter.next().createNode();
    }

Or like this :

    For (Tree cursor : treeLeaves) {
        cursor.createNode();
    }

But I keep having this exception :

    Exception in thread "main" java.util.ConcurrentModificationException

Even when put the codes below in snychronized(treeLeaves){} bloc. P.S: I don't know if this is usefull or not but; it's an n-Tree.

I believe there are some other key info you are not showing: Based on what you showed us, you are not changing the the list (`treeLeaves`) when iterating it. The above code shouldn't cause `ConcurrentModificationException` (at least not from `treeLeaves`) — Adrian Shum, Dec 30 '15 at 02:01
@AdrianShum I said below that the `.createNode()` method adds a node, and if it's a leave node it adds it into `treeLeaves`. Is it still not comprehensive ? — Khalil Hamani, Dec 30 '15 at 02:06
oops, I see what you mean there then. Coz it does not look that normal so I missed your point there. — Adrian Shum, Dec 30 '15 at 02:09

score 5 · Answer 1 · edited May 23 '17 at 12:17

5

You need A ConcurrentList...

http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/CopyOnWriteArrayList.html

read Is there a concurrent List in Java's JDK?

Also you can't change a arraylist when browsing it... Instead you can use a buffer in tempoaray memory to edit current list if you like.

edited May 23 '17 at 12:17

Community

1
1

answered Dec 30 '15 at 01:49

Ya Wang

1,758
1
19
41

synchronized list won't help. `ConcurrentModificationException` means more than multi-thread acccess to a collection. – Adrian Shum Dec 30 '15 at 01:57
Okey thank you verry much @Ya Wang, I am going to try it and I'll be intouch – Khalil Hamani Dec 30 '15 at 02:42
Indeed this is great I don't have the Exception anymore. Thank you. – Khalil Hamani Dec 30 '15 at 03:33
what's happening is actually nothing different from my solution :P COW actually means it is having a new copy of list when you add to it (while you still iterating the original copy). – Adrian Shum Dec 30 '15 at 03:35

score 2 · Accepted Answer · answered Dec 30 '15 at 02:24

For an ArrayList, you could avoid the iterator by just using an index:

for (int i = 0; i < treeLeaves.size(); i++) {
    Tree current = treeLeaves.get(i);
    // your code
}

As long as the only thing you do is append to the end of the array, and you don't insert in the middle or at the beginning or delete any items, this will work. treeLeaves.size() will be recomputed every time you go through the loop, which means that if you append to the end, the size will be recomputed and i will get to the new items. Yes, using an old-fashioned loop isn't as "cool" as an iterator, but it works.

I don't recommend using this for any kind of List other than an ArrayList, because in general, get(i) will have to start from the beginning of the list and step through each element (unless the runtime optimizes the case where you're using get(i+1) after get(i), which wouldn't be too hard, but I don't know whether the implementations do that). For an ArrayList, however, get(i) should take constant time.

Yeah thank you @ajb, in fact it's a mind-trick, once you learn the iterator way. It does'nt make you want to use the "old-fashioned" loop anymore. Anyway, this is helping, so thank you again. — Khalil Hamani, Dec 30 '15 at 02:41

score 1 · Answer 3 · answered Dec 30 '15 at 02:06

This is because in Java, when an Iterator is created, you cannot modify the underlying data structure. The enhanced for loop "for (Tree cursor : treeLeaves))" uses an Iterator.

As Ya stated, "Also you can't change a arraylist when browsing it... Instead you can use a buffer in tempoaray memory to edit current list if you like."

score 0 · Answer 4 · answered Dec 30 '15 at 02:13

In brief, in most cases, if you change the structure of a collection, all still-open iterators will become invalid. (Quite some exception including using Concurrent collections, or modification is done through the iterator, or etc.)

Your problem can be demonstrated easily by:

List<Node> treeLeaves = new ArrayList<>();

//... add something to treeLeaves

for (leaf :  treeLeaves) {
    treeLeaves.add(new Node());
}

For your case, it can be easily solved by creating a new collection to iterate:

List<Node> treeLeaves = new ArrayList<>();
//... add something to treeLeaves

List<Node> tempLeaves = new ArrayList<>(treeLeaves);    
for (leaf :  tempLeaves ) {
    treeLeaves.add(new Node());
}

The problem is I have to go as far as the `treeLeaves` ArrayList expands. Using a temporary list doesn't work, as no update is done while browsing. — Khalil Hamani, Dec 30 '15 at 02:18

Java - Add elements to an ArrayList while browsing it

4 Answers4