Adding elements to a collection during iteration

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.

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.

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

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.

Use ListIterator as follows:

List<String> l = new ArrayList<>();
l.add("Foo");
ListIterator<String> iter = l.listIterator(l.size());
while(iter.hasPrevious()){
    String prev=iter.previous();
    if(true /*You condition here*/){
        iter.add("Bah");
        iter.add("Etc");
    }
}

The key is to iterate in reverse order - then the added elements appear on the next iteration.

I know its been quite old. But thought of its of any use to anyone else. Recently I came across this similar problem where I need a queue that is modifiable during iteration. I used listIterator to implement the same much in the same lines as of what Avi suggested -> Avi's Answer. See if this would suit for your need.

ModifyWhileIterateQueue.java

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ModifyWhileIterateQueue<T> {
        ListIterator<T> listIterator;
        int frontIndex;
        List<T> list;

        public ModifyWhileIterateQueue() {
                frontIndex = 0;
                list =  new ArrayList<T>();
                listIterator = list.listIterator();
        }

        public boolean hasUnservicedItems () {
                return frontIndex < list.size();  
        }

        public T deQueue() {
                if (frontIndex >= list.size()) {
                        return null;
                }
                return list.get(frontIndex++);
        }

        public void enQueue(T t) {
                listIterator.add(t); 
        }

        public List<T> getUnservicedItems() {
                return list.subList(frontIndex, list.size());
        }

        public List<T> getAllItems() {
                return list;
        }
}

ModifyWhileIterateQueueTest.java

    @Test
    public final void testModifyWhileIterate() {
            ModifyWhileIterateQueue<String> queue = new ModifyWhileIterateQueue<String>();
            queue.enQueue("one");
            queue.enQueue("two");
            queue.enQueue("three");

            for (int i=0; i< queue.getAllItems().size(); i++) {
                    if (i==1) {
                            queue.enQueue("four");
                    }
            }

            assertEquals(true, queue.hasUnservicedItems());
            assertEquals ("[one, two, three, four]", ""+ queue.getUnservicedItems());
            assertEquals ("[one, two, three, four]", ""+queue.getAllItems());
            assertEquals("one", queue.deQueue());

    }

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]

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.

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;
}

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.

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.