Remove the element of ArrayList and List in for-loop indexes?

[Tan Quang]

First of all, this topic will certainly relate to safety and performance.

Suppose I have an ArrayList that contains 1 million elements (or larger) and is only allowed to use for loop index.
In the process of browsing the elements, suppose I need to remove some elements at some positions.

ArrayList<Integer> oneMillionArrays = oneMillionElms;
int size = oneMillionArrays.size();
log.debug("Size of arraylist is: " + size);
for(int index = 0; index < size; ++index) {
	int elms = oneMillionArrays.get(index);
	if(elms == ... || ...) { // certain conditions
		oneMillionArrays.remove(i); // Remove the element then select 1 of 2 ways below
		/*
		--size; // reduce size or IndexOutOfBoundsException
		--index // If you don't want to reduce the size, you can do this.
		*/
	}
}

And the first question is: If I have to choose 1 in 2, I should choose to reduce size or reduce index?

In addition, I can change the way to browse the element into a descending index (from size to 0) but a long time ago, I've read an article, they have said that is: With ArrayList, you should browse by index Ascending (from 0 to size), and the List is reverse (from size to 0). (Please don't ask me that document information, I read it for a long time ago and I often can't remember where I read it?   )
But I don't pay attention to the effect of such browsing because ArrayList I always browse in a way to increase the index, and with List then I often use Iterator or foreach loop.
And today, I have read the answer about the benefits when traverse the List backwards (from size to 0).
As the answer on StackOverflow:

Benefits:
It only iterates over the list once
No extra objects created, or other unneeded complexity
No problems with trying to use the index of a removed item, because... well, think about it!

But that is explaining to the List, and it seems that many people agree with that answer. Is that true?

The last question is: So why I shouldn't browse backwards index in ArrayList?

I'll try to make this topic shortest possible by don't go around like the previous topic.  

[Carey Brown]

Is it supposed to remove multiple elems during one complete run of the loop, or only remove one element?

[Piet Souris]

Question 1: both

For instance, if you remove the element at index 0, then the next element to inspect is also at index 0, not index1.

I would simply use a Stream and a filter, much easier (has an implicit loop)

And nothing wrong with going backwards, easier than going forward.

[Carey Brown]

List<Integer> oneMillionArrays = oneMillionElms;
int size = oneMillionArrays.size();
for( int index = size ; index >= 0 ; index-- )  {
    int elms = oneMillionArrays.get(index);
    if( elms == ... || ... ) {
        oneMillionArrays.remove(i);
    }
}

[Piet Souris]

No need for line 2

[Piet Souris]

And the get-method is very inefficient for linked lists

[Carey Brown]

It's an ArrayList per 1st post.

[Carey Brown]

Practicing...

		List<Integer> list = new ArrayList<>();
		list.add( 1 );
		list.add( 2 );
		list.add( 3 );
		Predicate<Integer> pred = i -> i % 2 == 0;
		List<Integer> newList = list.stream()
				.filter( pred )
				.collect( Collectors.toList() );
		System.out.println( newList );

[Mike Simmons]

The quoted Stack Overflow answer seems very poor.  Yes, looping in reverse is a little better than a naive forward loop here.  And it's a little easier to understand - see how the "forward indexed loop" requires an extra i-- to make it work.  But it's still a pretty horrible option, from a performance perspective.  Here's a comparison of several options I can think of here.  All of these start with a list of values from 1 to SIZE, and then remove all odd values.  Try changing the value of SIZE to see how much it can affect things.  Note that the differences between several options are too small to measure accurately, unless you increase SIZE quite a bit... but the crappy answers like the one given on Stack Overflow are way too slow to handle much larger lists.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;

public class RemovingRows {

  private static final int SIZE = 600_000;

