55
\$\begingroup\$

I needed a way to remove elements on a List while iterating through it.

Supposedly something like this (illegal code):

List<Integer> nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
...
nums.add(10);

System.out.println("BEFORE REMOVE: " + nums);

for (Integer integer : nums) {
    if (integer < 3) {
        //not allowed
        nums.remove(integer);
    }
}

But we all know that the above code is not allowed.

So what I'm doing right now is that I create another List, where I'm putting every element that meets a given condition, then iterate through that List to get the elements that I need to remove on the first List.

List<Integer> toRemove = new ArrayList();
for (Integer integer : nums) {
    if (integer < 3) {
        toRemove.add(integer);
    }
}

for (Integer integer : toRemove) {
    nums.remove(integer);
}

System.out.println("AFTER REMOVE: " + nums);

I know it's not really long, but is there a better way to do this?

Is there some API that I can use?

\$\endgroup\$
  • \$\begingroup\$ I think you can use nums.removeAll(toRemove) \$\endgroup\$ – Ishan Fernando Feb 5 '18 at 6:17
71
\$\begingroup\$

There are several ways to do this. Let's look at the alternatives:

Iterating over a copy, removing from original

This is a simple solution for the underlying problem of your first code: A ConcurrentModificationException is thrown because you iterate through the list and removing from it at the same time.

Easy solution is to create a copy of the list and iterate through that.

for (Integer integer : new ArrayList<>(nums)) {
    if (integer < 3) {
        nums.remove(integer);
    }
}

Down-sides of this approach:

  • Creates a copy of the original list, which requires memory and an operation which performance depends on the type of the list (ArrayList, LinkedList, etc.)
  • Additionally, nums.remove(value) is a \$O(n)\$ operation. Making this loop overall \$O(n^2)\$

Java 8 Streams

List<Integer> filteredList = nums.stream().filter(i -> i >= 3).collect(Collectors.toList());

Down-sides:

  • Does not actually modify the existing list, so if references to the list are spread around various variables, you still have some old elements that just shouldn't be in that list.
  • Creates various stream-related objects which might not be the most effective option.

On the up-side, this is among the fastest for bigger lists.

If you're not using Java 8:

List<Object> originalList;
List<Object> newList = new YourFavoriteListType<>();
for (Object obj : originalList) {
    if (shouldKeep(obj)) {
        newList.add(obj);
    }
}

Java 8 method

nums.removeIf(i -> i < 3);

Java 8 introduced the default method removeIf on the Collection interface. This allows different implementations to have implementation-specific performance-optimized implementations of this method.

Iterator.remove()

Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    Integer integer = it.next();
    if (integer < 3) {
        it.remove();
    }
}

