LinkedList与List< T> [英] LinkedList vs List<T>

问题描述

可能重复:
何时应使用列表与链接列表

如果我不希望对数据结构使用按索引访问，那么我可以节省多少费用LinkedList超过列表?如果不是100％确定我永远不会使用索引访问，我想知道两者之间的区别.

If I expect not to use the access by index for my data structure how much do I save by using LinkedList over List ? If if am not 100% sure I will never use access by index, I would like to know the difference.

假设我有N个实例.在LinkedList中插入和删除只会是o(1)op，而在List中，我可能是O(n)，但是由于它已优化，所以很高兴知道n的某些值之间的区别.说N = 1,000,000和N = 1,000,000,000

Suppose I have N instances. inserting and removing in a LinkedList will only be a o(1) op , where as in List it may me be O(n), but since it it optimized, it would be nice to know what the difference is for some values of n. say N = 1,000,000 and N = 1,000,000,000

推荐答案

List 只是一个数组的包装器. LinkedList< T> 仅在访问顺序数据(正向或反向)时才最有效.

List<T> is just a wrapper over an Array. LinkedList<T> is only at it's most efficient if you are accessing sequential data (either forwards or backwards).

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

Linked lists provide very fast insertion or deletion of a list member. Each member in a linked list contains a pointer to the next member in the list so to insert a member at position 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

检查以下内容:何时应该使用列表与LinkedList

这篇关于LinkedList与List< T>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！