Deleting objects from an ArrayList in Java

Question

Hi guys,

I have a big doubt and I hope someone can help me out. 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:

1 - 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.

2 - 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?

Thanks in advance,
Carlos

Answer 1

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.

Answer 2

Maybe Iterator’s remove() method? The JDK’s default collection classes should all creator iterators that support this method.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

Most performant would, I guess, be using the listIterator method and do a reverse iteration:

for (ListIterator<E> iter = list.listIterator(list.size()); iter.hasPrevious();){
    if (weWantToDelete(iter.previous()))  iter.remove();
}

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

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