title: How to Quickly Remove Items From a List
body: <p>I am looking for a way to quickly remove items from a C# <code>List&lt;T&gt;</code>.  The documentation states that the <code>List.Remove()</code> and <code>List.RemoveAt()</code> operations are both <code>O(n)</code></p>
  
  <ul>
  <li><a href="http://msdn.microsoft.com/en-us/library/cd666k3e.aspx" rel="noreferrer">List.Remove</a></li>
  <li><a href="http://msdn.microsoft.com/en-us/library/5cw9x18z%28v=vs.80%29.aspx" rel="noreferrer">List.RemoveAt</a></li>
  </ul>
  
  <p>This is severely affecting my application.</p>
  
  <p>I wrote a few different remove methods and tested them all on a <code>List&lt;String&gt;</code> with 500,000 items.  The test cases are shown below...</p>
  
  <hr>
  
  <p><strong>Overview</strong></p>
  
  <p>I wrote a method that would generate a list of strings that simply contains string representations of each number ("1", "2", "3", ...).  I then attempted to <code>remove</code> every 5th item in the list.  Here is the method used to generate the list:</p>
  
  <pre><code>private List&lt;String&gt; GetList(int size)
  {
      List&lt;String&gt; myList = new List&lt;String&gt;();
      for (int i = 0; i &lt; size; i++)
          myList.Add(i.ToString());
      return myList;
  }
  </code></pre>
  
  <p><strong>Test 1: RemoveAt()</strong></p>
  
  <p>Here is the test I used to test the <code>RemoveAt()</code> method.</p>
  
  <pre><code>private void RemoveTest1(ref List&lt;String&gt; list)
  {
       for (int i = 0; i &lt; list.Count; i++)
           if (i % 5 == 0)
               list.RemoveAt(i);
  }
  </code></pre>
  
  <p><strong>Test 2: Remove()</strong></p>
  
  <p>Here is the test I used to test the <code>Remove()</code> method.</p>
  
  <pre><code>private void RemoveTest2(ref List&lt;String&gt; list)
  {
       List&lt;int&gt; itemsToRemove = new List&lt;int&gt;();
       for (int i = 0; i &lt; list.Count; i++)
          if (i % 5 == 0)
               list.Remove(list[i]);
  }
  </code></pre>
  
  <p><strong>Test 3: Set to null, sort, then RemoveRange</strong></p>
  
  <p>In this test, I looped through the list one time and set the to-be-removed items to <code>null</code>.  Then, I sorted the list (so null would be at the top), and removed all the items at the top that were set to null.
  NOTE: This reordered my list, so I may have to go put it back in the correct order.</p>
  
  <pre><code>private void RemoveTest3(ref List&lt;String&gt; list)
  {
      int numToRemove = 0;
      for (int i = 0; i &lt; list.Count; i++)
      {
          if (i % 5 == 0)
          {
              list[i] = null;
              numToRemove++;
          }
      }
      list.Sort();
      list.RemoveRange(0, numToRemove);
      // Now they're out of order...
  }
  </code></pre>
  
  <p><strong>Test 4: Create a new list, and add all of the "good" values to the new list</strong></p>
  
  <p>In this test, I created a new list, and added all of my keep-items to the new list. Then, I put all of these items into the original list.</p>
  
  <pre><code>private void RemoveTest4(ref List&lt;String&gt; list)
  {
     List&lt;String&gt; newList = new List&lt;String&gt;();
     for (int i = 0; i &lt; list.Count; i++)
     {
        if (i % 5 == 0)
           continue;
        else
           newList.Add(list[i]);
     }
  
     list.RemoveRange(0, list.Count);
     list.AddRange(newList);
  }
  </code></pre>
  
  <p><strong>Test 5: Set to null and then FindAll()</strong></p>
  
  <p>In this test, I set all the to-be-deleted items to <code>null</code>, then used the <code>FindAll()</code> feature to find all the items that are not <code>null</code></p>
  
  <pre><code>private void RemoveTest5(ref List&lt;String&gt; list)
  {
      for (int i = 0; i &lt; list.Count; i++)
         if (i % 5 == 0)
             list[i] = null;
      list = list.FindAll(x =&gt; x != null);
  }
  </code></pre>
  
  <p><strong>Test 6: Set to null and then RemoveAll()</strong></p>
  
  <p>In this test, I set all the to-be-deleted items to <code>null</code>, then used the <code>RemoveAll()</code> feature to remove all the items that are not <code>null</code></p>
  
  <pre><code>private void RemoveTest6(ref List&lt;String&gt; list)
  {
      for (int i = 0; i &lt; list.Count; i++)
          if (i % 5 == 0)
              list[i] = null;
      list.RemoveAll(x =&gt; x == null);
  }
  </code></pre>
  
  <hr>
  
  <p><strong>Client Application and Outputs</strong></p>
  
  <pre><code>int numItems = 500000;
  Stopwatch watch = new Stopwatch();
  
  // List 1...
  watch.Start();
  List&lt;String&gt; list1 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest1(ref list1);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  
  // List 2...
  watch.Start();
  List&lt;String&gt; list2 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest2(ref list2);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  
  // List 3...
  watch.Reset(); watch.Start();
  List&lt;String&gt; list3 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest3(ref list3);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  
  // List 4...
  watch.Reset(); watch.Start();
  List&lt;String&gt; list4 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest4(ref list4);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  
  // List 5...
  watch.Reset(); watch.Start();
  List&lt;String&gt; list5 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest5(ref list5);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  
  // List 6...
  watch.Reset(); watch.Start();
  List&lt;String&gt; list6 = GetList(numItems);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  
  watch.Reset(); watch.Start();
  RemoveTest6(ref list6);
  watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
  Console.WriteLine();
  </code></pre>
  
  <p><strong>Results</strong></p>
  
  <pre><code>00:00:00.1433089   // Create list
  00:00:32.8031420   // RemoveAt()
  
  00:00:32.9612512   // Forgot to reset stopwatch :(
  00:04:40.3633045   // Remove()
  
  00:00:00.2405003   // Create list
  00:00:01.1054731   // Null, Sort(), RemoveRange()
  
  00:00:00.1796988   // Create list
  00:00:00.0166984   // Add good values to new list
  
  00:00:00.2115022   // Create list
  00:00:00.0194616   // FindAll()
  
  00:00:00.3064646   // Create list
  00:00:00.0167236   // RemoveAll()
  </code></pre>
  
  <p><strong>Notes And Comments</strong></p>
  
  <ul>
  <li><p>The first two tests do not actually remove every 5th item from the list, because the list is being reordered after each remove. In fact, out of 500,000 items, only 83,334 were removed (should have been 100,000).  I am okay with this - clearly the Remove()/RemoveAt() methods are not a good idea anyway.</p></li>
  <li><p>Although I tried to remove the 5th item from the list, in <em>reality</em> there will not be such a pattern.  Entries to be removed will be random.</p></li>
  <li><p>Although I used a <code>List&lt;String&gt;</code> in this example, that will not always be the case.  It could be a <code>List&lt;Anything&gt;</code></p></li>
  <li><p>Not putting the items in the list to begin with is <strong>not</strong> an option.</p></li>
  <li><p>The other methods (3 - 6) all performed much better, <em>comparatively</em>, however I am a little concerned -- In 3, 5, and 6 I was forced to set a value to <code>null</code>, and then remove all the items according to this sentinel.  I don't like that approach because I can envision a scenario where one of the items in the list might be <code>null</code> and it would get removed unintentionally.</p></li>
  </ul>
  
  <p>My question is: What is the best way to quickly remove many items from a <code>List&lt;T&gt;</code>?  Most of the approaches I've tried look really ugly, and potentially dangerous, to me.  Is a <code>List</code> the wrong data structure?</p>
  
  <p>Right now, I am leaning towards creating a new list and adding the good items to the new list, but it seems like there should be a better way.</p>