我什么时候应该使用List vs LinkedList

Question

什么时候使用List vs LinkedList更好？

Answer 1

在大多数情况下,List<T>更有用.LinkedList<T>在列表中间添加/删除项目时会有更少的成本,而List<T>只能在列表末尾便宜地添加/删除.

LinkedList<T>如果您正在访问顺序数据(向前或向后),那么它的效率最高 - 随机访问相对昂贵,因为它每次都必须走链(因此它没有索引器).但是,因为a List<T>本质上只是一个数组(带有包装器),随机访问就可以了.

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

Answer 2

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

链接列表可以单独链接,也可以双重链接.这指的是链中的每个元素是否仅与下一个元素(单链接)或前一个/下一个元素(双重链接)都有链接. LinkedList<T>是双重联系的.

在内部,List<T>由数组支持.这在内存中提供了非常紧凑的表示.相反,LinkedList<T>涉及额外的存储器以存储连续元素之间的双向链接.因此,a的内存占用量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>提供线性时间,因为列表中的额外项目必须在插入/移除后随机移动.

Answer 3

链接列表可以非常快速地插入或删除列表成员.链表中的每个成员都包含指向列表中下一个成员的指针,以便在位置i处插入成员:

• 更新成员i-1中的指针以指向新成员
• 将指针放在新成员中以指向成员i

链表的缺点是随机访问是不可能的.访问成员需要遍历列表,直到找到所需的成员.

Answer 4

编辑

请阅读此答案的评论.人们声称我没有做适当的测试.我同意这不应该是一个公认的答案.在我学习的过程中,我做了一些测试,感觉就像分享它们一样.

原始答案......

我发现了有趣的结果:

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

因此,只有当您计划插入多个项目时,您还可以在某个地方引用计划插入项目的位置,然后使用链接列表.仅仅因为你必须插入很多项目它不会使它更快,因为搜索你想要插入它的位置需要时间.

Answer 5

我之前的回答不够准确.真的很可怕:D但现在我可以发布更有用和正确的答案.

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

结果短:

• 数组需要使用:

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

• 列表需要使用:

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

• LinkedList需要使用:

  • 如果需要在列表的开头/中间/末尾添加单元格(通常)
  • 如果只需要顺序访问(前进/后退)
  • 如果您需要保存大量物品,但物品数量很少.
  • 最好不要使用大量的项目,因为它使用额外的内存链接.

更多细节:

有趣的是:

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

2. LinkedList<T>是基于节点指针的集合.在.NET中,它是双重链接的实现.这意味着先前/下一个元素具有到当前元素的链接.并且数据是碎片化的 - 不同的列表对象可以位于RAM的不同位置.此外,将使用LinkedList<T>比用于List<T>或数组更多的内存.

3. List<T>在.Net是Java的替代品ArrayList<T>.这意味着这是数组包装器.因此它在内存中被分配为一个连续的数据块.如果分配的数据大小超过85000字节,它将被移动到大对象堆.根据大小,这可能导致堆碎片(一种温和的内存泄漏形式).但是在同一时间,如果大小<85000字节 - 这在内存中提供了非常紧凑和快速访问的表示.

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

Answer 6

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

希望这有帮助,

Answer 7

链接列表相对于数组的主要优点是链接为我们提供了有效重新排列项目的功能.塞奇威克,p.91