可能重复：
我什么时候应该使用List与LinkedList
这个问题与我之前合并的问题有关：与List vs LinkedList 有关
如果我希望不对我的数据结构使用按索引访问，那么在列表上使用LinkedList可以节省多少？如果我不能100%确定我永远不会使用按索引访问，我想知道其中的区别。
假设我有N个实例。在LinkedList中插入和删除只会是一个o(1(op，其中与List中一样，它可能是o(n(，但由于它是优化的，所以最好知道n的某些值的差异，比如n=1000000和n=1000000000
好的，我做了这个实验，结果是：
这是包含1000000个项目的列表和链接列表的经过时间：
LinkedList 500 insert/remove operations: 10171
List 500 insert/remove operations: 968465
与1000000个项目相比，链表的速度快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();
}
}
不用担心。像往常一样编写应用程序。完成后，使用真实数据运行它几次，并评测性能。换出你正在使用的类并比较结果。
List在内部使用一个数组，它总是有一个固定的大小，例如它使用的大小是16(通常是2的幂(，所以即使您存储了一个项目，它也会保存大小为16的数组，其中15为空。
现在假设，当您存储所有16个项目，并尝试添加第17个项目时，它现在将创建一个32的新数组，(16+16(，将所有16个从旧数组复制到新数组，然后将项目放在32大小数组的第17位。
现在，当你从第一位移除一个项目时，第一个项目之后的所有项目都会向前移动一步，所以第二个变成第一个，第三个变成第二个等等。
"链表"是由指针组成的，它不是数组，它只占用您创建的节点，并存储上一个和下一个节点的引用。
对于性能问题，如果您很少添加/删除项目，但会非常频繁地迭代(读取整个列表或通过索引访问项目(，那么List将非常有效。列表将更好地用于随机访问场景，比如您将能够在指定索引的情况下非常快速地获取项目。
如果您要非常频繁地添加/删除项目，则链表将非常有效，但很少迭代它(整个列表(。链表将更适合顺序访问，在顺序访问中，您将从当前节点向后或向前导航，但当您尝试查找索引项时，它的性能将非常差。
在List<T>中的反向插入实际上在摊销的恒定时间内运行。然而，去除元件是昂贵的(O(n)(。