什么时候应该使用列表与LinkedList

什么时候使用List(Of T) vs LinkedList(Of T)更好？

Answer 1

编辑

请阅读这个答案的意见。 人们声称我没有做适当的testing。 我同意这不应该是一个被接受的答案。 正如我在学习，我做了一些testing，感觉像分享他们。

原始答案…

我发现有趣的结果：

 // 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; 

即使你只访问数据本质上是慢得多！ 我说永远不要使用linkedList。

---

---

---

这里是另一个比较，执行大量的插入（我们计划在列表中间插入一个项目）

链接列表（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; 

所以只有当你计划插入几个项目，你也有一个地方有你打算插入项目，然后使用链接列表的参考。 仅仅因为你必须插入很多项目，所以它不会让它变得更快，因为search你想插入的位置需要花费一些时间。

Answer 2

在大多数情况下， List<T>更有用。 当添加/删除列表中的项目时， LinkedList<T>成本较低，而List<T>只能在列表的末尾添加/删除。

如果你正在访问顺序数据（向前或向后）， LinkedList<T>只是最有效的 – 随机访问相对比较昂贵，因为每次都必须遍历链（因此为什么没有索引器）。 但是，因为一个List<T>本质上只是一个数组（包装），所以随机访问是可以的。

List<T>也提供了很多支持方法 – Find ， ToArray等; 但是，这些也可以通过扩展方法用于.NET 3.5 / C＃3.0的LinkedList<T> – 所以这不是一个因素。

Answer 3

把链表看作一个列表可能有点误导。 这更像一个链条。 事实上，在.NET中， LinkedList<T>甚至不实现IList<T> 。 在链表中没有真正的索引概念，即使它看起来可能也是如此。 当然，这个类提供的方法都不接受索引。

链接列表可以单独链接，也可以双重链接。 这是指链中的每个元素是否仅与下一个链接（单链接）或与之前/下一个链接（双链接）的链接。 LinkedList<T>是双重链接的。

在内部， List<T>由数组支持。 这在内存中提供了非常紧凑的表示forms。 相反， LinkedList<T>包含额外的内存来存储连续元素之间的双向链接。 因此， LinkedList<T>的内存占用量通常会大于List<T> （注意List<T>可以使用未使用的内部数组元素来提高追加操作期间的性能）。

他们也有不同的performance特征：

附加

• LinkedList<T>.AddLast(item) 常量时间
• List<T>.Add(item) 摊销常量时间，线性最坏情况

前置

• LinkedList<T>.AddFirst(item) 常量时间
• List<T>.Insert(0, item) 线性时间

插入

• LinkedList<T>.AddBefore(node, item) 常量时间
• LinkedList<T>.AddAfter(node, item) 常量时间
• List<T>.Insert(index, item) 线性时间

切除

• LinkedList<T>.Remove(item) 线性时间
• LinkedList<T>.Remove(node) 常量时间
• List<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>提供线性时间，因为在插入/移除之后，列表中的额外项目必须被混洗。

Answer 4

链接列表提供非常快的插入或删除列表成员。 链表中的每个成员都包含一个指向列表中下一个成员的指针，以便在位置i处插入成员：

• 更新成员i-1中的指针指向新成员
• 将新成员中的指针设置为指向成员i

链表的缺点是随机访问是不可能的。 访问成员需要遍历列表，直到find所需的成员。

Answer 5

List和LinkedList的区别在于它们的底层实现。 List是基于数组的数组（ArrayList）。 LinkedList是基于节点指针的集合（LinkedListNode）。 在API级别的用法上，它们都是相同的，因为它们都实现了相同的一组接口，比如ICollection，IEnumerable等等。

性能至关重要。 例如，如果您正在实施具有繁重“INSERT”操作的列表，则LinkedList优于List。 由于LinkedList可以在O（1）时间内完成，但是List可能需要扩展底层数组的大小。 有关更多信息/详细信息，您可能需要了解LinkedList和数组数据结构之间的algorithm差异。 http://en.wikipedia.org/wiki/Linked_list和Array

希望这个帮助，

Answer 6

链接列表在数组上的主要优点是链接为我们提供了重新排列项目的能力。 Sedgewick，p。 91

