C# 性能差异……如此戏剧化？

Performance differences... so dramatic?

提问by Alvin Wong

Just now I read some posts about List<T>vs LinkedList<T>, so I decided to benchmark some structures myself. I benchmarked Stack<T>, Queue<T>, List<T>and LinkedList<T>by adding data and removing data to/from the front/end. Here's the benchmark result:

刚才我读了一些关于List<T>vs 的帖子LinkedList<T>，所以我决定自己对一些结构进行基准测试。我为基准Stack<T>，Queue<T>，List<T>和LinkedList<T>通过从前/结束添加数据和删除数据到/。这是基准测试结果：

               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:

代码：

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<int> stack = new Stack<int>();
            Queue<int> queue = new Queue<int>();
            List<int> list1 = new List<int>();
            List<int> list2 = new List<int>();
            LinkedList<int> linkedlist1 = new LinkedList<int>();
            LinkedList<int> linkedlist2 = new LinkedList<int>();
            int dummy;


            sw.Reset();
            Console.Write("{0,40}", "Pushing to Stack...");
            sw.Start();
            for (int i = 0; i < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 100000; i++)
            {
                dummy = linkedlist2.Last.Value;
                linkedlist2.RemoveLast();
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
        }
    }
}

The differences are sodramatic!

差异是如此显着！

As you can see, the performance of Stack<T>and Queue<T>are fast and comparable, that's expected.

正如你所看到的，性能Stack<T>和Queue<T>正在快速和可比，这是预期。

For List<T>, 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 Stack<T>.

因为List<T>，使用前端和后端有很大的不同！令我惊讶的是，从末尾添加/删除的性能实际上与Stack<T>.

For LinkedList<T>, manipulating with the front is fast (-er than List<T>), but for the end, it is incredibly slow for removingmanipulating with the end is too.

对于LinkedList<T>，使用前端进行操作很快（-er than List<T>），但是对于最后，删除使用后端进行操作的速度也非常慢。

---

---

So... can any experts account on:

所以......任何专家都可以解释：

