Remove items from list or add build a new list? [closed]

Question

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

From performance point of view: is it better to use iterator and iterator.remove() for the elements I want to remove, or should I add these elements 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 ArrayList is a significant cost when the list is long as much of the backing array must be copied.

Option 2 will work for all lists.

It is also the pattern we are encouraged to use with streams:

    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 best

Space complexity: Option 1 is best

ArrayList remove is O(n) while add is O(1), however, you will have to allocate new memory for the new list.