ConcurrentModificationException with ArrayList

[fogus]

Hello,

I am building a binarytree ADT for storing a dictionary. My underlying data structure is an arraylist, which is a global in my binarytree class.

My algorithm to build the tree works something like this:

Take an ArrayList
   take the middle element and set it as the root of the tree
   split the tree at that middle element and set the left and right pointer of the root to the left and right subtrees.
   recursively call this method, adding the middle elements to the global ArrayList

The problem is that I always get the ConcurrentModificationException ( I tried to post the URL here ).

My question is, how can I modify a node's (constructed in my "node" class) pointers without getting this problem?

(I could swear this whole project would have taken me 1 hour tops in python. I just spend all my time with these errors.)

Thanks!

[Nicholas Jordan]

If another thread makes structural modifications to a Collection, in general we get a concurrent modification exception. There has to be a barrier that will ....

uh, it sorta gets complicated but the short version is that we would make a complete new Tree and set the pointers to the new Tree. Which operation would have to block all access to the tree during update. Individual record locking does not lend to the Collections design.

That devolves into some convoluted design consequences, a robust / time-critical design can be achieved with (synchronized) code construct - but that is going to be difficult to do with large collections as a complete array copy operation has to intervene between T(n) and T(n+1) access of either read or write as reads can be done but will throw on a write the structurally modifies the tree structure.

[fogus]

I seriously cannot build a new tree for every iteration. We are talking about a 600kb, 80,000 line dictionary here.

How would you write bubble sort in java if the list you were sorting was global?

[Nicholas Jordan]

I would use a TreeMap, I have code for a WordCount, which I will share with you if you want. I could stand to look at it now - my skills are greater than when I wrote it and it is a super-critical part of my original project. That has not gotten any attention in very long time..

Shortened version is just do TreeMap dot add( new Integer( String.hashcode(), new String( the original string ) )

btw thanks to EFH at JR for me getting that running.

I only tested it once, if you will do some testing - I will share it with you.