什么时候使用List和LinkedList更好?


当前回答

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

其他回答

本质上,. net中的List<>是数组的包装器。LinkedList<>是一个链表。所以问题归结为,数组和链表之间的区别是什么,以及什么时候应该使用数组而不是链表。可能在你决定使用哪个时最重要的两个因素可以归结为:

Linked lists have much better insertion/removal performance, so long as the insertions/removals are not on the last element in the collection. This is because an array must shift all remaining elements that come after the insertion/removal point. If the insertion/removal is at the tail end of the list however, this shift is not needed (although the array may need to be resized, if its capacity is exceeded). Arrays have much better accessing capabilities. Arrays can be indexed into directly (in constant time). Linked lists must be traversed (linear time).

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

Edit

请阅读对这个答案的评论。人们说我没有 适当的测试。我同意这不应该是一个可以接受的答案。就像我一样 我做了一些测试,想和大家分享。

最初的回答…

我发现了有趣的结果:

// 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的常见情况是这样的:

假设您想要从一个字符串列表中删除许多特定的字符串,这些字符串的大小很大,比如100,000。要删除的字符串可以在HashSet dic中查找,字符串列表中应该包含30,000到60,000个这样的需要删除的字符串。

那么用于存储100,000个字符串的列表的最佳类型是什么?答案是LinkedList。如果它们存储在数组列表中,则遍历它并删除匹配的字符串将占用 到数十亿次操作,而使用迭代器和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重新检查它

短的结果:

Array need to use: So often as possible. It's fast and takes smallest RAM range for same amount information. If you know exact count of cells needed If data saved in array < 85000 b (85000/32 = 2656 elements for integer data) If needed high Random Access speed List need to use: If needed to add cells to the end of list (often) If needed to add cells in the beginning/middle of the list (NOT OFTEN) If data saved in array < 85000 b (85000/32 = 2656 elements for integer data) If needed high Random Access speed LinkedList need to use: If needed to add cells in the beginning/middle/end of the list (often) If needed only sequential access (forward/backward) If you need to save LARGE items, but items count is low. Better do not use for large amount of items, as it's use additional memory for links.

更多的细节:

有趣的是:

LinkedList<T> internally is not a List in .NET. It's even does not implement IList<T>. And that's why there are absent indexes and methods related to indexes. LinkedList<T> is node-pointer based collection. In .NET it's in doubly linked implementation. This means that prior/next elements have link to current element. And data is fragmented -- different list objects can be located in different places of RAM. Also there will be more memory used for LinkedList<T> than for List<T> or Array. List<T> in .Net is Java's alternative of ArrayList<T>. This means that this is array wrapper. So it's allocated in memory as one contiguous block of data. If allocated data size exceeds 85000 bytes, it will be moved to Large Object Heap. Depending on the size, this can lead to heap fragmentation(a mild form of memory leak). But in the same time if size < 85000 bytes -- this provides a very compact and fast-access representation in memory. Single contiguous block is preferred for random access performance and memory consumption but for collections that need to change size regularly a structure such as an Array generally need to be copied to a new location whereas a linked list only needs to manage the memory for the newly inserted/deleted nodes.