1. the similarity in performance of using Stack<T>and the end of List<T>,
2. the differences in using the front and the end of List<T>, and
3. the reason that using the end of LinkedList<T>is soslow(not applicable as that is a coding error due to the use of Linq's Last(), thanks to CodesInChaos)?

1. 使用Stack<T>和结束的性能相似List<T>，
2. 使用前端和后端的差异List<T>，以及
3. 在使用结束的原因LinkedList<T>是如此缓慢（不适用，因为这是一个编码错误是由于使用LINQ的的Last()，感谢CodesInChaos）？

I think I know why List<T>doesn't handle the front so well... because List<T>needs to move the whole list back and fro when doing that. Correct me if I am wrong.

我想我知道为什么List<T>不能很好地处理前端......因为List<T>这样做时需要来回移动整个列表。如果我错了，请纠正我。

P.S. My System.Diagnostics.Stopwatch.Frequencyis 2435947, and the program is targeted to .NET 4 Client Profile and compiled with C# 4.0, on Windows 7 Visual Studio 2010.

PS My System.Diagnostics.Stopwatch.Frequencyis 2435947，该程序针对 .NET 4 Client Profile 并在 Windows 7 Visual Studio 2010 上使用 C# 4.0 编译。

采纳答案by CodesInChaos

Concerning 1:

关于 1：

Stack<T>'s and List<T>'s performance being similar isn't surprising. I'd expect both of them to use arrays with a doubling strategy. This leads to amortized constant-time additions.

Stack<T>'s 和List<T>'s 的表现相似并不奇怪。我希望他们都使用具有加倍策略的数组。这导致摊销的恒定时间添加。

You can use List<T>everywhere you can use Stack<T>, but it leads to less expressive code.

您可以List<T>在任何可以使用的地方使用Stack<T>，但这会导致代码的表现力较差。

Concerning 2:

关于2：

I think I know why List<T>doesn't handle the front so well... because List<T>needs to move the whole list back and fro when doing that.

我想我知道为什么List<T>不能很好地处理前端......因为List<T>这样做时需要来回移动整个列表。

That's correct. Inserting/removing elements at the beginning is expensive because it moves all elements. Getting or replacing elements at the beginning on the other hand is cheap.

没错。在开始时插入/删除元素很昂贵，因为它移动了所有元素。另一方面，在开始时获取或替换元素很便宜。

Concerning 3:

关于 3：

Your slow LinkedList<T>.RemoveLastvalue is a mistake in your benchmarking code.

你的慢LinkedList<T>.RemoveLast值是你的基准代码中的一个错误。

Removing or getting the last item of a doubly linked list is cheap. In the case of LinkedList<T>that means that RemoveLastand Lastare cheap.

删除或获取双向链表的最后一项很便宜。在这种情况下，LinkedList<T>这意味着RemoveLast并且Last便宜。

But you weren't using the Lastproperty, but LINQ's extension method Last(). On collections that don't implement IList<T>it iterates the whole list, giving it O(n)runtime.

但是您没有使用该Last属性，而是使用 LINQ 的扩展方法Last(). 在没有实现IList<T>它的集合上迭代整个列表，给它O(n)运行时。

回答by Arun Manivannan

I have a Java background and I guess your question relates more to general datastructures than a specific language. Also, I apologize if my statements are incorrect.

我有 Java 背景，我猜您的问题更多地与通用数据结构有关，而不是特定语言。另外，如果我的陈述有误，我深表歉意。

1. the similarity in performance of using Stack and the end of List

1.使用Stack和List结尾的性能相似

2. the differences in using the front and the end of List, and

2.List的前端和后端使用的区别，以及

At least in Java, Stacks are implemented using arrays(Apologies if that is not the case with C#. You could refer to the source for the implementation) And same is the case of Lists. Typical with an array, all insertions at the end takes lesser time than at the beginning because the pre-existing values in the array needs to be moved down to accommodate the insertion at the beginning.

至少在 Java 中，堆栈是使用数组实现的（抱歉，如果 C# 不是这种情况。您可以参考实现的源代码）列表也是如此。典型的数组，末尾的所有插入比开头花费的时间更少，因为数组中预先存在的值需要向下移动以适应开头的插入。

Link to Stack.java sourceand its superclass Vector

链接到 Stack.java 源代码及其超类Vector

3. the reason that using the end of LinkedList is so slow?

3. 使用LinkedList结尾这么慢是什么原因？

LinkedList do not allow random accessand have to traverse through the nodes before reaching your insertion point. If you find that the performance is slower for the last nodes, then I suppose the LinkedList implementation should be a singly-linked list. I guess you would want to consider a doubly-linked-list for optimal performance while accessing elements at the end.

LinkedList不允许随机访问，在到达插入点之前必须遍历节点。如果您发现最后一个节点的性能较慢，那么我认为 LinkedList 实现应该是一个单向链表。我想您会想要在最后访问元素时考虑使用双向链表以获得最佳性能。

http://en.wikipedia.org/wiki/Linked_list

http://en.wikipedia.org/wiki/Linked_list

回答by Aki Suihkonen

The speed comes essentially from the number of operations needed to insert, delete, or search an item. You already noticed, that list needs memory transfers.

速度主要取决于插入、删除或搜索项目所需的操作数量。您已经注意到，该列表需要内存传输。

Stack is a list, that is accessible only at the top element -- and the computer always knows, where it is.

堆栈是一个列表，只能在顶部元素访问——而且计算机总是知道它在哪里。

The linked list is another thing: the start of the list is known, thus it's very fast to add or remove from the start -- but finding the last element takes time. Caching the location of the last element OTOH is only worthwhile for addition. For deletion one needs to traverse the complete list minus one element to find the 'hook' or pointer to the last one.

链表是另一回事：列表的开头是已知的，因此从开头添加或删除非常快——但是找到最后一个元素需要时间。缓存最后一个元素 OTOH 的位置只值得添加。对于删除，需要遍历减去一个元素的完整列表以找到指向最后一个元素的“钩子”或指针。

Just looking at the numbers, one can make some educated guesses of the internals of each data structure:

仅看数字，就可以对每个数据结构的内部结构做出一些有根据的猜测：

• pop from a stack is fast, as expected
• push to stack is slower. and it's slower than adding to the end of the list. Why?
  • apparently the allocation unit size for stack is smaller -- it may only increase the stack size by 100, while growing the list could be done in units of 1000.
• A list seems to be a static array. Accessing the list at the front requires memory transfers, that take time in proportion to the list length.
• Basic linked list operations shouldn't take that much longer, it's generally only required to
  • new_item.next = list_start; list_start = new_item; // to add
  • list_start = list_start.next; // to remove
  • however, as addLast is so fast, it means that also when adding or deleting to a linked list, one has to update the pointer to the last element also. So there's extra bookkeeping.
• Doubly linked lists OTOH make it relatively fast to insert and delete at both ends of the list (I've been informed that a better code uses DLLs), however,
  • links to previous and next item also double the work for the bookkeeping

• 正如预期的那样，从堆栈中弹出很快
• 推入堆栈较慢。它比添加到列表的末尾要慢。为什么？
  • 显然堆栈的分配单元大小更小——它可能只会将堆栈大小增加 100，而增加列表可以以 1000 为单位完成。
• 列表似乎是一个静态数组。访问前面的列表需要内存传输，其时间与列表长度成正比。
• 基本的链表操作不应该花那么长时间，一般只需要
  • new_item.next = list_start; list_start = new_item; // 加上
  • list_start = list_start.next; // 去除
  • 然而，由于 addLast 如此之快，这意味着在向链表添加或删除时，也必须更新指向最后一个元素的指针。所以有额外的簿记。
• 双向链表 OTOH 使得在列表两端插入和删除的速度相对较快（我被告知更好的代码使用 DLL），但是，
  • 上一个和下一个项目的链接也会使簿记工作加倍

回答by Aki Suihkonen

List<T>is a dynamic over-allocating array(a data structure you'll also see in many other languages' standard library). This means it internally uses of a "static" array (an array that can't be resized, known as just "array" in .NET) which may be and often is larger than the size of the list. Appending then simply increments a counter and uses the next, previously unused, slot of the internal array. The array is only re-allocated (which requires copying all elements) if the internal array becomes to small to accommodate all items. When that happens, the size of the array is increased by a factors (not a constant), usually 2.

List<T>是一个动态的过度分配数组（您还会在许多其他语言的标准库中看到这种数据结构）。这意味着它在内部使用了一个“静态”数组（一个不能调整大小的数组，在 .NET 中称为“数组”），它可能并且经常大于列表的大小。追加然后简单地增加一个计数器并使用内部数组的下一个以前未使用的插槽。如果内部数组变小以容纳所有项目，则仅重新分配数组（这需要复制所有元素）。发生这种情况时，数组的大小会增加一个因子（不是常数），通常是 2。

This ensures that amortizedtime complexity (basically, the average time per operation over a long sequence of operations) for appending is O(1) even in the worst case. For adding at the front, no such optimization is feasible (at least not while keeping both random access and O(1) appending at the end). It always has to copy all elements to move them into their new slots (making space for the added element in the first slot). Stack<T>does the same thing, you just don't notice the discrepancy with adding to the front because you only ever operate on one end (the fast one).

这确保了即使在最坏的情况下，追加的摊销时间复杂度（基本上，一个长操作序列中每个操作的平均时间）也是 O(1)。对于在前面添加，没有这样的优化是可行的（至少在同时保持随机访问和 O(1) 附加在末尾的情况下是不可行的）。它总是必须复制所有元素以将它们移动到新的插槽中（为第一个插槽中添加的元素腾出空间）。Stack<T>做同样的事情，你只是没有注意到添加到前面的差异，因为你只在一端（快速的）上操作。

Getting the end of a linked list depends a lot on the internals of your list. One canmaintain a reference to the last element, but this makes all operations on the list more complicated, and may (I don't have an example at hand) make some operations much more expensive. Lacking such a reference, appending to the end requires walking through allelements of the linked list to find the last node, which is of course awfully slow for lists of nontrivial size.

获取链表的结尾很大程度上取决于列表的内部结构。一个可以维持到最后一个元素的引用，但是这使得列表更复杂的所有操作，并可能（我没有在手边的例子）使一些操作更加昂贵。缺少这样的引用，追加到末尾需要遍历链表的所有元素以找到最后一个节点，这对于非平凡大小的列表来说当然非常慢。

As pointed out by @CodesInChaos, your linked list manipulation was flawed. The fast retrieval of the end you see now is most likely caused by LinkedList<T>explicitly maintaining a reference to the last node, as mentioned above. Note that getting an element not at either end is still slow.

正如@CodesInChaos 所指出的，您的链表操作存在缺陷。如上所述，您现在看到的结尾的快速检索很可能是由于LinkedList<T>显式维护对最后一个节点的引用造成的。请注意，获取不在任一端的元素仍然很慢。

回答by poke

the similarity in performance of using Stack and the end of List,

使用 Stack 和 List 结尾的性能相似，

As explained by delnan, they both use a simple array internally, so they behave very similar when working at the end. You could see a stack being a list with just access to the last object.

正如 delnan 所解释的那样，它们都在内部使用一个简单的数组，因此在最后工作时它们的行为非常相似。您可以看到堆栈是一个列表，只能访问最后一个对象。

the differences in using the front and the end of List

List前后使用的区别

You already suspected it correctly. Manipulating the beginning of a list, means that the underlying array needs to change. Adding an item usually means that you need to shift all other elements by one, same with removing. If you know that you will be manipulating both ends of a list, you're better of using a linked list.

你已经猜对了。操作列表的开头，意味着底层数组需要改变。添加一个项目通常意味着您需要将所有其他元素移动一个，与删除相同。如果您知道要操作列表的两端，则最好使用链表。

the reason that using the end of LinkedList is so slow?

使用LinkedList结尾的原因如此之慢？

Usually, element insertion and deletion for linked lists at any position can be done in constant time, as you just need to change at most two pointers. The problem is just getting to the position. A normal linked list has just a pointer to its first element. So if you want to get to the last element, you need to iterate through all elements. A queue implemented with a linked list usually solves this problem by having an additional pointer to the last element, so adding elements is possible in constant time as well. The more sophisticated data structure would be a double linked list that has both pointers to the first and lastelement, and where each element also contains a pointer to the next and previouselement.

通常，链表任意位置的元素插入和删除都可以在常数时间内完成，因为您最多只需要更改两个指针。问题只是到达位置。一个普通的链表只有一个指向它的第一个元素的指针。所以如果你想到达最后一个元素，你需要遍历所有元素。使用链表实现的队列通常通过添加指向最后一个元素的指针来解决这个问题，因此也可以在恒定时间内添加元素。更复杂的数据结构将是一个双链表，它具有指向第一个和最后一个元素的指针，并且每个元素还包含一个指向下一个和上一个元素的指针。

What you should learn about this is that there are many different data structures that are made for a single purpose, which they can handle very efficiently. Choosing the correct structure depends a lot on what you want to do.

您应该了解的是，有许多不同的数据结构是为单一目的而制作的，它们可以非常有效地处理。选择正确的结构很大程度上取决于您想要做什么。

回答by cskwg

Just improved some of the deficiencies of the previous code, especially the influence of Random and the dummy calculations. Array still tops everything, but the performance of List is impressing and LinkedList is very good for random insertions.

只是改进了之前代码的一些不足，特别是Random和dummy计算的影响。Array 仍然是最重要的，但 List 的性能令人印象深刻，LinkedList 非常适合随机插入。

The sorted results are:

排序结果如下：

12      array[i]
40      list2[i]
62      FillArray
68      list2.RemoveAt
78      stack.Pop
126     list2.Add
127     queue.Dequeue
159     stack.Push
161     foreach_linkedlist1
191     queue.Enqueue
218     linkedlist1.RemoveFirst
219     linkedlist2.RemoveLast
2470        linkedlist2.AddLast
2940        linkedlist1.AddFirst

The code is:

代码是：

using System;
using System.Collections.Generic;
using System.Diagnostics;
//
namespace Benchmarking {
    //
    static class Collections {
        //
        public static void Main() {
            const int limit = 9000000;
            Stopwatch sw = new Stopwatch();
            Stack<int> stack = new Stack<int>();
            Queue<int> queue = new Queue<int>();
            List<int> list1 = new List<int>();
            List<int> list2 = new List<int>();
            LinkedList<int> linkedlist1 = new LinkedList<int>();
            LinkedList<int> linkedlist2 = new LinkedList<int>();
            int dummy;

            sw.Reset();
            Console.Write( "{0,40}  ", "stack.Push");
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                stack.Push( i );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            sw.Reset();
            Console.Write( "{0,40}  ", "stack.Pop" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                stack.Pop();
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            sw.Reset();
            Console.Write( "{0,40}  ", "queue.Enqueue" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                queue.Enqueue( i );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            sw.Reset();
            Console.Write( "{0,40}  ", "queue.Dequeue" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                queue.Dequeue();
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );

            //sw.Reset();
            //Console.Write( "{0,40}  ", "Insert to List at the front..." );
            //sw.Start();
            //for ( int i = 0; i < limit; i++ ) {
            //  list1.Insert( 0, i );
            //}
            //sw.Stop();
            //Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            //
            //sw.Reset();
            //Console.Write( "{0,40}  ", "RemoveAt from List at the front..." );
            //sw.Start();
            //for ( int i = 0; i < limit; i++ ) {
            //  dummy = list1[ 0 ];
            //  list1.RemoveAt( 0 );
            //  dummy++;
            //}
            //sw.Stop();
            //Console.WriteLine( sw.ElapsedMilliseconds.ToString() );

            sw.Reset();
            Console.Write( "{0,40}  ", "list2.Add" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                list2.Add( i );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            sw.Reset();
            Console.Write( "{0,40}  ", "list2.RemoveAt" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                list2.RemoveAt( list2.Count - 1 );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            sw.Reset();
            Console.Write( "{0,40}  ", "linkedlist1.AddFirst" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                linkedlist1.AddFirst( i );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            sw.Reset();
            Console.Write( "{0,40}  ", "linkedlist1.RemoveFirst" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                linkedlist1.RemoveFirst();
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            sw.Reset();
            Console.Write( "{0,40}  ", "linkedlist2.AddLast" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                linkedlist2.AddLast( i );
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );
            sw.Reset();
            Console.Write( "{0,40}  ", "linkedlist2.RemoveLast" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                linkedlist2.RemoveLast();
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            // Fill again
            for ( int i = 0; i < limit; i++ ) {
                list2.Add( i );
            }
            sw.Reset();
            Console.Write( "{0,40}  ", "list2[i]" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                dummy = list2[ i ];
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            // Fill array
            sw.Reset();
            Console.Write( "{0,40}  ", "FillArray" );
            sw.Start();
            var array = new int[ limit ];
            for ( int i = 0; i < limit; i++ ) {
                array[ i ] = i;
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );

            sw.Reset();
            Console.Write( "{0,40}  ", "array[i]" );
            sw.Start();
            for ( int i = 0; i < limit; i++ ) {
                dummy = array[ i ];
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );


            // Fill again
            for ( int i = 0; i < limit; i++ ) {
                linkedlist1.AddFirst( i );
            }
            sw.Reset();
            Console.Write( "{0,40}  ", "foreach_linkedlist1" );
            sw.Start();
            foreach ( var item in linkedlist1 ) {
                dummy = item;
            }
            sw.Stop();
            Console.WriteLine( sw.ElapsedMilliseconds.ToString() );

            //
            Console.WriteLine( "Press Enter to end." );
            Console.ReadLine();
        }
    }
}