何时应使用 List 与 LinkedList

当您需要内置索引访问、排序（以及在此二进制搜索之后）和“ToArray（）”方法时，您应该使用 List。

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

LinkedList<T>只有在访问顺序数据（向前或向后）时才最有效 - 随机访问相对昂贵，因为它每次都必须遍历链（因此它没有索引器）。但是，由于 a 本质上只是一个数组（带有包装器），因此随机访问是可以的。List<T>

List<T>还提供了很多支持方式 - 、 等;但是，这些也可通过扩展方法用于 .NET 3.5/C# 3.0 - 因此这不是一个因素。FindToArrayLinkedList<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 和阵列

希望这有帮助，

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

链表可以是单链接的，也可以是双链接的。这是指链中的每个元素是仅链接到下一个元素（单独链接）还是同时链接到前一个/下一个元素（双重链接）。 是双重联系的。LinkedList<T>

在内部，由数组支持。这在内存中提供了非常紧凑的表示形式。相反，涉及额外的存储器来存储连续元素之间的双向链接。因此，a 的内存占用通常大于 for（需要注意的是，可以有未使用的内部数组元素，以提高追加操作期间的性能。List<T>LinkedList<T>LinkedList<T>List<T>List<T>

它们也具有不同的性能特征：

附加

• 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() 线性时间

正如你所看到的，它们大多是等价的。在实践中，API 的使用更加麻烦，其内部需求的细节会溢出到您的代码中。LinkedList<T>

但是，如果您需要从列表中进行多次插入/删除，它会提供恒定时间。 提供线性时间，因为在插入/删除后必须对列表中的额外项目进行洗牌。List<T>

编辑

请阅读此答案的评论。人们说我没有这样做 适当的测试。我同意这不应该是一个公认的答案。就像我一样 学习我做了一些测试，并想分享它们。

原答案...

我发现了有趣的结果：

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

因此，只有当您计划插入多个项目并且您还在某个地方拥有计划插入项目的位置的参考时，才使用链表。仅仅因为您必须插入大量项目，它并不能使它更快，因为搜索要插入它的位置需要时间。

使用场合LinkedList<>

1. 你不知道有多少物体从闸门进来。例如。Token Stream
2. 当您只想在末尾删除\插入时。

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

与数组相比，链表的主要优点是链接为我们提供了有效地重新排列项目的能力。 塞奇威克，第 91 页

这是根据 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();
        }
    }
}

---

您可以看到结果与此处记录的其他人的理论性能一致。很清楚 - 在插入的情况下获得大量时间。我还没有测试是否从列表中间删除，但结果应该是相同的。当然，还有其他方面，它的表现要好得多，比如 O（1） 随机访问。LinkedList<T>List<T>

使用 LinkedList 的常见情况如下：

假设您要从大尺寸字符串列表中删除许多特定的字符串，例如 100,000。要删除的字符串可以在 HashSet dic 中查找，据信字符串列表包含 30,000 到 60,000 个要删除的字符串。

那么存储 100,000 个字符串的最佳列表类型是什么？答案是 LinkedList。如果它们存储在 ArrayList 中，则遍历它并删除匹配的字符串 whould 会占用 到数十亿次操作，而使用迭代器和 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();
}

我之前的回答不够准确。 这确实是可怕的:D 但现在我可以发布更有用和正确的答案。

---

我做了一些额外的测试。您可以通过以下链接找到它的来源，并自行在您的环境中重新检查它： https://github.com/ukushu/DataStructuresTestsAndOther.git

简短结果：

• 阵列需要使用：

  • 尽可能多地。它速度很快，并且对于相同数量的信息，占用最小的RAM范围。
  • 如果您知道所需细胞的确切计数
  • 如果数据保存在数组中< 85000 b（85000/32 = 整数数据为 2656 个元素）
  • 如果需要高随机存取速度

• 列表需要使用：

  • 如果需要将单元格添加到列表末尾（经常）
  • 如果需要在列表的开头/中间添加单元格（不经常）
  • 如果数据保存在数组中< 85000 b（85000/32 = 整数数据为 2656 个元素）
  • 如果需要高随机存取速度

