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

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

更新成员i-1中的指针以指向新成员

将指针放在新成员中以指向成员i

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

编辑

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

原始答案......

我发现了有趣的结果:

// 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 list = new LinkedList();

        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 list = new List(); // 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 list = new LinkedList();

        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 list = new List();

        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;

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

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

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

结果短:

数组需要使用:

经常这样.它速度快,占用的RAM范围最小,可用于相同数量的信息.

如果你知道所需细胞的确切数量

如果数据保存在数组<85000 b

如果需要高随机访问速度

列表需要使用:

如果需要将单元格添加到列表末尾(通常)

如果需要在列表的开头/中间添加单元格(NOT OFTEN)

如果数据保存在数组<85000 b

如果需要高随机访问速度

LinkedList需要使用:

如果需要在列表的开头/中间/末尾添加单元格(通常)

如果只需要顺序访问(前进/后退)

如果您需要保存大量物品,但物品数量很少.

最好不要使用大量的项目,因为它使用额外的内存链接.

更多细节:

有趣的是:

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

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

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

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

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

希望这有帮助,