Deleting objects from an ArrayList in Java

Question

I need to delete some objects from an ArrayList if they meet a condition and I m wondering which way could be more efficient   Here s the situation  I have a class that contains an ArrayList containing some other objects  I have to iterate over this ArrayList and delete all elements meeting a certain condition   As far as I know  those would be my options to delete    Create a new ArrayList and add the elements that doesn t meet the condition  After the iteration  swap from the old arraylist to the new one without the elements  Create a new ArrayList and add the elements that meet the condition  After the iteration  use the removeAll   method passing the ArrayList with the objects to be deleted    Is there a more efficient way to delete objects from an ArrayList

User · Answer

You could iterate backwards and remove as you go through the ArrayList  This has the advantage of subsequent elements not needing to shift and is easier to program than moving forwards

User · Answer

First  I d make sure that this really is a performance bottleneck  otherwise I d go with the solution that is cleanest and most expressive   If it IS a performance bottleneck  just try the different strategies and see what s the quickest  My bet is on creating a new ArrayList and puting the desired objects in that one  discarding the old ArrayList

User · Answer

Whilst this is counter intuitive this is the way that i sped up this operation by a huge amount   Exactly what i was doing    ArrayList  lt  HashMap  lt  String   String  gt  gt  results     This has been filled with a whole bunch of results   ArrayList  lt  HashMap  lt  String   String     discard   findResultsToDiscard results    results removeall discard    However the remove all method was taking upwards of 6 seconds  NOT including the method to get the discard results  to remove approximately 800 results from an array of 2000  ish    I tried the iterator method suggested by gustafc and others on this post   This did speed up the operation slightly  down to about 4 seconds  however this was still not good enough  So i tried something risky      ArrayList  lt  HashMap  lt  String  String gt  gt  results     List  lt  Integer  gt  noIndex   getTheDiscardedIndexs results    for  int j   noIndex size  -1  j  gt   0  j--        results remove noIndex get j  intValue         whilst the getTheDiscardedIndexs save an array of index s rather then an array of HashMaps  This it turns out sped up removing objects much quicker   about 0 1 of a second now  and will be more memory efficient as we dont need to create a large array of results to remove   Hope this helps someone

User · Answer

There is a hidden cost in removing elements from an ArrayList   Each time you delete an element  you need to move the elements to fill the  hole   On average  this will take N   2 assignments for a list with N elements    So removing M elements from an N element ArrayList is O M   N  on average   An O N  solution involves creating a new list   For example   List data        List newData   new ArrayList data size       for  Iterator i   data iterator    i hasNext            Object element   i next         if                   newData add element             If N is large  my guess is that this approach will be faster than the remove approach for values of M as small as 3 or 4   But it is important to create newList large enough to hold all elements in list to  avoid copying the backing array when it is expanded

User · Answer

Most performant would  I guess  be using the listIterator method and do a reverse iteration   for  ListIterator lt E gt  iter   list listIterator list size     iter hasPrevious          if  weWantToDelete iter previous      iter remove        Edit  Much later  one might also want to add the Java 8 way of removing elements from a list  or any collection   using a lambda or method reference  An in-place filter for collections  if you like   list removeIf e - gt  e isBad    amp  amp  e shouldGoAway       This is probably the best way to clean up a collection  Since it uses internal iteration  the collection implementation could take shortcuts to make it as fast as possible  for ArrayLists  it could minimize the amount of copying needed

User · Answer

I have found an alternative faster solution     int j   0    for  Iterator i   list listIterator    i hasNext            j         if  campo getNome   equals key            i remove           i   list listIterator j

User · Answer

With an iterator you can handle always the element which comes to order  not a specified index  So  you should not be troubled with the above matter   Iterator itr   list iterator    String strElement       while itr hasNext        strElement    String itr next      if strElement equals  2            itr remove

User · Answer

Another way  The Iterator has an optional remove  -method  that is implemented for ArrayList  You can use it while iterating   I don t know though  which variant is the most performant  you should measure it   starblue commented  that the complexity isn t good  and that s true  for removeAll   too   because ArrayList has to copy all elements  if in the middle is an element added or removed  For that cases should a LinkedList work better  But  as we all don t know your real use-cases the best is too measure all variants  to pick the best solution

User · Answer

I m good with Mnementh s recommentation   Just one caveat though     ConcurrentModificationException   Mind that you don t have more than one thread running  This exception could appear if more than one thread executes  and the threads are not well synchronized

User · Answer

Maybe Iterator   s remove   method  The JDK   s default collection classes should all creator iterators that support this method

User · Answer

Obviously  of the two methods you mention number 1 is more efficient  since it only needs to go through the list once  while with method number 2 the list has to be traversed two times  first to find the elements to remove  and them to remove them    Actually  removing a list of elements from another list is likely an algorithm that s worse than O n  so method 2 is even worse   The iterator method   List data         for  Iterator i   data iterator    i hasNext            Object element   i next         if                    i remove

User · Answer

int sizepuede  listaoptionVO size    for  int i   0  i  lt  sizepuede  i          if listaoptionVO get i  getDescripcionRuc    null           listaoptionVO remove listaoptionVO get i            i--          sizepuede--             edit  added indentation

User · Answer

Unless you re positive that the issue you re facing is indeed a bottleneck  I would go for the readable  public ArrayList filterThings          ArrayList pileOfThings      ArrayList filteredPileOfThings   new ArrayList         for  Thing thingy   pileOfThings            if  thingy property    1                filteredPileOfThings add thingy                                   return filteredPileOfThings

[java] Deleting objects from an ArrayList in Java

Examples related to java

Examples related to performance

Examples related to memory-management

Examples related to arraylist