• LinkedList 需要使用：

  • 如果需要在列表的开头/中间/结尾添加单元格（通常）
  • 如果需要，仅顺序访问（向前/向后）
  • 如果您需要保存 LARGE 项目，但项目计数较低。
  • 最好不要用于大量项目，因为它会为链接使用额外的内存。

更多详情：

有趣的是：

1. LinkedList<T>internally 不是 .NET 中的 List。它甚至没有实现.这就是为什么缺少与索引相关的索引和方法的原因。IList<T>

2. LinkedList<T>是基于节点指针的集合。在 .NET 中，它采用双链接实现。这意味着 prior/next 元素链接到当前元素。而且数据是碎片化的——不同的列表对象可以位于 RAM 的不同位置。此外，用于的内存将多于 for 或 Array。LinkedList<T>List<T>

3. List<T>在 .Net 中是 Java 的替代品。这意味着这是数组包装器。因此，它在内存中作为一个连续的数据块进行分配。如果分配的数据大小超过 85000 字节，则该数据将移动到大型对象堆。根据大小的不同，这可能会导致堆碎片（一种轻微的内存泄漏形式）。但同时，如果大小< 85000 字节，这将在内存中提供非常紧凑和快速访问的表示。ArrayList<T>

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

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

从本质上讲，.NET 中的 a 是数组的包装器。A 是链表。所以问题归结为，数组和链表之间有什么区别，什么时候应该使用数组而不是链表。在您决定使用哪个时，可能最重要的两个因素可以归结为：List<>LinkedList<>

• 链表具有更好的插入/删除性能，只要插入/删除不在集合中的最后一个元素上即可。这是因为数组必须移动插入/删除点之后的所有剩余元素。但是，如果插入/删除位于列表的末尾，则不需要此偏移（尽管如果超出其容量，则可能需要调整阵列的大小）。
• 阵列具有更好的访问能力。数组可以直接索引（在恒定时间内）。必须遍历链表（线性时间）。

我确实同意上面提出的大部分观点。我也同意，在大多数情况下，List看起来是一个更明显的选择。

但是，我只想补充一点，在许多情况下，LinkedList 比 List 更好，效率更高。

1. 假设您正在遍历元素，并且想要执行大量插入/删除操作;LinkedList 在线性 O（n） 时间内完成，而 List 在二次 O（n^2） 时间内完成。
2. 假设您想一次又一次地访问更大的对象，LinkedList 将变得更加有用。
3. 使用 LinkedList 可以更好地实现 Deque（） 和 queue（）。
4. 一旦您处理了许多更大的对象，增加 LinkedList 的大小就会变得更容易和更好。

希望有人会发现这些评论有用。

在 .NET 中，列表表示为数组。因此，与LinkedList相比，使用普通的List会更快，这就是为什么上面的人看到他们看到的结果。

为什么要使用列表？ 我会说这要看情况。如果未指定任何元素，则 List 会创建 4 个元素。当您超过此限制时，它会将内容复制到新数组中，将旧数组留在垃圾回收器手中。然后，它将大小加倍。在本例中，它创建一个包含 8 个元素的新数组。想象一下，有一个包含 100 万个元素的列表，然后你又添加了 1 个元素。它基本上将创建一个全新的数组，其大小是您需要的两倍。新阵列将具有 2Mil 容量，但是，您只需要 1Mil 和 1。本质上是在 GEN2 中为垃圾收集器留下东西，等等。因此，它实际上最终可能成为一个巨大的瓶颈。你应该小心这一点。

除了其他答案之外，我发现在大型数据集和内存分配方面更好。LinkedList<T>

虽然需要连续的空间，但不需要。 当您拥有 GB 大小的数据时，这非常有用。 因为单个 Node 条目可以适合任何有足够空间的地方。 在这种情况下，使用常规或您需要 GB 的连续空间。List<T>LinkedList<T>List<T>T[]

想象一下，您有 2,000,000 个项目： 当您插入其中并且它需要重新分配（因为已满）时，您需要为 4,000,000 个项目提供连续空间（假设增长因子为 2.0 倍）。实际上甚至更多，因为新数组和旧数组需要同时存在才能重新分配。List<T>Capacity

有了 a，项目分散在内存中任何适合它们的地方，添加项目无非是为单个和节点的数据分配内存（+运行时需要的任何其他东西）LinkedList<T>T