C# 我什么时候应该使用 List 和 LinkedList
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/169973/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
When should I use a List vs a LinkedList
提问by Jonathan Allen
When is it better to use a Listvs a LinkedList?
什么时候使用List和LinkedList更好？
采纳答案by Tono Nam
Edit
编辑
Please read the comments to this answer. People claim I did not do proper tests. I agree this should not be an accepted answer. As I was learning I did some tests and felt like sharing them.
请阅读对此答案的评论。人们声称我没有进行适当的测试。我同意这不应该是一个可以接受的答案。在学习的过程中，我做了一些测试，并想分享它们。
Original answer...
原答案...
I found interesting results:
我发现了有趣的结果：
// 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;
}
}
Linked list (3.9 seconds)
链表（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;
List (2.4 seconds)
列表（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!!I say never use a linkedList.
即使您基本上只访问数据，它也会慢得多！！我说永远不要使用链表。
Here is another comparison performing a lot of inserts (we plan on inserting an item at the middle of the list)
这是另一个执行大量插入的比较（我们计划在列表中间插入一个项目）
Linked List (51 seconds)
链表（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;
List (7.26 seconds)
列表（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;
Linked List having reference of location where to insert (.04 seconds)
链接列表具有插入位置的参考（0.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;
So only if you plan on inserting several items and you alsosomewhere have the reference of where you plan to insert the item then use a linked list. Just because you have to insert a lot of items it does not make it faster because searching the location where you will like to insert it takes time.
因此，只有当您计划插入多个项目并且您还在某处拥有您计划插入项目的位置的参考时，才使用链表。仅仅因为您必须插入大量项目，它并不会使其更快，因为搜索您想要插入的位置需要时间。
回答by Michael Damatov
When you need built-in indexed access, sorting (and after this binary searching), and "ToArray()" method, you should use List.
当您需要内置索引访问、排序（以及在此二进制搜索之后）和“ToArray()”方法时，您应该使用 List。
回答by Marc Gravell
In most cases, List<T>is more useful. LinkedList<T>will have less cost when adding/removing items in the middle of the list, whereas List<T>can only cheaply add/remove at the endof the list.
大多数情况下，List<T>更有用。LinkedList<T>在列表中间添加/删除项目时成本较低，而List<T>只能在列表末尾廉价添加/删除。
LinkedList<T>is only at it'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't have an indexer). However, because a List<T>is essentially just an array (with a wrapper) random access is fine.
LinkedList<T>只有在访问顺序数据（向前或向后）时才最有效 - 随机访问相对昂贵，因为它每次都必须遍历链（因此它没有索引器）。但是，因为 aList<T>本质上只是一个数组（带有包装器），所以随机访问是可以的。
List<T>also offers a lot of support methods - Find, ToArray, etc; however, these are also available for LinkedList<T>with .NET 3.5/C# 3.0 via extension methods - so that is less of a factor.
List<T>还提供了很多的支持方法- Find，ToArray等; 但是，这些也可LinkedList<T>通过扩展方法用于.NET 3.5/C# 3.0 - 所以这不是一个因素。
回答by b3.
Linked lists provide very fast insertion or deletion of a list member. Each member in a linked list contains a pointer to the next member in the list so to insert a member at position i:
链表提供非常快速的列表成员插入或删除。链表中的每个成员都包含一个指向列表中下一个成员的指针，以便在位置 i 插入一个成员：
- update the pointer in member i-1 to point to the new member
- set the pointer in the new member to point to member i
- 更新成员 i-1 中的指针以指向新成员
- 将新成员中的指针设置为指向成员 i
The disadvantage to a linked list is that random access is not possible. Accessing a member requires traversing the list until the desired member is found.
链表的缺点是无法随机访问。访问成员需要遍历列表直到找到所需的成员。
回答by user23117
The difference between List and LinkedList lies in their underlying implementation. List is array based collection (ArrayList). LinkedList is node-pointer based collection (LinkedListNode). On the API level usage, both of them are pretty much the same since both implement same set of interfaces such as ICollection, IEnumerable, etc.
List 和 LinkedList 之间的区别在于它们的底层实现。List 是基于数组的集合 (ArrayList)。LinkedList 是基于节点指针的集合 (LinkedListNode)。在 API 级别的使用上，它们几乎相同，因为它们都实现了相同的接口集，例如 ICollection、IEnumerable 等。
The key difference comes when performance matter. For example, if you are implementing the list that has heavy "INSERT" operation, LinkedList outperforms List. Since LinkedList can do it in O(1) time, but List may need to expand the size of underlying array. For more information/detail you might want to read up on the algorithmic difference between LinkedList and array data structures. http://en.wikipedia.org/wiki/Linked_listand Array
当性能很重要时，关键的区别就出现了。例如，如果您正在实现具有大量“插入”操作的列表，则 LinkedList 优于 List。由于 LinkedList 可以在 O(1) 时间内完成，但 List 可能需要扩展底层数组的大小。有关更多信息/详细信息，您可能需要阅读 LinkedList 和数组数据结构之间的算法差异。http://en.wikipedia.org/wiki/Linked_list和数组
Hope this help,
希望这有帮助，
回答by Drew Noakes
Thinking of a linked list as a list can be a bit misleading. It's more like a chain. In fact, in .NET, LinkedList<T>does not even implement IList<T>. There is no real concept of index in a linked list, even though it may seem there is. Certainly none of the methods provided on the class accept indexes.
将链表视为列表可能有点误导。它更像是一个链条。事实上，在 .NET 中，LinkedList<T>甚至没有实现IList<T>. 链表中没有真正的索引概念，即使它看起来有。当然，该类提供的任何方法都不接受索引。
Linked lists may be singly linked, or doubly linked. This refers to whether each element in the chain has a link only to the next one (singly linked) or to both the prior/next elements (doubly linked). LinkedList<T>is doubly linked.
链表可以是单链的，也可以是双链的。这是指链中的每个元素是否仅与下一个元素（单链接）或前/后元素都有链接（双链接）。 LinkedList<T>是双重联系的。
Internally, List<T>is backed by an array. This provides a very compact representation in memory. Conversely, LinkedList<T>involves additional memory to store the bidirectional links between successive elements. So the memory footprint of a LinkedList<T>will generally be larger than for List<T>(with the caveat that List<T>can have unused internal array elements to improve performance during append operations.)
在内部，List<T>由一个数组支持。这在内存中提供了非常紧凑的表示。相反，LinkedList<T>需要额外的内存来存储连续元素之间的双向链接。所以 a 的内存占用LinkedList<T>通常会比 for 大List<T>（需要注意的是，List<T>可以使用未使用的内部数组元素来提高追加操作期间的性能。）
They have different performance characteristics too:
它们也具有不同的性能特征：
Append
附加
LinkedList<T>.AddLast(item)constant timeList<T>.Add(item)amortized constant time, linear worst case
LinkedList<T>.AddLast(item)恒定时间List<T>.Add(item)摊销固定时间，线性最坏情况
Prepend
前置
LinkedList<T>.AddFirst(item)constant timeList<T>.Insert(0, item)linear time
LinkedList<T>.AddFirst(item)恒定时间List<T>.Insert(0, item)线性时间
Insertion
插入
LinkedList<T>.AddBefore(node, item)constant timeLinkedList<T>.AddAfter(node, item)constant timeList<T>.Insert(index, item)linear time
LinkedList<T>.AddBefore(node, item)恒定时间LinkedList<T>.AddAfter(node, item)恒定时间List<T>.Insert(index, item)线性时间
Removal
移动
LinkedList<T>.Remove(item)linear timeLinkedList<T>.Remove(node)constant timeList<T>.Remove(item)linear timeList<T>.RemoveAt(index)linear time
LinkedList<T>.Remove(item)线性时间LinkedList<T>.Remove(node)恒定时间List<T>.Remove(item)线性时间List<T>.RemoveAt(index)线性时间
Count
数数
LinkedList<T>.Countconstant timeList<T>.Countconstant time
LinkedList<T>.Count恒定时间List<T>.Count恒定时间
Contains
包含
LinkedList<T>.Contains(item)linear timeList<T>.Contains(item)linear time
LinkedList<T>.Contains(item)线性时间List<T>.Contains(item)线性时间
Clear
清除
LinkedList<T>.Clear()linear timeList<T>.Clear()linear time
LinkedList<T>.Clear()线性时间List<T>.Clear()线性时间
As you can see, they're mostly equivalent. In practice, the API of LinkedList<T>is more cumbersome to use, and details of its internal needs spill out into your code.
如您所见，它们大多是等效的。在实践中， 的 APILinkedList<T>使用起来比较麻烦，其内部需求的细节会溢出到您的代码中。
However, if you need to do many insertions/removals from within a list, it offers constant time. List<T>offers linear time, as extra items in the list must be shuffled around after the insertion/removal.
但是，如果您需要从列表中进行多次插入/删除操作，它会提供恒定的时间。 List<T>提供线性时间，因为列表中的额外项目必须在插入/删除后重新排列。
回答by Antony Thomas
Use LinkedList<>when
使用LinkedList<>时
- You don't know how many objects are coming through the flood gate. For example,
Token Stream. - When you ONLY wanted to delete\insert at the ends.
- 你不知道有多少物体通过防洪闸。例如，
Token Stream。 - 当您只想在末尾删除\插入时。
For everything else, it is better to use List<>.
对于其他一切，最好使用List<>.
回答by Dr. Alrawi
The primary advantage of linked lists over arrays is that the links provide us with the capability to rearrange the items efficiently. Sedgewick, p. 91
链表相对于数组的主要优点是链接为我们提供了有效重新排列项目的能力。塞奇威克，第。91
回答by nawfal
This is adapted from Tono Nam's accepted answer correcting a few wrong measurements in it.
这是改编自Tono Nam接受的答案，纠正了其中的一些错误测量。
The test:
考试：
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);
}
And the code:
和代码：
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();
}
}
}
You can see the results are in accordance with theoretical performance others have documented here. Quite clear - LinkedList<T>gains big time in case of insertions. I haven't tested for removal from the middle of list, but the result should be the same. Of course List<T>has other areas where it performs way better like O(1) random access.
您可以看到结果与其他人在此处记录的理论性能一致。很清楚 -LinkedList<T>在插入的情况下获得大量时间。我还没有测试从列表中间删除，但结果应该是一样的。当然还有List<T>其他领域表现得更好，比如 O(1) 随机访问。
回答by Tom
A common circumstance to use LinkedList is like this:
使用 LinkedList 的常见情况是这样的：
Suppose you want to remove many certain strings from a list of strings with a large size, say 100,000. The strings to remove can be looked up in HashSet dic, and the list of strings is believed to contain between 30,000 to 60,000 such strings to remove.
假设您想从一个较大的字符串列表中删除许多特定的字符串，比如 100,000。要删除的字符串可以在 HashSet dic 中查找，并且字符串列表被认为包含 30,000 到 60,000 个要删除的此类字符串。
Then what's the best type of List for storing the 100,000 Strings? The answer is LinkedList. If the they are stored in an ArrayList, then iterating over it and removing matched Strings whould take up to billions of operations, while it takes just around 100,000 operations by using an iterator and the remove() method.
那么存储 100,000 个字符串的最佳列表类型是什么？答案是链表。如果它们存储在一个 ArrayList 中，那么迭代它并删除匹配的字符串将需要多达数十亿次操作，而使用迭代器和 remove() 方法只需要大约 100,000 次操作。
LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
String string = iterator.next();
if (dic.contains(string))
iterator.remove();
}
