什么时候使用List和LinkedList更好?
当前回答
在. net中,列表被表示为数组。因此,与LinkedList相比,使用普通List会更快。这就是为什么上面的人看到他们看到的结果。
Why should you use the List? I would say it depends. List creates 4 elements if you don't have any specified. The moment you exceed this limit, it copies stuff to a new array, leaving the old one in the hands of the garbage collector. It then doubles the size. In this case, it creates a new array with 8 elements. Imagine having a list with 1 million elements, and you add 1 more. It will essentially create a whole new array with double the size you need. The new array would be with 2Mil capacity however, you only needed 1Mil and 1. Essentially leaving stuff behind in GEN2 for the garbage collector and so on. So it can actually end up being a huge bottleneck. You should be careful about that.
其他回答
Edit
请阅读对这个答案的评论。人们说我没有 适当的测试。我同意这不应该是一个可以接受的答案。就像我一样 我做了一些测试,想和大家分享。
最初的回答…
我发现了有趣的结果:
// Temporary class to show the example
class Temp
{
public decimal A, B, C, D;
public Temp(decimal a, decimal b, decimal c, decimal d)
{
A = a; B = b; C = c; D = d;
}
}
链表(3.9秒)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
列表(2.4秒)
List<Temp> list = new List<Temp>(); // 2.4 seconds
for (var i = 0; i < 12345678; i++)
{
var a = new Temp(i, i, i, i);
list.Add(a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
即使你只是访问数据,本质上也要慢得多!!我说永远不要使用linkedList。
下面是另一个执行大量插入的比较(我们计划在列表中间插入一个项)
链表(51秒)
LinkedList<Temp> list = new LinkedList<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
var curNode = list.First;
for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
curNode = curNode.Next;
list.AddAfter(curNode, a); // Insert it after
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
榜单(7.26秒)
List<Temp> list = new List<Temp>();
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.Insert(i / 2, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
有插入位置引用的链表(。04秒)
list.AddLast(new Temp(1,1,1,1));
var referenceNode = list.First;
for (var i = 0; i < 123456; i++)
{
var a = new Temp(i, i, i, i);
list.AddLast(a);
list.AddBefore(referenceNode, a);
}
decimal sum = 0;
foreach (var item in list)
sum += item.A;
因此,只有当你计划插入几个项目,并且你也在某个地方有你计划插入项目的引用时,才使用链表。只是因为你必须插入很多项,这并不会使它更快,因为搜索你想要插入的位置需要时间。
本质上,. net中的List<>是数组的包装器。LinkedList<>是一个链表。所以问题归结为,数组和链表之间的区别是什么,以及什么时候应该使用数组而不是链表。可能在你决定使用哪个时最重要的两个因素可以归结为:
Linked lists have much better insertion/removal performance, so long as the insertions/removals are not on the last element in the collection. This is because an array must shift all remaining elements that come after the insertion/removal point. If the insertion/removal is at the tail end of the list however, this shift is not needed (although the array may need to be resized, if its capacity is exceeded). Arrays have much better accessing capabilities. Arrays can be indexed into directly (in constant time). Linked lists must be traversed (linear time).
链表提供了快速插入或删除列表成员的功能。链表中的每个成员都包含指向链表中下一个成员的指针,因此要在位置i插入一个成员:
更新成员i-1中的指针,使其指向新成员 将新成员中的指针设置为指向成员I
链表的缺点是不能进行随机访问。访问成员需要遍历列表,直到找到所需的成员。
List和LinkedList之间的区别在于它们的底层实现。List是基于数组的集合(ArrayList)。LinkedList是基于节点指针的集合(LinkedListNode)。在API级别的使用上,它们几乎是相同的,因为它们都实现了相同的接口集,如ICollection、IEnumerable等。
关键的区别在于性能问题。例如,如果您正在实现具有大量“INSERT”操作的列表,LinkedList的性能优于list。因为LinkedList可以在O(1)时间内完成,但是List可能需要扩展底层数组的大小。要了解更多信息/细节,你可能想要阅读LinkedList和数组数据结构之间的算法差异。http://en.wikipedia.org/wiki/Linked_list和Array
希望这能有所帮助,
我同意上面提到的大部分观点。我也同意,在大多数情况下,List看起来是一个更明显的选择。
但是,我只是想补充一点,在很多情况下,LinkedList比List更有效。
假设你正在遍历元素,你想要执行大量的插入/删除;LinkedList在线性O(n)时间内完成,而List在二次O(n²)时间内完成。 假设你想一次又一次地访问更大的对象,LinkedList就变得非常有用。 Deque()和queue()更好地使用LinkedList实现。 当你处理很多更大的对象时,增加LinkedList的大小会更容易和更好。
希望有人会觉得这些评论有用。
推荐文章
- 防止在ASP中缓存。NET MVC中使用属性的特定操作
- 转换为值类型'Int32'失败,因为物化值为空
- c#中有任何连接字符串解析器吗?
- 多维数组如何在内存中格式化?
- 在Linq中转换int到字符串到实体的问题
- 是否可以动态编译和执行c#代码片段?
- 创建自定义MSBuild任务时,如何从c#代码获取当前项目目录?
- MSBuild路径
- c#和Java的主要区别是什么?
- 在c#中创建一个特定时区的DateTime
- .NET中的属性是什么?
- csproj文件中的“Service Include”是干什么用的?
- 如何使用try catch进行异常处理是最佳实践
- 替换字符串中第一次出现的模式
- .NET中字节的字面后缀?