title: How to efficiently (performance) remove many items from List in Java?
body: <p>I have quite large List named items (>= 1,000,000 items) and some condition denoted by &lt;cond&gt; that selects items to be deleted and &lt;cond&gt; is true for many (maybe half) of items on my list.</p>
  
  <p>My goal is to efficiently remove items selected by &lt;cond&gt; and retain all other items, source list may be modified, new list may be created - best way to do it should be chosen considering performance.</p>
  
  <p>Here is my testing code:</p>
  
  <pre><code>    System.out.println("preparing items");
      List&lt;Integer&gt; items = new ArrayList&lt;Integer&gt;(); // Integer is for demo
      for (int i = 0; i &lt; 1000000; i++) {
          items.add(i * 3); // just for demo
      }
  
      System.out.println("deleting items");
      long startMillis = System.currentTimeMillis();
      items = removeMany(items);
      long endMillis = System.currentTimeMillis();
  
      System.out.println("after remove: items.size=" + items.size() + 
              " and it took " + (endMillis - startMillis) + " milli(s)");
  </code></pre>
  
  <p>and naive implementation:</p>
  
  <pre><code>public static &lt;T&gt; List&lt;T&gt; removeMany(List&lt;T&gt; items) {
      int i = 0;
      Iterator&lt;T&gt; iter = items.iterator();
      while (iter.hasNext()) {
          T item = iter.next();
          // &lt;cond&gt; goes here
          if (/*&lt;cond&gt;: */i % 2 == 0) {
              iter.remove();
          }
          i++;
      }
      return items;
  }
  </code></pre>
  
  <p>As you can see I used item index modulo 2 == 0 as remove condition (&lt;cond&gt;) - just for demonstation purposes.</p>
  
  <p>What better version of <code>removeMany</code> may be provided and why this better version is actually better?</p>