  public static void main(String[] args) {

    test("forward indexed loop", makeList(), list -> {
      for (int i = 0; i < list.size(); i++) {
        if (list.get(i) % 2 != 0) {
          list.remove(i);
          i--;
        }
      }
      return list;
    });

    test("reverse indexed loop", makeList(), list -> {
      for (int i = list.size() - 1; i >= 0; i--) {
        if (list.get(i) % 2 != 0) {
          list.remove(i);
        }
      }
      return list;
    });

    test("iterator on ArrayList", makeList(), list -> {
      for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
        if (it.next() % 2 != 0) {
          it.remove();
        }
      }
      return list;
    });

    test("iterator on LinkedList", new LinkedList<>(makeList()), list -> {
      for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
        if (it.next() % 2 != 0) {
          it.remove();
        }
      }
      return list;
    });

    test("make new list", makeList(), list -> {
      List<Integer> newList = new ArrayList<>();
      for (int i : list) {
        if (i % 2 == 0) {
          newList.add(i);
        }
      }
      return newList;
    });

    test("removeIf", makeList(), list -> {
      list.removeIf(n -> n % 2 != 0);
      return list;
    });

    test("removeIf on LinkedList", new LinkedList<>(makeList()), list -> {
      list.removeIf(n -> n % 2 != 0);
      return list;
    });

    test("stream new list", makeList(), list -> {
      return list.stream().filter(n -> n % 2 == 0).collect(Collectors.toList());
    });
  }

  private static List<Integer> makeList() {
    List<Integer> list = new ArrayList<>();
    for (int i = 1; i <= SIZE; i++) {
      list.add(i);
    }
    return list;
  }

  private static void test(String label, List<Integer> list, Function<List<Integer>, List<Integer>> func) {
    int beforeSize = list.size();
    long t1 = System.currentTimeMillis();
    var result = func.apply(list);
    long t2 = System.currentTimeMillis();
    int afterSize = result.size();

    System.out.println(label);
    System.out.println("  time: " + (t2 - t1)/1000.0);
    if (afterSize != beforeSize / 2) {
      System.out.println("  incorrect size: " + afterSize);
    }
    if (result.stream().anyMatch(n -> n % 2 != 0)) {
      System.out.println("  contains odd values");
    }
  }
}

[Tan Quang]

Carey Brown wrote:Is it supposed to remove multiple elems during one complete run of the loop, or only remove one element?

Is removing one (few) elements in the loop.

[Tan Quang]

Piet Souris wrote:Question 1: both

For instance, if you remove the element at index 0, then the next element to inspect is also at index 0, not index1.

I would simply use a Stream and a filter, much easier (has an implicit loop)

And nothing wrong with going backwards, easier than going forward.

Why is both? Just 1 in 2, if you choose both will give incorrect results.

[Tan Quang]

Piet Souris wrote:And the get-method is very inefficient for linked lists

I know it (at least until my most recent post). But this is a hypothetical situation that you are only allowed to use get(index).

[Tan Quang]

Carey Brown wrote:

List<Integer> oneMillionArrays = oneMillionElms;
int size = oneMillionArrays.size();
for( int index = size ; index >= 0 ; index-- )  {
    int elms = oneMillionArrays.get(index);
    if( elms == ... || ... ) {
        oneMillionArrays.remove(index);
    }
}

A long time ago, I've read an article, they have said that is: With ArrayList, you should browse by index Ascending (from 0 to size), and the List is reverse (from size to 0).
I wonder why there is this distinction? Why ArrayList shouldn't browse index in the direction of backwards (from size to 0)?

[Tan Quang]

Carey Brown wrote:Practicing...

		List<Integer> list = new ArrayList<>();
		list.add( 1 );
		list.add( 2 );
		list.add( 3 );
		Predicate<Integer> pred = i -> i % 2 == 0;
		List<Integer> newList = list.stream()
				.filter( pred )
				.collect( Collectors.toList() );
		System.out.println( newList );

This topic should be included in a hypothetical situation that you are only allowed to use get(index), all other methods aren't allowed to use!

[Carey Brown]

Tan Quang wrote:

Carey Brown wrote:

