Java: adding elements to a collection during iteration

Question

Is it possible to add elements to a collection while iterating over it?

More specifically, I would like to iterate over a collection, and if an element satisfies a certain condition I want to add some other elements to the collection, and make sure that these added elements are iterated over as well. (I realise that this could lead to an unterminating loop, but I'm pretty sure it won't in my case.)

The Java Tutorial from Sun suggests this is not possible: "Note that Iterator.remove is the only safe way to modify a collection during iteration; the behavior is unspecified if the underlying collection is modified in any other way while the iteration is in progress."

So if I can't do what I want to do using iterators, what do you suggest I do?

Answer 1

How about building a Queue with the elements you want to iterate over; when you want to add elements, enqueue them at the end of the queue, and keep removing elements until the queue is empty. This is how a breadth-first search usually works.

Answer 2

In general, it's not safe, though for some collections it may be. The obvious alternative is to use some kind of for loop. But you didn't say what collection you're using, so that may or may not be possible.

Answer 3

You may also want to look at some of the more specialised types, like ListIterator, NavigableSet and (if you're interested in maps) NavigableMap.

Answer 4

Using iterators...no, I don't think so. You'll have to hack together something like this:

 Collection< String > collection = new ArrayList< String >( Arrays.asList( "foo", "bar", "baz" ) );
 int i = 0;
 while ( i < collection.size() ) {

  String curItem = collection.toArray( new String[ collection.size() ] )[ i ];
  if ( curItem.equals( "foo" ) ) {
   collection.add( "added-item-1" );
  }
  if ( curItem.equals( "added-item-1" ) ) {
   collection.add( "added-item-2" );
  }

  i++;
 }

 System.out.println( collection );

Which yeilds:
[foo, bar, baz, added-item-1, added-item-2]

Answer 5

I prefer to process collections functionally rather than mutate them in place. That avoids this kind of problem altogether, as well as aliasing issues and other tricky sources of bugs.

So, I would implement it like:

List<Thing> expand(List<Thing> inputs) {
    List<Thing> expanded = new ArrayList<Thing>();

    for (Thing thing : inputs) {
        expanded.add(thing);
        if (needsSomeMoreThings(thing)) {
            addMoreThingsTo(expanded);
        }
    }

    return expanded;
}

Answer 6

IMHO the safer way would be to create a new collection, to iterate over your given collection, adding each element in the new collection, and adding extra elements as needed in the new collection as well, finally returning the new collection.

Answer 7

Besides the solution of using an additional list and calling addAll to insert the new items after the iteration (as e.g. the solution by user Nat), you can also use concurrent collections like the CopyOnWriteArrayList.

The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.

With this special collection (usually used for concurrent access) it is possible to manipulate the underlying list while iterating over it. However, the iterator will not reflect the changes.

Is this better than the other solution? Probably not, I don't know the overhead introduced by the Copy-On-Write approach.

Answer 8

Actually it is rather easy. Just think for the optimal way. I beleive the optimal way is:

for (int i=0; i<list.size(); i++) {
   Level obj = list.get(i);

   //Here execute yr code that may add / or may not add new element(s)
   //...

   i=list.indexOf(obj);
}

The following example works perfectly in the most logical case - when you dont need to iterate the added new elements before the iteration element. About the added elements after the iteration element - there you might want not to iterate them either. In this case you should simply add/or extend yr object with a flag that will mark them not to iterate them.