// Temporary class to show the example
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
链接列表（3.9秒）
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
清单（2.4秒）
List<Temp> list = new List<Temp>(); // 2.4 seconds
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.Add(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
Even if you only access data essentially it is much slower!! 我说永远不要使用linkList .
Here is another comparison performing a lot of inserts (we plan on inserting an item at the middle of the list)
链接列表（51秒）
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
var curNode = list.First;
for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
curNode = curNode.Next;
list.AddAfter(curNode, a); // Insert it after
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
清单（7.26秒）
List<Temp> list = new List<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.Insert(i / 2, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
链接列表，其中包含插入位置的参考（.04秒）
list.AddLast(new Temp(1,1,1,1));
var referenceNode = list.First;
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
list.AddBefore(referenceNode, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
因此，只有当您计划插入多个项目并且 also 某处具有您计划插入项目的位置的引用时，才使用链接列表 . 仅仅因为你必须插入很多项目它不会使它更快，因为搜索你想要插入它的位置需要时间 .
LinkedList<T> 只是在它's most efficient if you are accessing sequential data (either forwards or backwards) - random access is relatively expensive since it must walk the chain each time (hence why it doesn'有一个索引器） . 但是，因为 List<T> 本质上只是一个数组（带有包装器），随机访问就可以了 .
static void Main()
{
LinkedListPerformance.AddFirst_List(); // 12028 ms
LinkedListPerformance.AddFirst_LinkedList(); // 33 ms
LinkedListPerformance.AddLast_List(); // 33 ms
LinkedListPerformance.AddLast_LinkedList(); // 32 ms
LinkedListPerformance.Enumerate_List(); // 1.08 ms
LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms
//I tried below as fun exercise - not very meaningful, see code
//sort of equivalent to insertion when having the reference to middle node
LinkedListPerformance.AddMiddle_List(); // 5724 ms
LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms
Environment.Exit(-1);
}
和代码：
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace stackoverflow
{
static class LinkedListPerformance
{
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
static readonly int start = 0;
static readonly int end = 123456;
static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);
static Temp temp(int i)
{
return new Temp(i, i, i, i);
}
static void StopAndPrint(this Stopwatch watch)
{
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);
}
public static void AddFirst_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(0, temp(i));
watch.StopAndPrint();
}
public static void AddFirst_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddFirst(temp(i));
watch.StopAndPrint();
}
public static void AddLast_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Add(temp(i));
watch.StopAndPrint();
}
public static void AddLast_LinkedList()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (int i = start; i < end; i++)
list.AddLast(temp(i));
watch.StopAndPrint();
}
public static void Enumerate_List()
{
var list = new List<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
public static void Enumerate_LinkedList()
{
var list = new LinkedList<Temp>(query);
var watch = Stopwatch.StartNew();
foreach (var item in list)
{
}
watch.StopAndPrint();
}
//for the fun of it, I tried to time inserting to the middle of
//linked list - this is by no means a realistic scenario! or may be
//these make sense if you assume you have the reference to middle node
//insertion to the middle of list
public static void AddMiddle_List()
{
var list = new List<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
list.Insert(list.Count / 2, temp(i));
watch.StopAndPrint();
}
//insertion in linked list in such a fashion that
//it has the same effect as inserting into the middle of list
public static void AddMiddle_LinkedList1()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
LinkedListNode<Temp> evenNode = null, oddNode = null;
for (int i = start; i < end; i++)
{
if (list.Count == 0)
oddNode = evenNode = list.AddLast(temp(i));
else
if (list.Count % 2 == 1)
oddNode = list.AddBefore(evenNode, temp(i));
else
evenNode = list.AddAfter(oddNode, temp(i));
}
watch.StopAndPrint();
}
//another hacky way
public static void AddMiddle_LinkedList2()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start + 1; i < end; i += 2)
list.AddLast(temp(i));
for (int i = end - 2; i >= 0; i -= 2)
list.AddLast(temp(i));
watch.StopAndPrint();
}
//OP's original more sensible approach, but I tried to filter out
//the intermediate iteration cost in finding the middle node.
public static void AddMiddle_LinkedList3()
{
var list = new LinkedList<Temp>();
var watch = Stopwatch.StartNew();
for (var i = start; i < end; i++)
{
if (list.Count == 0)
list.AddLast(temp(i));
else
{
watch.Stop();
var curNode = list.First;
for (var j = 0; j < list.Count / 2; j++)
curNode = curNode.Next;
watch.Start();
list.AddBefore(curNode, temp(i));
}
}
watch.StopAndPrint();
}
}
}
15 回答
当您需要内置索引访问，排序（以及此二进制搜索之后）和“ToArray（）”方法时，您应该使用List .
编辑
原始答案......
我发现了有趣的结果：
链接列表（3.9秒）
清单（2.4秒）
Even if you only access data essentially it is much slower!! 我说永远不要使用linkList .
Here is another comparison performing a lot of inserts (we plan on inserting an item at the middle of the list)
链接列表（51秒）
清单（7.26秒）
链接列表，其中包含插入位置的参考（.04秒）
因此，只有当您计划插入多个项目并且 also 某处具有您计划插入项目的位置的引用时，才使用链接列表 . 仅仅因为你必须插入很多项目它不会使它更快，因为搜索你想要插入它的位置需要时间 .
在大多数情况下，
List<T>更有用 . 在列表中间添加/删除项目时，LinkedList<T>的成本会降低，而List<T>只能在列表末尾便宜地添加/删除 .LinkedList<T>只是在它's most efficient if you are accessing sequential data (either forwards or backwards) - random access is relatively expensive since it must walk the chain each time (hence why it doesn'有一个索引器） . 但是，因为List<T>本质上只是一个数组（带有包装器），随机访问就可以了 .List<T>还提供了很多支持方法 -Find，ToArray等;但是，这些也可以通过扩展方法用于.NET 3.5 / C＃3.0LinkedList<T>- 因此这不是一个因素 .将链表视为列表可能会有点误导 . 它更像是一个链条 . 事实上，在.NET中，
LinkedList<T>甚至没有实现IList<T>. 链表中没有真正的索引概念，即使它看起来似乎存在 . 当然，该类提供的方法都不接受索引 .链接列表可以单独链接，也可以双重链接 . 这指的是链中的每个元素是否仅与下一个元素（单链接）或前一个/下一个元素（双重链接）的链接 .
LinkedList<T>是双重联系的 .在内部，
List<T>由数组支持 . 这在内存中提供了非常紧凑的表示 . 相反，LinkedList<T>涉及额外的内存来存储连续元素之间的双向链接 . 因此LinkedList<T>的内存占用量通常会大于List<T>（需要注意的是List<T>可以使用未使用的内部数组元素来提高追加操作期间的性能 . ）它们也有不同的性能特征：
追加
LinkedList<T>.AddLast(item)constant timeList<T>.Add(item)摊销恒定时间，线性最坏情况Prepend
LinkedList<T>.AddFirst(item)constant timeList<T>.Insert(0, item)线性时间插入
LinkedList<T>.AddBefore(node, item)constant timeLinkedList<T>.AddAfter(node, item)constant timeList<T>.Insert(index, item)线性时间删除
LinkedList<T>.Remove(item)线性时间LinkedList<T>.Remove(node)constant timeList<T>.Remove(item)线性时间List<T>.RemoveAt(index)线性时间伯爵
LinkedList<T>.Count恒定时间List<T>.Count恒定时间包含
LinkedList<T>.Contains(item)线性时间List<T>.Contains(item)线性时间清除
LinkedList<T>.Clear()线性时间List<T>.Clear()线性时间如你所见，它们大多相当于 . 实际上，
LinkedList<T>的API使用起来比较麻烦，其内部需求的详细信息也会泄漏到您的代码中 .但是，如果您需要在列表中执行许多插入/删除操作，它会提供恒定的时间 .
List<T>提供线性时间，因为列表中的额外项目必须在插入/移除后随机移动 .链接列表可以非常快速地插入或删除列表成员 . 链表中的每个成员都包含指向列表中下一个成员的指针，以便在位置i处插入成员：
更新成员i-1中的指针以指向新成员
将新成员中的指针设置为指向成员i
链表的缺点是随机访问是不可能的 . 访问成员需要遍历列表，直到找到所需的成员 .
List和LinkedList之间的区别在于它们的底层实现 . List是基于数组的集合（ArrayList） . LinkedList是基于节点指针的集合（LinkedListNode） . 在API级别的使用上，两者都非常相同，因为它们都实现了相同的接口集，例如ICollection，IEnumerable等 .
当性能很重要时，关键的区别就在于例如，如果要实现具有大量"INSERT"操作的列表，则LinkedList优于List . 由于LinkedList可以在O（1）时间内完成，但List可能需要扩展底层数组的大小 . 有关更多信息/详细信息，您可能需要了解LinkedList和数组数据结构之间的算法差异 . http://en.wikipedia.org/wiki/Linked_list和Array
希望这个帮助，
我之前的回答不够准确 . 真的很可怕：D但现在我可以发布更有用和正确的答案 .
我做了一些额外的测试 . 您可以通过以下链接找到它的来源，并在您自己的环境中重新检查它：https://github.com/ukushu/DataStructuresTestsAndOther.git
Short results:
数组需要使用：
尽可能经常 . 对于相同数量的信息，它速度很快，占用的RAM范围最小 .
如果您知道所需的确切细胞数量
如果数据保存在数组<85000 b
如果需要高随机访问速度
列表需要使用：
如果需要将单元格添加到列表末尾（通常）
如果需要在列表的开头/中间添加单元格（NOT OFTEN）
如果数据保存在数组<85000 b
如果需要高随机访问速度
LinkedList需要使用：
如果需要在列表的开头/中间/末尾添加单元格（通常）
如果只需要顺序访问（向前/向后）
如果您需要保存大型物品，但物品数量较少 .
最好不要使用大量的项目，因为它使用额外的内存用于链接 .
More details:
Interesting to know:
LinkedList<T>内部不是.NET中的List . 它甚至没有实现IList<T>. 这就是为什么缺少与索引相关的索引和方法的原因 .LinkedList<T>是基于节点指针的集合 . 在.NET中，它是双重链接实现 . 这意味着先前/下一个元素具有到当前元素的链接 . 并且数据是碎片化的 - 不同的列表对象可以位于RAM的不同位置 . 此外，LinkedList<T>将使用比List<T>或Array更多的内存 ..Net中的
List<T>是Java的ArrayList<T>的替代品 . 这意味着这是数组包装器 . 因此它在内存中被分配为一个连续的数据块 . 如果分配的数据大小超过85000字节，它将被移动到大对象堆 . 根据大小，这可能导致堆碎片（一种温和的内存泄漏形式） . 但是在同一时间，如果大小<85000字节 - 这在内存中提供了非常紧凑和快速访问的表示 .单个连续块对于随机访问性能和内存消耗是首选，但对于需要定期更改大小的集合，通常需要将诸如Array之类的结构复制到新位置，而链表仅需要管理新的内存插入/删除节点 .
链表对数组的主要优点是链接为我们提供了有效重新排列项的能力 . 塞奇威克，p . 91
使用LinkedList的常见情况是这样的：
假设您要从大小的字符串列表中删除许多特定字符串，例如100,000 . 要删除的字符串可以在HashSet dic中查找，字符串列表被认为包含30,000到60,000个要删除的字符串 .
那么存储100,000个字符串的最佳类型是什么？答案是LinkedList . 如果它们存储在ArrayList中，那么迭代它并删除匹配的字符串最多需要数十亿次操作，而使用迭代器和remove（）方法只需要大约100,000次操作 .
这是根据Tono Nam已接受的答案改编而来纠正其中的一些错误测量 .
考试：
和代码：
您可以看到结果与其他人在此处记录的理论性能一致 . 非常清楚 - 在插入的情况下，
LinkedList<T>获得了大量时间 . 我没有测试从列表中间删除，但结果应该是相同的 . 当然List<T>还有其他领域，它像O（1）随机访问一样表现得更好 .从本质上讲，.NET中的
List<>是数组的包装器 .LinkedList<>是一个链表 . 所以问题归结为，数组和链表之间有什么区别，什么时候应该使用数组而不是链表 . 您决定使用哪两个最重要的因素可能归结为：链接列表具有更好的插入/删除性能，只要插入/删除不在集合中的最后一个元素上即可 . 这是因为数组必须移动插入/移除点之后的所有剩余元素 . 但是，如果插入/移除位于列表的尾端，则不需要此移位（尽管如果超出其容量，则可能需要调整阵列的大小） .
Arrays具有更好的访问功能 . 数组可以直接索引（在恒定时间内） . 必须遍历链接列表（线性时间） .
我同意上面提到的大部分观点 . 而且我也同意List在大多数情况下看起来更明显 .
但是，我只想补充一点，有很多实例，其中LinkedList是比List更好的选择，以提高效率 .
假设你正在遍历元素，你想要执行大量的插入/删除; LinkedList在线性O（n）时间内完成，而List在二次O（n ^ 2）时间内完成 .
假设您想要一次又一次地访问更大的对象，LinkedList变得非常有用 .
使用LinkedList可以更好地实现
Deque（）和queue（） .
一旦处理了许多更大的对象，增加LinkedList的大小就会容易得多 .
希望有人会发现这些评论有用 .
使用
LinkedList<>时您不知道有多少物体通过防洪闸门 . 例如，
Token Stream.当你只想在末尾删除\ insert时 .
对于其他一切，最好使用
List<>.这里有很多平均答案......
一些链表实现使用预分配节点的底层块 . 如果他们不这样做，那么恒定时间/线性时间就不那么重要了，因为内存性能会很差，缓存性能会更差 .
使用链接列表时
1）您想要线程安全 . 您可以构建更好的线程安全算法 . 锁定成本将主导并发样式列表 .
2）如果你有一个像结构一样的大型队列，并且想要一直移除或添加任何地方但最终 . > 100K列表存在但不常见 .
我问similar question related to performance of the LinkedList collection，发现Steven Cleary's C# implement of Deque是一个解决方案 . 与Queue系列不同，Deque允许前后移动物品 . 它类似于链表，但具有改进的性能 .