我使用了很多列表和数组，但我还没有遇到一个场景，数组列表不能像链表一样容易使用，如果不是更容易的话。我希望有人能给我一些例子，说明什么时候链表明显更好。
当前回答
我做了一些基准测试，发现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类使用了比数组更好的东西。
其他回答
这个问题的简单答案可以用以下几点来给出:
当需要类似类型的数据元素集合时，将使用数组。而链表是混合类型数据链接元素(称为节点)的集合。 在数组中，可以在O(1)时间内访问任何元素。然而，在链表中，我们需要遍历整个链表，从头到所需的节点，花费O(n)时间。 对于数组，需要在初始时声明特定的大小。但是链表的大小是动态的。
如果您需要在中间插入项，并且不想开始调整数组大小和移动内容，则列表的优势就会显现出来。
你是对的，通常情况下并非如此。我遇到过一些非常具体的案例，但不是很多。
数组具有O(1)随机访问，但是向数组中添加或删除内容的代价非常高。
链表在任何地方添加或删除项目和迭代都非常便宜，但随机访问是O(n)。
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
数组列表适用于写一次读多次或追加程序，但不适用于从前面或中间进行添加/删除。
我做了一些基准测试，发现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类使用了比数组更好的东西。
