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

User · Answer

This is what I usually do  with collections like sets   Set lt T gt  adds   new HashSet lt T gt   dels   new HashSet lt T gt   for   T e  target     if    lt has to be removed gt    dels add   e      else if    lt has to be added gt    adds add    lt new element gt     target removeAll   dels    target addAll   adds      This creates some extra-memory  the pointers for intermediate sets  but no duplicated elements happen  and extra-steps  iterating again over changes   however usually that s not a big deal and it might be better than working with an initial collection copy

User · Answer

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 lt Thing gt  expand List lt Thing gt  inputs        List lt Thing gt  expanded   new ArrayList lt Thing gt          for  Thing thing   inputs            expanded add thing           if  needsSomeMoreThings thing                 addMoreThingsTo expanded                        return expanded

User · Answer

For examle we have two lists     public static void main String   args            ArrayList a   new ArrayList Arrays asList new String    a1    a2    a3   a4    a5              ArrayList b   new ArrayList Arrays asList new String    b1    b2    b3   b4    b5              merge a  b           a stream   map  x - gt  x        forEach System out  print            public static void merge List a  List b           for  Iterator itb   b iterator    itb hasNext                   for  ListIterator it   a listIterator     it hasNext                        it next                    it add itb next                                       a1 b1 a2 b2 a3 b3 a4 b4 a5 b5

User · Answer

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 lt T gt            ListIterator lt T gt  listIterator          int frontIndex          List lt T gt  list           public ModifyWhileIterateQueue                     frontIndex   0                  list    new ArrayList lt T gt                     listIterator   list listIterator                       public boolean hasUnservicedItems                      return frontIndex  lt  list size                         public T deQueue                     if  frontIndex  gt   list size                              return null                                    return list get frontIndex                        public void enQueue T t                    listIterator add t                       public List lt T gt  getUnservicedItems                     return list subList frontIndex  list size                        public List lt T gt  getAllItems                     return list                ModifyWhileIterateQueueTest java       Test     public final void testModifyWhileIterate                 ModifyWhileIterateQueue lt String gt  queue   new ModifyWhileIterateQueue lt String gt                 queue enQueue  one                queue enQueue  two                queue enQueue  three                 for  int i 0  i lt  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

User · Answer

Given a list List lt Object gt  which you want to iterate over  the easy-peasy way is   while   list isEmpty        Object obj   list get 0          do whatever you need to       possibly list add new Object obj1       list remove 0       So  you iterate through a list  always taking the first element and then removing it  This way you can append new elements to the list while iterating

User · Answer

Using iterators   no  I don t think so  You ll have to hack together something like this       Collection lt  String  gt  collection   new ArrayList lt  String  gt   Arrays asList   foo    bar    baz           int i   0      while   i  lt  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

User · Answer

Use ListIterator as follows   List lt String gt  l   new ArrayList lt  gt     l add  Foo    ListIterator lt String gt  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

User · Answer

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

User · Answer

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

User · Answer

I tired ListIterator but it didn t help my case  where you have to use the list while adding to it  Here s what works for me   Use LinkedList   LinkedList lt String gt  l   new LinkedList lt String gt     l addLast  A     while  l isEmpty         String str   l removeFirst        if    Condition for adding new element            l addLast   lt New Element gt         else         System out println str       This could give an exception or run into infinite loops  However  as you have mentioned      I m pretty sure it won t in my case   checking corner cases in such code is your responsibility

User · Answer

Even though we cannot add items to the same list during iteration  we can use Java 8 s flatMap  to add new elements to a stream  This can be done on a condition  After this the added item can be processed   Here is a Java example which shows how to add to the ongoing stream an object depending on a condition which is then processed with a condition   List lt Integer gt  intList   new ArrayList lt  gt     intList add 1   intList add 2   intList add 3    intList   intList stream   flatMap i - gt        if  i    2  return Stream of i  i   10      condition for adding the extra items     return Stream of i      map i - gt  i   1           collect Collectors toList      System out println intList     The output of the toy example is       2  3  21  4

User · Answer

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

User · Answer

public static void main String   args           This array list simulates source of your candidates for processing     ArrayList lt String gt  source   new ArrayList lt String gt            This is the list where you actually keep all unprocessed candidates     LinkedList lt String gt  list   new LinkedList lt String gt             Here we add few elements into our simulated source of candidates        just to have something to work with     source add  first element        source add  second element        source add  third element        source add  fourth element        source add  The Fifth Element       aka Milla Jovovich         Add first candidate for processing into our main list     list addLast source get 0            This is just here so we don t have to have helper index variable        to go through source elements     source remove 0           We will do this until there are no more candidates for processing     while  list isEmpty                     This is how we get next element for processing from our list            of candidates  Here our candidate is String  in your case it            will be whatever you work with          String element   list pollFirst               This is where we process the element  just print it out in this case         System out println element               This is simulation of process of adding new candidates for processing            into our list during this iteration          if source size    gt  0     When simulated source of candidates dries out  we stop                          Here you will somehow get your new candidate for processing                In this case we just get it from our simulation source of candidates              String newCandidate   source get 0                  This is the way to add new elements to your list of candidates for processing             list addLast newCandidate                  In this example we add one candidate per while loop iteration and                 zero candidates when source list dries out  In real life you may happen                to add more than one candidate here                 list addLast newCandidate2                  list addLast newCandidate3                  etc                  This is here so we don t have to use helper index variable for iteration                through source              source remove 0

User · Answer

Forget about iterators  they don t work for adding  only for removing  My answer applies to lists only  so don t punish me for not solving the problem for collections  Stick to the basics       List lt ZeObj gt  myList   new ArrayList lt ZeObj gt            populate the list with whatever                          int noItems   myList size        for  int i   0  i  lt  noItems  i              ZeObj currItem   myList get i              when you want to add  simply add the new item at last and            increment the stop condition         if  currItem asksForMore                  myList add new ZeObj                 noItems

User · Answer

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

User · Answer

Actually it is rather easy  Just think for the optimal way  I beleive the optimal way is   for  int i 0  i lt 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

User · Answer

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

User · Answer

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 lt String gt  list   Arrays asList new String    Hello    World      Collection lt String gt  additionalList   new ArrayList lt String gt      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 lt Integer gt  queue   new LinkedList lt Integer gt     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

[java] Adding elements to a collection during iteration

Examples related to java

Examples related to iterator