List<Integer> oneMillionArrays = oneMillionElms;
int size = oneMillionArrays.size();
for( int index = size ; index >= 0 ; index-- )  {
    int elms = oneMillionArrays.get(index);
    if( elms == ... || ... ) {
        oneMillionArrays.remove(index);
    }
}

A long time ago, I've read an article, they have said that is: With ArrayList, you should browse by index Ascending (from 0 to size), and the List is reverse (from size to 0).
I wonder why there is this distinction? Why ArrayList shouldn't browse index in the direction of backwards (from size to 0)?

Going backwards in an ArrayList while removing is more efficient. See Mike's timings.

[Tan Quang]

Mike Simmons wrote:The quoted Stack Overflow answer seems very poor.  Yes, looping in reverse is a little better than a naive forward loop here.  And it's a little easier to understand - see how the "forward indexed loop" requires an extra i-- to make it work.  But it's still a pretty horrible option, from a performance perspective.  Here's a comparison of several options I can think of here.  All of these start with a list of values from 1 to SIZE, and then remove all odd values.  Try changing the value of SIZE to see how much it can affect things.  Note that the differences between several options are too small to measure accurately, unless you increase SIZE quite a bit... but the crappy answers like the one given on Stack Overflow are way too slow to handle much larger lists...

I tested the code you sent.
Using get(index) with List is a bad thing, but it brings better performance with ArrayList. Similar to the use of Iterator brings better performance with the List but bring bad performance to ArrayList.
But this topic doesn't talk about Iterator and other methods. I have changed a little code for the current topic:

