性能差异…如此戏剧性？
刚才我看了一些关于List<T> vs LinkedList<T>post ，所以我决定自己对一些结构进行基准testing。 我通过添加数据和从前端/末端删除数据，对Stack<T> ， Queue<T> ， List<T>和LinkedList<T>了基准testing。 基准testing结果如下：
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
码：
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); } } }
差异如此显着！
正如你所看到的， Stack<T>和Queue<T>是快速和可比较的，这是预期的。
对于List<T> ，使用前面和后面有很多的区别！ 而令我惊讶的是，添加/删除的性能实际上可以与Stack<T>的性能相媲美。
对于LinkedList<T> ，前面的操作比List<T>要快，但是对于最后的操作来说， 移除操作的速度非常慢 。
所以…任何专家的帐户可以：
- 使用
Stack<T>和List<T>的结尾的相似性， - 使用
List<T>的前面和末尾的区别，和 - 使用
LinkedList<T>的结尾的原因是如此之慢（不适用，因为使用Linq的Last()， 这是CodeInChaos的编码错误）？
我想我知道为什么List<T>不能很好地处理前面的内容，因为List<T>需要在整个列表中来回移动。 纠正我，如果我错了。
PS我的System.Diagnostics.Stopwatch.Frequency为2435947 ，该程序的目标是.NET 4客户端configuration文件，并在Windows 7 Visual Studio 2010中用C＃4.0编译。
关于1：
Stack<T>和List<T>的performance相似并不奇怪。 我希望他们都使用双重策略的arrays。 这导致了摊销恒定时间的增加。
您可以在任何可以使用Stack<T> List<T>地方使用List<T> ，但会导致代码expression能力下降 。
关于2：
我想我知道为什么
List<T>不能很好地处理前面的内容，因为List<T>需要在整个列表中来回移动。
这是正确的。 在开始插入/删除元素是昂贵的，因为它移动所有元素。 另一方面，一开始就获取或replace元素便宜。
关于3：
您的基准代码中的速度很慢， LinkedList<T>.RemoveLast值是一个错误。
删除或获取双向链表的最后一项是便宜的。 在LinkedList<T>的情况下，这意味着RemoveLast和Last是便宜的。
但是你没有使用Last属性，而是LINQ的扩展方法Last() 。 在没有实现IList<T>集合上迭代整个列表，给它O(n)运行时。
List<T>是一个dynamic的过度分配数组 （一个数据结构，你也可以在许多其他语言的标准库中看到）。 这意味着它在内部使用了一个“静态”数组（一个无法resize的数组，在.NET中被称为“数组”），这个数组可能并且通常大于列表的大小。 追加然后只增加一个计数器，并使用内部arrays的下一个，以前未使用的插槽。 如果内部数组变小以容纳所有项目，则只重新分配数组（要求复制所有元素）。 发生这种情况时，arrays的大小增加了一个因素（不是常数），通常是2。
这确保了即使在最坏的情况下， 延续的时间复杂度（基本上，在一长序列操作上的每个操作的平均时间）也是O（1）。 对于前面的添加，没有这样的优化是可行的（至less不保留随机访问和O（1）在最后附加）。 它总是必须复制所有元素，将它们移动到新的插槽中（为第一个插槽添加元素的空间）。 Stack<T> 做同样的事情 ，你只是没有注意到添加到前面的差异，因为你只在一端（快速的一端）操作。
获取链表的结尾在很大程度上取决于列表的内部。 我们可以保持对最后一个元素的引用，但是这会使得列表中的所有操作变得更加复杂，并且可能（我没有一个例子）使一些操作更加昂贵。 缺less这样的引用，追加到最后需要遍历链表的所有元素来查找最后一个节点，这对于非平凡大小的列表来说当然非常慢。
正如@CodesInChaos指出的，你的链表操作是有缺陷的。 如上所述，现在看到的结尾的快速检索最有可能是由LinkedList<T>明确维护对最后一个节点的引用引起的。 请注意，获取不在任何一端的元素仍然很慢。
速度主要取决于插入，删除或search项目所需的操作数量。 您已经注意到，该列表需要内存传输。
堆栈是一个列表，只能在顶层元素访问 – 而且计算机总是知道它在哪里。
链表是另一回事：列表的开头是已知的，因此从开始就添加或删除非常快 – 但是find最后一个元素需要时间。 caching最后一个元素OTOH的位置是唯一值得添加的。 对于删除，需要遍历整个列表减去一个元素来查找“钩子”或指向最后一个元素的指针。
只要看数字，就可以对每个数据结构的内部进行一些教育性的猜测：
- 如预期的那样，从堆栈popup是快速的
- 推入堆栈比较慢。 并且比添加到列表的末尾要慢。 为什么？
- 显然堆栈的分配单元尺寸较小 – 它只能将堆栈大小增加100，而增加列表可以以1000为单位完成。
- 一个列表似乎是一个静态数组。 访问前面的列表需要内存传输，这需要花费与列表长度成比例的时间。
- 基本的链表操作不应该花费那么长的时间，通常只需要
- new_item.next = list_start; list_start = new_item; // 加上
- list_start = list_start.next; // 去除
- 然而，addLast速度如此之快，意味着在添加或删除链表时，也必须将指针更新为最后一个元素。 所以还有额外的簿记。
- 双链表OTOH使它在列表两端插入和删除的速度相对较快（我已被告知更好的代码使用DLL），但是，
- 上一个和下一个项目的链接也使簿记工作翻了一番
使用Stack的性能和List的结尾相似，
正如delnan所解释的那样，它们都在内部使用一个简单的数组，所以在最后工作时它们的行为非常相似。 你可以看到一个栈只是访问最后一个对象的列表。
使用List的前端和末端的区别
你已经正确地怀疑了。 操纵列表的开始，意味着底层数组需要改变。 添加一个项目通常意味着您需要将所有其他元素移动一个，与移除相同。 如果你知道你会操纵列表的两端，你最好使用链表。
使用LinkedList结束的原因是如此之慢？
通常情况下，链接列表在任何位置的元素插入和删除都可以在同一时间完成，因为您只需要更改最多两个指针。 问题只是到了这个位置。 正常的链表只有一个指向它的第一个元素的指针。 所以如果你想要到最后一个元素，你需要遍历所有的元素。 使用链表实现的队列通常通过增加一个指向最后一个元素的指针来解决这个问题，所以在常量时间内添加元素也是可能的。 更复杂的数据结构将是一个双向链表，既有指向第一个也是最后一个元素的指针，每个元素还包含指向下一个和上一个元素的指针。
你应该知道的是，有很多不同的数据结构是为了一个单一的目的而devise的，他们可以非常有效地处理这些数据结构。 select正确的结构很大程度上取决于你想要做什么。
我有一个Java背景，我想你的问题更多地涉及到通用数据结构而不是特定的语言。 另外，如果我的陈述不正确，我很抱歉。
1.使用Stack的性能与List的结尾相似
2.使用List的前端和末端的区别，和
至less在Java中，Stacks是用数组来实现的（如果C＃没有，那么可以参考源文件）。列表也是一样的。 典型情况下，数组中的所有插入操作都比起始时间要less，因为数组中的预先存在的值需要向下移动以适应插入操作的开始。
链接到Stack.java源代码及其超类Vector
3.使用LinkedList结束的原因是如此之慢？
LinkedList 不允许随机访问 ，必须在到达插入点之前遍历节点。 如果你发现最后一个节点的性能比较慢，那么我想LinkedList实现应该是一个单链表 。 我想你会想在最后访问元素的时候考虑一个双向链表来获得最佳性能。
