什么时候在数组/数组列表上使用链表?

我使用了很多列表和数组，但我还没有遇到一个场景，数组列表不能像链表一样容易使用，如果不是更容易的话。我希望有人能给我一些例子，说明什么时候链表明显更好。

当前回答

我做了一些基准测试，发现list类实际上比LinkedList随机插入更快:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

链表需要900毫秒，列表类需要100毫秒。

它创建后续整数的列表。每个新的整数被插入到一个已经在列表中的随机数之后。也许List类使用了比数组更好的东西。

2016-05-08 13:33:08

其他回答

如果您需要在中间插入项，并且不想开始调整数组大小和移动内容，则列表的优势就会显现出来。

你是对的，通常情况下并非如此。我遇到过一些非常具体的案例，但不是很多。

2008-12-26 07:07:49

我认为主要的区别在于你是否经常需要从列表顶部插入或删除内容。

对于一个数组，如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。

对于链表，它是o(1)，因为您只需要创建节点，重新分配头，并将对next的引用分配为前一个头。

当经常在列表的末尾插入或删除时，数组是更可取的，因为复杂度将是o(1)，不需要重新索引，但对于链表，它将是o(n)，因为你需要从头到最后一个节点。

我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。