import java.util.ArrayList;
public class Main {
    private static final int SIZE = 1_000_000;
    private static ArrayList<Integer> makeList() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 1; i <= SIZE; ++i) {
          list.add(i);
        }
        return list;
    }
	public static void main(String[] args) {
	    long t1 = System.currentTimeMillis();
        ArrayList<Integer> list = makeList();
        int size = list.size();
        System.out.println("List 1 initial size ===> " + size);
        for(int i = 0; i < size; ++i) {
            int elms = list.get(i);
            if(elms % 2 != 0) {
                list.remove(i);
                --i;
                --size;
                
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("forward indexed loop, new size ==> " + list.size());
        System.out.println("cost time: " + (t2 - t1)/1000.0);
        list.clear();
        t1 = System.currentTimeMillis();
        list = makeList();
        size = list.size();
        System.out.println("List 2 initial size ===> " + size);
        for(int i = size - 1; i >= 0; --i) {
            int elms = list.get(i);
            if(elms % 2 != 0) {
                list.remove(i);
                --i;
            }
        }
        t2 = System.currentTimeMillis();
        System.out.println("reverse indexed loop, new size ==> " + list.size());
        System.out.println("cost time: " + (t2 - t1)/1000.0);
	}
}

There is a surprise that with the forwards loop will throw IndexOutOfBoundsException if only reduces i without reducing size, and will give incorrect results if only reduces size without reducing i. Therefore, with the forwards loop, we need to reduce both i and size.
From the forwards loop, we can deduce the backwards loop, the backwards loop will only need to reduce i.
Return to the main topic, this is the result when I conduct testing with ArrayList with 1 million elements with both loop types:

List 1 initial size ===> 1000000
forward indexed loop, new size ==> 500000
cost time: 41.232
List 2 initial size ===> 1000000
reverse indexed loop, new size ==> 500000
cost time: 17.133

Can see, backwards loop faster than the forwards loop with both ArrayList and List. But why I shouldn't use the backwards loop? Especially with ArrayList?

[Tan Quang]

Carey Brown wrote:Going backwards in an ArrayList while removing is more efficient. See Mike's timings.

If ignoring the problem is that the result will be reversed, so why shouldn't we use the backward loop? Especially with ArrayList as in some documents?

[Piet Souris]

Tan Quang wrote:

for(int index = 0; index < size; ++index) {

And the first question is: If I have to choose 1 in 2, I should choose to reduce size or reduce index?

Piet Souris wrote:Question 1: both

Tan Quang wrote:Why is both? Just 1 in 2, if you choose both will give incorrect results.

Tan Quang wrote:

--i;
--size;

Therefore, with the forwards loop, we need to reduce both i and size.

But perhaps I misunderstood your question.

[Carey Brown]

Tan Quang wrote:

Carey Brown wrote:Going backwards in an ArrayList while removing is more efficient. See Mike's timings.

If ignoring the problem is that the result will be reversed, so why shouldn't we use the backward loop? Especially with ArrayList as in some documents?

Don't know what you mean by "the result will be reversed". No it won't. The ArrayList is still in the same order, minus the removed entries.

[Mike Simmons]

Tan Quang wrote:Using get(index) with List is a bad thing, but it brings better performance with ArrayList.

Using get(index) with an ArrayList isn't bad at all.  The problem is, you're also using remove(index) - that has poor performance with both ArrayList and LinkedList.  Every time you remove one element, you are also forcing it to move every subsequent entry in the ArrayList by one.  So if you have 1000 entries, and delete entry #2, entries 3-1000 will all shift left by one, and become the new entries 2-999.  And you do that sort of thing every time you call remove().  That is why the performance is so bad for this method.

The reason why it's faster to do this in reverse is, it's faster to remove things the closer they are to the end.  If you start with the end, that's easy, and by the time you get to the beginning, you have already removed half the entries afterwards.  So you still have to move a bunch of entries, but you 're moving less than you would if you went from front to back.

Interestingly, if you were to use add(index, element) to add a new entry, rather than remove(index), you would find it's faster to go forward, rather than in reverse.  That's because if you add lines, you're making the list bigger as you go, so if do the beginning first, you're adding to the beginning when it's as short as it's ever going to be.  

Anyway, if for some reason you really really need to do this only using get(index) and remove(index), I guess going in reverse is the best way.  But, as shown, if you're allowed to use any other techniques, there are numerous much better ways to do this.

[Tan Quang]

Piet Souris wrote:

But perhaps I misunderstood your question.

Hmm... I'm sure I confused something...  

[Tan Quang]

Carey Brown wrote:Don't know what you mean by "the result will be reversed". No it won't. The ArrayList is still in the same order, minus the removed entries.

Yes, with remove will no problem. It is only reversed if add into another ArrayList.

[Tan Quang]

Mike Simmons wrote:Using get(index) with an ArrayList isn't bad at all.

Oops ... I just said that it was BAD with the List, NOT BAD with ArrayList.

Mike Simmons wrote:The problem is, you're also using remove(index) - that has poor performance with both ArrayList and LinkedList.  Every time you remove one element, you are also forcing it to move every subsequent entry in the ArrayList by one.  So if you have 1000 entries, and delete entry #2, entries 3-1000 will all shift left by one, and become the new entries 2-999.  And you do that sort of thing every time you call remove().  That is why the performance is so bad for this method.

The reason why it's faster to do this in reverse is, it's faster to remove things the closer they are to the end.  If you start with the end, that's easy, and by the time you get to the beginning, you have already removed half the entries afterwards.  So you still have to move a bunch of entries, but you 're moving less than you would if you went from front to back.

Interestingly, if you were to use add(index, element) to add a new entry, rather than remove(index), you would find it's faster to go forward, rather than in reverse.  That's because if you add lines, you're making the list bigger as you go, so if do the beginning first, you're adding to the beginning when it's as short as it's ever going to be.  

Anyway, if for some reason you really really need to do this only using get(index) and remove(index), I guess going in reverse is the best way.  But, as shown, if you're allowed to use any other techniques, there are numerous much better ways to do this.

I use ArrayList, List with FastList (javolution.util.FastList). Looking at their source code, it seems that remove(index) is the same: Returns the element that has just been deleted and shifts any subsequent values to the left.
So, deleting elements in the index with all 3 types of data are not a great option. I try with: Loop forward, backward and Iterator for 1 million elements. As a result, the loop forward and Iterator is similar to each other (about 40 seconds) while the loop backward to the result faster than doubling (about 16.5 seconds).

[Campbell Ritchie]

Tan Quang wrote:. . . the forwards loop will throw IndexOutOfBoundsException if only reduces i without reducing size, and will give incorrect results if only reduces size without reducing i. Therefore, with the forwards loop, we need to reduce both i and size. . . .

That is because you wrote both loops incorrectly. Don't try using variables in the loop header when you can use a feature of the list:-

/* incorrect form */
for (int i = 0; i < size; i++)
{
   // ...
}

In the following instance the loop corrects itself every time anything is added to or removed from the list; there is no need for size++; or size--;:-

/* correct form */
for (int i = 0; i < myList.size(); i++)
{
   // ...
}

If you iterate the list backwards, any changes to is size will be “behind” the point of iteration and will not cause any problems. That is why iterating backwards is preferred; it doesn't need i++; nor i--;nor size++; nor size--;

/* incorrect form but it won't cause any problems */
for (int i = size - 1; i >= 0; i--)
{
   // ...
}

/* correct form */
for (int i = myList.size() - 1; i >= 0; i--)
{
   // ...
}

Oops ... I just said that it was BAD with the List, NOT BAD with ArrayList.

I think you have misunderstood the difference between declared tyes and runtime types. If you declare a variable as type List<XYZ>, which is correct, that permits the runtime type of the list to be a LinkedList<XYZ> or an ArrayList<XYZ>.  It is therefore best to write your loop to accommodate both kinds of List. I tried MS' code on JShell and got the following results:-

RemovingRows.main(null);
forward indexed loop
 time: 138.106
reverse indexed loop
 time: 45.547
iterator on ArrayList
 time: 139.262
iterator on LinkedList
 time: 0.064
make new list
 time: 0.058
removeIf
 time: 0.076
removeIf on LinkedList
 time: 0.069
stream new list
 time: 0.057

Using get() on a LinkedList seems even slower, but that might be because remove(i) causes boxing conversion to an Integer.

jshell> run()
|  Exception java.lang.RuntimeException: Over 1000s at i = 234000
|        at run (#19:12)
|        at (#20:1)

I think the following is the explanation, part of which MS has already told you:-
You will find the following in the documentation for ArrayList

All of the other operations run in linear time (roughly speaking).

That includes remove(). So repeated removals of odd numbers will run in quadratic time. If you iterate backwards in MS' array list, after the first removal, nothing needs to be moved, after the second removal one item, after the third two items, etc. This doesn't change if you use an Iterator. If you iterate forwards, after the first removal you move 599,998 items, after the second 599,997 items, after the third 599,996 items. This actually shows the problem of removing elements from the beginning and middle of an array list; it runs in linear time O(n) where n is the number of elements to the “right” of the removal point (well, I think it does!). Removal of elements from the middle of a linked list is much faster (constant time), but only if you have a handle to th element to remove already. That is why the removal technique with an Iterator runs so much faster on a linked list; the Iterator already has a reference to the element to remove. Creating a new List, either in a loop or with a Stream, is just as fast. I don't know how removeIf() is implemented; that is fast, but slightly slower on a linked list.

removeIf on linked list: 0.258s

I shall have to remember always to use removeIf() for removing elements from a list.

[Tan Quang]

Campbell Ritchie wrote:Using get() on a LinkedList seems even slower...

Yes, that's why I usually only use get(index) with ArrayList and always limit the maximum using it with List or LinkedList.
I have a question like this, the following code is using get(index) and remove(index) for List.

List<String> stringList = someSList;
for(int index = 0; index < stringList.size();) {
	String str = stringList.get(index);
	if(str == null) {
		stringList.remove(index); // remove elements at the `index` position
		continue; // stop execute the code below and move to the next element at the current `index` position
	}
	// ...do some work with str...
	++index; // If `str` doesn't null, increase the `index` value, move to the next element.
}

As mentioned above, both methods provide poor performance, so I will switch to use Iterator:

List<String> stringList = someSList;
for(Iterator<String> iter = stringList .iterator(); iter.hasNext();) {
	String str = iter.next();
	if(str == null) {
		iter.remove(); // remove null element
		continue; // stop execute the code below and move to the next element
	}
	// ...do some work with str...
}

As the code that I have converted to using the Iterator above, the removal of the null element is similar to the get / remove(index) loop, all have continue keyword to stop executing the code below. Only one thing is differrence in the Iterator, whether str has null or not it will definitely switch to the next element.
So, the code that converts to Iterator as I understand and explain exactly not (especially continue keyword)? If it's not correct, please explain the problem and suggest me how to fix it.  
P/s: Yes, new methods all bring better performance get / remove(index) but perhaps but the new methods should be discussed in another topic. Please take a look at this as the topic on a Java version that doesn't support those improvement methods.

[Campbell Ritchie]

Tan Quang wrote:

Campbell Ritchie wrote:Using get() on a LinkedList seems even slower...

Yes, that's why I usually only use get(index) with ArrayList  . . .

I think you misunderstood what I said. I said that the removal app runs even slower with a linked list and get(). I wasn't saying that get() is slower on a linked list, even though we all know get() does run slowly on a linked list. Remember that you may not be removing the element at index i, but it might be boxed to the Integer, in which case it would be using equals() as well. That might be the explanation for its unusually slow execution.
I suggest you don't use continue; in that context because you can readily replace it with else. See line 7 below.

List<String> stringList = someSList;
for(Iterator<String> iter = stringList.iterator(); iter.hasNext();) {
    String str = iter.next();
    if(str == null) {
        iter.remove(); // remove null element
    }
    else {
        // ...do some work with str...
    }
}

Since you should usually declare a List as type List<XYZ>, it makes it awkward to use the get(), remove(), etc. methods at all.

[Mike Simmons]

Tan Quang wrote:So, the code that converts to Iterator as I understand and explain exactly not (especially continue keyword)? If it's not correct, please explain the problem and suggest me how to fix it.  
P/s: Yes, new methods all bring better performance get / remove(index) but perhaps but the new methods should be discussed in another topic. Please take a look at this as the topic on a Java version that doesn't support those improvement methods.

Other than the unnecessary continue, there's nothing really wrong with your implementation using Iterator.remove().  I already showed code to do that, and the timing is just as bad as the forward loop, for the same fundamental reason.  Each remove() is moving a bunch of elements by one index position.  Lots of unnecessary work.

For whatever reason you need to use Java 7... you can still use the method I labeled as Iterator on LinkedList, or make new list.  Those still work in JDK 7.  I'm sorry if you really really want to use the same ArrayList you started with, but it's just a bad idea under Java 7.  There's only so much we can do if you are unwilling or unable to use better techniques.

[Tan Quang]

Campbell Ritchie wrote:I suggest you don't use continue; in that context because you can readily replace it with else...

Yes, I understand can use else there. Why I shouldn't use continue keyword? Is it slow? Or does it cost a lot of resources? Or both?

Campbell Ritchie wrote:Since you should usually declare a List as type List<XYZ>, it makes it awkward to use the get(), remove(), etc. methods at all.

Yes, I don't want to appear warning that I am using raw type so I often try to add the specified parameter to the data type.

[Tan Quang]

Mike Simmons wrote:Other than the unnecessary continue, there's nothing really wrong with your implementation using Iterator.remove().  I already showed code to do that, and the timing is just as bad as the forward loop, for the same fundamental reason.  Each remove() is moving a bunch of elements by one index position.  Lots of unnecessary work.

For whatever reason you need to use Java 7... you can still use the method I labeled as Iterator on LinkedList, or make new list.  Those still work in JDK 7.  I'm sorry if you really really want to use the same ArrayList you started with, but it's just a bad idea under Java 7.  There's only so much we can do if you are unwilling or unable to use better techniques.

I'll not use Iterator with ArrayList in most cases.
As a result after testing the code you give, creating a new list or using new methods like removeIf, stream,... are very fast. But how does their memory cost? It seems that it is not low (especially the continuous creation of new lists)...

[Carey Brown]

Tan Quang wrote:Why I shouldn't use continue keyword? Is it slow? Or does it cost a lot of resources? Or both?

Continue is very efficient but it "smells" like a GOTO and GOTOs are highly discouraged in high level languages as a potential source of bugs and reduced readability. There are cases where a carefully placed continue will improve the code but even then you're asking the seasoned reader to stop and understand why the continue was chosen at all. So, all things being equal, you should choose 'else' over 'continue' in your case.

[Carey Brown]

Tan Quang wrote:But how does their memory cost? It seems that it is not low (especially the continuous creation of new lists)...

First of all, your new list does not contain copies of all of the objects in the original list, it only contains copies of some of the references, and references are quite small. Secondly, more often than not the new list is then assigned to the old list variable thus freeing up the old list for garbage collection.

[Tan Quang]

Carey Brown wrote:First of all, your new list does not contain copies of all of the objects in the original list, it only contains copies of some of the references, and references are quite small. Secondly, more often than not the new list is then assigned to the old list variable thus freeing up the old list for garbage collection.

I tested the removeIf and stream method on ArrayList, this is the code that I use to test (extends from the loop code above):

...
        list.clear();
        t1 = System.currentTimeMillis();
        list = makeList();
        System.out.println("List 3 initial size ===> " + list.size());
        list.removeIf(n -> n % 2 != 0);
        t2 = System.currentTimeMillis();
        System.out.println("list removeIf, new size ==> " + list.size());
        System.out.println("cost time: " + (t2 - t1)/1000.0); // 0.049
        list.clear();
        t1 = System.currentTimeMillis();
        list = makeList();
        System.out.println("List 4 initial size ===> " + list.size());
        list = list.stream().filter(n -> n % 2 == 0).collect(Collectors.toCollection(ArrayList::new));
        t2 = System.currentTimeMillis();
        System.out.println("list stream, new size ==> " + list.size());
        System.out.println("cost time: " + (t2 - t1)/1000.0); // 0.053
...

It is true that it's very fast, but I'm curious about the cost (memory, CPU) that it uses?
And it seems, it is designed for simple conditions, with complex conditions, the use of it doesn't seem feasible.

[Campbell Ritchie]

I would say your figures (53ms and 49ms) mean the two algorithms run about the same speed.

Tan Quang wrote:. . . I'm curious about the cost (memory, CPU) that it uses? . . .

Don't worry about either. You might be able to work out the CPU load and memory load if you use a profiling tool or jconsole or similar. The memory load for removeIf() is probably slight and that for creating a new List is probably the same as the memory footprint of the new List. 500,000 references on a 64‑bit machine might occupy 8 bytes each, so that makes slightly over 4MB. Think back to 1962 when 4MB was an astronomical amount of memory and would have cost millions. Now I can buy 1000× that much memory for about the same price as a pizza. The CPU load per second is probably the same for all techniques, so the faster algorithms will use less power.

. . . with complex conditions, the use of it doesn't seem feasible.

You can make your conditions as simple or as complicated as you like. You can split conditions and call filter() repeatedly, on each part. Remember, the more experienced you are, the simpler you will make your conditions.

[Mike Simmons]

The removeIf() implementation is very fast, and requires little extra memory.  And there is absolutely no problem at all with putting complex conditions in it.  Why would there be a problem?

[Tan Quang]

Campbell Ritchie wrote:You can make your conditions as simple or as complicated as you like. You can split conditions and call filter() repeatedly, on each part. Remember, the more experienced you are, the simpler you will make your conditions.

With stream().filter() there is working method quite similar to Mike Simmons's "make new list" code above. I feel it seems to be suitable for use with the List because if used on ArrayList it will create a new ArrayList (while just need Collectors.toList() with List - maybe that's why in my test, removeIf has been about 4ms faster).

Mike Simmons wrote:The removeIf() implementation is very fast, and requires little extra memory.  And there is absolutely no problem at all with putting complex conditions in it.  Why would there be a problem?

Yes, it also helps me no need to use the loop.
-----------------------------------------------------------
I know that with ArrayList, add / remove elements is not a good idea. But I wonder:
If I want to add a new element, the use:

ArrayList.add(int index = ArrayList.size(), E element)

with the use

ArrayList.add(E element)

When remove elements, the use:

ArrayList.removeRange(int fromIndex = 0, int toIndex = ArrayList.size())

with the use

ArrayList.removeAll(ArrayList)

with the use

ArrayList.clear()

Which method will bring better performance for add / remove elements?

[Campbell Ritchie]

Tan Quang wrote:. . . I know that with ArrayList, add / remove elements is not a good idea.

Nobody has said that. We said that adding or removing at the beginning or middle of an array list runs in linear time.

. . . Which method will bring better performance for add / remove elements?

Wrong question. The correct question is, “Which technique provides the better scope for stupid errors on the programmer's part?” Or, maybe, “Which technique provides the better scope for confusing anybody reading your code?”

[Tan Quang]

Campbell Ritchie wrote:Nobody has said that. We said that adding or removing at the beginning or middle of an array list runs in linear time.
....Wrong question. The correct question is, “Which technique provides the better scope for stupid errors on the programmer's part?” Or, maybe, “Which technique provides the better scope for confusing anybody reading your code?”

Well, it seems I have found the answer (combined with ArrayList's source code) for this question.
With ArrayList.removeRange (0, ArrayList.size() will be similar to ArrayList.removeAll(ArrayList).
But they are slower than ArrayList.clear().

[Mike Simmons]

Tan Quang wrote:Well, it seems I have found the answer (combined with ArrayList's source code) for this question.
With ArrayList.removeRange (0, ArrayList.size() will be similar to ArrayList.removeAll(ArrayList).
But they are slower than ArrayList.clear().

Um, no.  Those methods don't even do the same thing.  Well, clear() and removeRange(0, list.size()) do exactly the same thing, with nearly the same speed.  But removeAll() takes an argument, and has to check every element in its own list to see if it's contained in the argument list, and only delete those elements that are in the argument list.  That takes a lot more time - but more importantly, it's a different operation, so why even compare the time they take?  Pick the operation that matches what you need to do, not the one that's fastest.

[Mike Simmons]

Hmmm, I realize now that when you say ArrayList.removeAll(ArrayList), you actually mean ArrayList is a variable name.  That's very confusing, since it looks like a class name.  Better to say list.removeAll(list), or arrayList.removeAll(arrayList).  Note the capitalization.  Variable names should look like variable names, not like class names.

Anyway, yes, I suppose list.removeAll(list) will do exactly the same thing as list.clear().  It's just a really inefficient, silly way to do things.  Obviously clear() will be faster, and more importantly, easier to read, and harder to make a mistake with when typing it.  So just use clear.  Easy.

[Tan Quang]

Mike Simmons wrote:Um, no.  Those methods don't even do the same thing.  Well, clear() and removeRange(0, list.size()) do exactly the same thing, with nearly the same speed.  But removeAll() takes an argument, and has to check every element in its own list to see if it's contained in the argument list, and only delete those elements that are in the argument list.  That takes a lot more time - but more importantly, it's a different operation, so why even compare the time they take?  Pick the operation that matches what you need to do, not the one that's fastest.

It is true that removeAll seems more "safe", but it takes more time.

ArrayList.clear() is O(n) and of removeAll is O(n^2)

Well, I don't think the performance difference is "small" here.