Remove items from list or add new list?

Question

Often I have come to the point where I need to iterate ArrayList and want to create a subset of it based on any condition.

In terms of performance: is it better to use an iterator and iterator.remove() for the items I want to remove, or add these items to a new list?

 for (Iterator<Object> it = list.iterator(); it.hasNext(); ) { Object item = it.next(); if (!conditionMatches(item)) { it.remove(); } } 

or

 List<Object> newList = new ArrayList<>(); for (Object item : list) { it (contitionMatches(item)) { newList.add(item); } } 

Answer 1

Option 1 will not work for read-only lists, such as those returned by Arrays.asList .

Also, remove from an ArrayList is a significant cost when the list is long, since most of the support array needs to be copied.

Option 2 will work for all lists.

This is also a template that we recommend using with threads:

  List<String> l = Arrays.asList("A","B","C"); List<String> filtered = l.stream() .filter(s -> s.equals("A")) .collect(Collectors.toList()); 

IMHO - use this one. The savings in option 1 are illusory.

Answer 2

Time complexity: option 2 is better

Cosmic complexity: option 1 is best

Removing ArrayList is O (n) and add is O (1), however you will need to allocate new memory for the new list.

Answer 3

If you need to remove only one item, you can do it anyway. If you want to delete all elements at a certain point, you can do it anyway (iterate back to delete). In general, however, the copying approach is likely to take much less time. If you prefer to modify the list in place, you can consider removeIf . Although the documentation does not indicate how it works, it most likely tracks the "to" and "from" index, shifting all elements in a single pass. Most likely, whether the approach to copying or modifying is appropriate will depend on how you use this list, and (if my assumption about removeIf is correct) may also depend on how much of the elements are removed.

Answer 4

if you want to remove the values ​​from the list, you need to do this from the end to the beginning, for example:

 for (int i=list.size()-1; i>=0; i--) { if (contitionMatches(list.get(i))) { list.remove(i); } } 

Answer 5

The second option is faster because it does not include the transfer of all subsequent elements when deleting an element at the current position.

When it comes to the larger ArrayList s, I dare even say that the first option is an anti-pattern.