The only down-side of this approach is that you need to switch your for-each to a while. However, this approach is the most efficient one, especially for LinkedList where it is \$O(n)\$ (it's \$O(n^2)\$ for ArrayList because it has to copy array data on each remove(index) call). This is the approach I would recommend in most cases.

Note: Instead of using a while-loop it can also be written as:

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    Integer integer = it.next();
    ...

Conclusion

If you want to mutate the existing list, removeIf is the solution I would go with. If you like functional programming and prefer a new list instead of mutating the existing one, then go with the list.stream().filter(...).collect(Collectors.toList()) approach.

See also

"When to use LinkedList over ArrayList?" on Stack Overflow

\$\endgroup\$
  • \$\begingroup\$ It's O(n) for a LinkedList, but O(n**2) for an ArrayList. There's nothing the iterator could do to avoid the moving of data. \$\endgroup\$ – maaartinus Sep 27 '14 at 15:45
  • \$\begingroup\$ @maaartinus True, but it does depend a little bit on how System.arraycopy is implemented, as it is a native call. I tend to think of it as a pure memory-copy call which I more think of as O(1) instead of O(n), but looking at a SO answer it seems like it is likely to be O(n). \$\endgroup\$ – Simon Forsberg Sep 27 '14 at 15:52
  • 2
    \$\begingroup\$ It used to be a native call when Java was terribly slow. It's no magic bullet, anymore. Now, it's a JVM intrinsic, which means that the JITc replaces the code by something smart and fast (using XMM registers). But it still remains O(n). I could imagine fooling around with virtual memory mappings, which would be even much faster, but still O(n). Anyway, it would apply to shift amounts being multiples of the page size, so let's forget it. \$\endgroup\$ – maaartinus Sep 27 '14 at 15:59
  • 1
    \$\begingroup\$ @maaartinus To keep O(n) for an ArrayList simply loop and collect all elements to be removed in a separate collection, then call removeAll() on the ArrayList. \$\endgroup\$ – bowmore Sep 28 '14 at 8:16
  • \$\begingroup\$ @bowmore Right, but the separate must have O(1) access for this. So you need something like a HashMap , which in turn has a rather high overhead (not really high, but high when compared to a list). I'd bet that collecting the wanted elements a second list is at least 3x faster. \$\endgroup\$ – maaartinus Sep 29 '14 at 18:26
21
\$\begingroup\$

Just had to do something very similar (hence why I'm here), ended up using Java8's Collection.removeIf(Predicate<? super E> filter)

With your code it would look like:

nums.removeIf((Integer i)->{return i<3;});

And if you wanted to collect the removes:

List<Integer> removed = new ArrayList<>();
nums.removeIf(
    (Integer i)->{
        boolean remove = i<3;
        if (remove) {
            removed.add(i);
        }
        return remove;
    });
\$\endgroup\$
  • 3
    \$\begingroup\$ I like this way for Java 8 as it is much more concise while still clear enough. However, internally (looking at the JDK code) it seems to still use an iterator and call iterator.remove(). So performance considerations listed in other posts still hold. \$\endgroup\$ – kg_sYy Oct 24 '15 at 14:17
6
\$\begingroup\$

Out of the other presented solutions, all but the one using Java 8 seem to be O(n**2), i.e., too slow when the list(*) gets a bit bigger.

The simplest fast solution is to create an empty list and add all elements not less than three.

If you need to modify the original list, then clean if afterwards and add all elements from the auxiliary list.


(*) Unless it's a LinkedList, which excels here. But its performance in all other scenarios is so terrible that it should be practically never used.

\$\endgroup\$
4
\$\begingroup\$

Another perhaps interesting option is using a CopyOnWriteArrayList:

@Test
public void testCanRemoveFromCopyOnWriteArrayList() {
    List<Integer> nums = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    for (Integer num : nums) {
        if (num < 3) {
            nums.remove(num);
        }
    }
    assertEquals(Arrays.asList(3, 4, 5), nums);
}

The downside is obvious, from the name of the class: it copies the underlying list before every write operation. This class is designed for observer lists, which are rarely modified and often traversed. I'm not sure if this applies to your case (if deleting from the list will be frequent or not), but I thought I'd mention this just in case.

\$\endgroup\$
4
\$\begingroup\$

Adding to @Simon's answer, you could use a reversed for loop to go through your array to remove items you don't want. It remains an O(n^2) operation because of the remove method. So this approach isn't any better, but it's a different way to do it.

for(int index = array.size() - 1; index >= 0; index--) {
    if(array.get(index) < 3){
        array.remove(index);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It is a bit faster as it moves no elements to be removed later. But agreed, it's still O(n**2). \$\endgroup\$ – maaartinus Sep 27 '14 at 16:34
  • \$\begingroup\$ array.get is a slow operation on a LinkedList, it would be better to use array.listIterator() which is capable of going backwards. \$\endgroup\$ – Simon Forsberg Sep 27 '14 at 17:33
  • \$\begingroup\$ Iterating using an old-fashioned for-loop does solve the ConcurrentModificationException though. (even if it would be a forward one you could just decrease the index every time an item has been removed) \$\endgroup\$ – Simon Forsberg Sep 27 '14 at 17:34
  • \$\begingroup\$ Well, the OP has an Arraylist<>, so I went with the ArrayList! And I find it clearer to use a reversed loop instead of messing with the index inside the loop \$\endgroup\$ – IEatBagels Sep 27 '14 at 18:56
  • \$\begingroup\$ Because the ArrayList.get is an O(1) operation \$\endgroup\$ – IEatBagels Sep 27 '14 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.