<分区>
Possible Duplicate:
When should I use a List vs a LinkedList
这个问题与我之前合并的问题相关:与List vs LinkedList相关
如果我不希望对我的数据结构使用按索引访问，那么通过使用 LinkedList 而不是 List 可以节省多少？如果不是 100% 确定我永远不会使用索引访问，我想知道其中的区别。
假设我有 N 个实例。在 LinkedList 中插入和删除只会是一个 o(1) op，而在 List 中它可能是 O(n)，但由于它经过优化，所以很高兴知道某些 n 值的区别是什么。假设 N = 1,000,000 和 N = 1,000,000,000
最佳答案
好的，我做了这个实验，结果如下:
这是包含 1000,000 个项目的列表和链表的耗时:
LinkedList 500 insert/remove operations: 10171
List 500 insert/remove operations: 968465
与 1000,000 个项目相比，链表快 100 倍。
代码如下:
static void Main(string[] args)
{
const int N = 1000*1000;
Random r = new Random();
LinkedList<int> linkedList = new LinkedList<int>();
List<int> list = new List<int>();
List<LinkedListNode<int>> linkedListNodes = new List<LinkedListNode<int>>();
for (int i = 0; i < N; i++)
{
list.Add(r.Next());
LinkedListNode<int> linkedListNode = linkedList.AddFirst(r.Next());
if(r.Next() % 997 == 0)
linkedListNodes.Add(linkedListNode);
}
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 500; i++)
{
linkedList.AddBefore(linkedListNodes[i], r.Next());
linkedList.Remove(linkedListNodes[i]);
}
stopwatch.Stop();
Console.WriteLine("LinkedList 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < 500; i++)
{
list.Insert(r.Next(0,list.Count), r.Next());
list.RemoveAt(r.Next(0, list.Count));
}
stopwatch.Stop();
Console.WriteLine("List 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
Console.Read();
}
}
关于c# - 在 (c#) 库中使用 List<T> 与 LinkedList<T> 的性能差异是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5880851/