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

There are two issues here:

The first issue is, adding to an Collection after an Iterator is returned. As mentioned, there is no defined behavior when the underlying Collection is modified, as noted in the documentation for Iterator.remove:

... The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

The second issue is, even if an Iterator could be obtained, and then return to the same element the Iterator was at, there is no guarantee about the order of the iteratation, as noted in the Collection.iterator method documentation:

... There are no guarantees concerning the order in which the elements are returned (unless this collection is an instance of some class that provides a guarantee).

For example, let's say we have the list [1, 2, 3, 4].

Let's say 5 was added when the Iterator was at 3, and somehow, we get an Iterator that can resume the iteration from 4. However, there is no guarentee that 5 will come after 4. The iteration order may be [5, 1, 2, 3, 4] -- then the iterator will still miss the element 5.

As there is no guarantee to the behavior, one cannot assume that things will happen in a certain way.

One alternative could be to have a separate Collection to which the newly created elements can be added to, and then iterating over those elements:

Collection<String> list = Arrays.asList(new String[]{"Hello", "World!"}); Collection<String> additionalList = new ArrayList<String>();  for (String s : list) {     // Found a need to add a new element to iterate over,     // so add it to another list that will be iterated later:     additionalList.add(s); }  for (String s : additionalList) {     // Iterate over the elements that needs to be iterated over:     System.out.println(s); } 

Edit

Elaborating on Avi's answer, it is possible to queue up the elements that we want to iterate over into a queue, and remove the elements while the queue has elements. This will allow the "iteration" over the new elements in addition to the original elements.

Let's look at how it would work.

Conceptually, if we have the following elements in the queue:

[1, 2, 3, 4]

And, when we remove 1, we decide to add 42, the queue will be as the following:

[2, 3, 4, 42]

As the queue is a FIFO (first-in, first-out) data structure, this ordering is typical. (As noted in the documentation for the Queue interface, this is not a necessity of a Queue. Take the case of PriorityQueue which orders the elements by their natural ordering, so that's not FIFO.)

The following is an example using a LinkedList (which is a Queue) in order to go through all the elements along with additional elements added during the dequeing. Similar to the example above, the element 42 is added when the element 2 is removed:

Queue<Integer> queue = new LinkedList<Integer>(); queue.add(1); queue.add(2); queue.add(3); queue.add(4);  while (!queue.isEmpty()) {     Integer i = queue.remove();     if (i == 2)         queue.add(42);      System.out.println(i); } 

The result is the following:

1 2 3 4 42 

As hoped, the element 42 which was added when we hit 2 appeared.