链接列表与列表<T>

Question

可能重复：
我什么时候应该使用List与LinkedList

如果我希望不对我的数据结构使用按索引访问，那么使用列表之上的LinkedList？如果我不能100%确定我永远不会使用按索引访问，我想知道其中的区别。

假设我有N个实例。在LinkedList中插入和删除只会是一个o(1(op，其中与List中一样，它可能是o(n(，但由于它是优化的，所以最好知道n的某些值有什么不同。例如N=1000000和N=1000000000

Answer 1

List<T>只是一个数组的包装器。LinkedList<T>只有在访问顺序数据(向前或向后(时才是最有效的。

链接列表提供了对列表成员的快速插入或删除。链接列表中的每个成员都包含一个指向列表中下一个成员的指针，以便在i:位置插入一个成员

update the pointer in member i-1 to point to the new member
set the pointer in the new member to point to member i

检查一下：我什么时候应该使用List与LinkedList

Answer 2

LinkedList<T>在对列表中的项目执行多次随机插入和删除时非常有用。否则，List<T>可能是最好的选择，因为它不携带链接列表中元素的开销(也可以进行索引(。

但是，如果您关心性能，那么您确实需要测试实际的代码。