Answer 7

我以前的答案是不够准确的。 真是太可怕了：D但现在我可以发表更多有用和正确的答案。

---

我做了一些额外的testing。 你可以通过下面的链接find它的源代码，并通过你自己的环境重新检查它： https : //github.com/ukushu/DataStructuresTestsAndOther.git

简短的结果：

• arrays需要使用：

  • 尽可能经常。 它的速度很快，同样数量的信息占用最小的RAM范围。
  • 如果你知道所需细胞的确切数量
  • 如果数据保存在<85000 b
  • 如果需要高随机访问速度

• 列表需要使用：

  • 如果需要将单元格添加到列表的末尾（通常）
  • 如果需要在列表的开头/中间添加单元格（NOT OFTEN）
  • 如果数据保存在<85000 b
  • 如果需要高随机访问速度

• LinkedList需要使用：

  • 如果需要在列表的开始/中间/结尾添加单元格（经常）
  • 如果只需要顺序访问（前进/后退）
  • 如果您需要保存大件物品，但物品数量很less。
  • 最好不要使用大量的项目，因为它使用额外的链接内存。

更多细节：

有趣的知道：

1. 链接列表内部不是.NET中的列表。 LinkedList<T> 。 甚至没有实现IList<T> 。 这就是为什么没有与索引相关的索引和方法。

2. LinkedList<T>是基于节点指针的集合。 在.NET中它是双重链接的实现。 这意味着先前/下一个元素链接到当前元素。 数据被分割 – 不同的列表对象可以位于RAM的不同位置。 此外，用于LinkedList<T>内存将比List<T>或Array多。

3. .Net中的List<T>是Java的替代ArraList<T> 。 这意味着这是数组包装。 所以它作为一个连续的数据块被分配在menory中。 如果分配的数据大小超过85000字节，则将分配给大对象堆。 根据大小，这可能导致堆碎片，一个温和的内存泄漏forms。 但是，如果大小<85000字节，则在内存中提供了非常紧凑且快速的访问表示。

4. 单个连续块是随机访问性能和内存消耗的首选，但对于需要定期更改大小的集合，通常需要将诸如Array之类的结构复制到新位置，而链接列表只需要pipe理新插入的内存/已删除的节点。

Answer 8

使用LinkedList常见的情况是这样的：

假设你想从一个大尺寸的string列表中删除许多特定的string，比如100,000。 可以在HashSet dic中查找要移除的string，并且相信string列表包含要移除的3万到6万个这样的string。

那么存储100,000个string的最佳列表是什么？ 答案是LinkedList。 如果它们被存储在一个ArrayList中，那么遍历它并删除匹配的Strings就会花费数十亿次操作，而使用迭代器和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(); } 

Answer 9

当你需要内置的索引访问，sorting（在这个二进制search之后）和“ToArray（）”方法时，你应该使用List。

Answer 10

这是根据Tono Nam接受的答案修正了一些错误的测量。

考试：

 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(); } } } 

---

你可以看到结果与其他人在这里logging的理论performance一致。 非常清楚 – LinkedList<T>在插入的情况下获得了大量的时间。 我还没有从列表中间进行testing，但结果应该是一样的。 当然， List<T>还有其他方面比O（1）随机访问更好。

Answer 11

使用LinkedList<>时

1. 你不知道有多less物体通过防洪门。 例如， Token Stream 。
2. 当你只想删除\插入在两端。

对于其他一切，最好使用List<> 。

Answer 12

这么多的平均答案在这里…

一些链表实现使用预分配节点的底层块。 如果他们不这样做，那么恒定的时间/线性时间就不那么重要了，因为内存性能会差，caching性能更差。

使用链接列表时

1）你想要线程安全。 你可以build立更好的线程安全algorithm。 locking成本将占据并发风格列表。

2）如果你有一个像结构一样的大队列，并且想要删除或添加任何地方，但是一直到最后。 > 100K列表存在，但不常见。

Answer 13

我问了一个与LinkedList集合的性能有关的类似问题 ，发现了Steven Cleary的Deque的C＃实现是一个解决scheme。 与队列集合不同，Deque允许将项目前后移动。 它与链表相似，但性能有所提高。