title: Performance differences... so dramatic?
body: <p>Just now I read <a href="https://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist">some posts about <code>List&lt;T&gt;</code> vs <code>LinkedList&lt;T&gt;</code></a>, so I decided to benchmark some structures myself. I benchmarked <code>Stack&lt;T&gt;</code>, <code>Queue&lt;T&gt;</code>, <code>List&lt;T&gt;</code> and <code>LinkedList&lt;T&gt;</code> by adding data and removing data to/from the front/end. Here's the benchmark result:</p>
  
  <pre class="lang-none prettyprint-override"><code>               Pushing to Stack...  Time used:      7067 ticks
                Poping from Stack...  Time used:      2508 ticks
  
                 Enqueue to Queue...  Time used:      7509 ticks
               Dequeue from Queue...  Time used:      2973 ticks
  
      Insert to List at the front...  Time used:   5211897 ticks
  RemoveAt from List at the front...  Time used:   5198380 ticks
  
           Add to List at the end...  Time used:      5691 ticks
    RemoveAt from List at the end...  Time used:      3484 ticks
  
           AddFirst to LinkedList...  Time used:     14057 ticks
      RemoveFirst from LinkedList...  Time used:      5132 ticks
  
            AddLast to LinkedList...  Time used:      9294 ticks
       RemoveLast from LinkedList...  Time used:      4414 ticks
  </code></pre>
  
  <p>Code: </p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Diagnostics;
  
  namespace Benchmarking
  {
      static class Collections
      {
          public static void run()
          {
              Random rand = new Random();
              Stopwatch sw = new Stopwatch();
              Stack&lt;int&gt; stack = new Stack&lt;int&gt;();
              Queue&lt;int&gt; queue = new Queue&lt;int&gt;();
              List&lt;int&gt; list1 = new List&lt;int&gt;();
              List&lt;int&gt; list2 = new List&lt;int&gt;();
              LinkedList&lt;int&gt; linkedlist1 = new LinkedList&lt;int&gt;();
              LinkedList&lt;int&gt; linkedlist2 = new LinkedList&lt;int&gt;();
              int dummy;
  
  
              sw.Reset();
              Console.Write("{0,40}", "Pushing to Stack...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  stack.Push(rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "Poping from Stack...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = stack.Pop();
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
  
  
              sw.Reset();
              Console.Write("{0,40}", "Enqueue to Queue...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  queue.Enqueue(rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "Dequeue from Queue...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = queue.Dequeue();
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
  
  
              sw.Reset();
              Console.Write("{0,40}", "Insert to List at the front...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  list1.Insert(0, rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "RemoveAt from List at the front...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = list1[0];
                  list1.RemoveAt(0);
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
  
  
              sw.Reset();
              Console.Write("{0,40}", "Add to List at the end...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  list2.Add(rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "RemoveAt from List at the end...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = list2[list2.Count - 1];
                  list2.RemoveAt(list2.Count - 1);
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
  
  
              sw.Reset();
              Console.Write("{0,40}", "AddFirst to LinkedList...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  linkedlist1.AddFirst(rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "RemoveFirst from LinkedList...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = linkedlist1.First.Value;
                  linkedlist1.RemoveFirst();
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
  
  
              sw.Reset();
              Console.Write("{0,40}", "AddLast to LinkedList...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  linkedlist2.AddLast(rand.Next());
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
              sw.Reset();
              Console.Write("{0,40}", "RemoveLast from LinkedList...");
              sw.Start();
              for (int i = 0; i &lt; 100000; i++)
              {
                  dummy = linkedlist2.Last.Value;
                  linkedlist2.RemoveLast();
                  dummy++;
              }
              sw.Stop();
              Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
          }
      }
  }
  </code></pre>
  
  <p>The differences are <strong>so</strong> dramatic!</p>
  
  <p>As you can see, the performance of <code>Stack&lt;T&gt;</code> and <code>Queue&lt;T&gt;</code> are fast and comparable, that's expected.</p>
  
  <p>For <code>List&lt;T&gt;</code>, using the front and the end has so much differences! And to my surprise, performance of adding/removing from the end is actually comparable to the performance of <code>Stack&lt;T&gt;</code>.</p>
  
  <p>For <code>LinkedList&lt;T&gt;</code>, manipulating with the front is fast (-er than <code>List&lt;T&gt;</code>)<s>, but for the end, it is incredibly slow for removing</s> manipulating with the end is too.</p>
  
  <hr>
  
  <p>So... can any experts account on:</p>
  
  <ol>
  <li>the similarity in performance of using <code>Stack&lt;T&gt;</code> and the end of <code>List&lt;T&gt;</code>,</li>
  <li>the differences in using the front and the end of <code>List&lt;T&gt;</code>, and<s></li>
  <li>the reason that using the end of <code>LinkedList&lt;T&gt;</code> is <em>so</em> slow</s> (not applicable as that is a coding error due to the use of Linq's <code>Last()</code>, <strong>thanks to CodesInChaos</strong>)?</li>
  </ol>
  
  <p>I think I know why <code>List&lt;T&gt;</code> doesn't handle the front so well... because <code>List&lt;T&gt;</code>needs to move the whole list back and fro when doing that. Correct me if I am wrong.</p>
  
  <p>P.S. My <code>System.Diagnostics.Stopwatch.Frequency</code> is <code>2435947</code>, and the program is targeted to .NET 4 Client Profile and compiled with C# 4.0, on Windows 7 Visual Studio 2010.</p>