什么时候使用List和LinkedList更好?
当前回答
我问了一个类似的关于LinkedList集合性能的问题,发现Steven Cleary的Deque c#实现是一个解决方案。与Queue集合不同,Deque允许前后移动项目。它类似于链表,但性能有所改进。
其他回答
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
希望这能有所帮助,
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;
因此,只有当你计划插入几个项目,并且你也在某个地方有你计划插入项目的引用时,才使用链表。只是因为你必须插入很多项,这并不会使它更快,因为搜索你想要插入的位置需要时间。
我同意上面提到的大部分观点。我也同意,在大多数情况下,List看起来是一个更明显的选择。
但是,我只是想补充一点,在很多情况下,LinkedList比List更有效。
假设你正在遍历元素,你想要执行大量的插入/删除;LinkedList在线性O(n)时间内完成,而List在二次O(n²)时间内完成。 假设你想一次又一次地访问更大的对象,LinkedList就变得非常有用。 Deque()和queue()更好地使用LinkedList实现。 当你处理很多更大的对象时,增加LinkedList的大小会更容易和更好。
希望有人会觉得这些评论有用。
在大多数情况下,List<T>更有用。LinkedList<T>在列表中间添加/删除项时成本更低,而list <T>只能在列表末尾添加/删除项。
LinkedList<T>只有在访问顺序数据(向前或向后)时才最有效-随机访问相对昂贵,因为它每次都必须遍历链(因此它没有索引器)。但是,因为List<T>本质上只是一个数组(带有包装器),所以随机访问是可以的。
List<T>还提供了很多支持方法- Find, ToArray等;然而,这些也可以通过扩展方法用于。net 3.5/ c# 3.0的LinkedList<T> -所以这不是一个因素。
链表相对于数组的主要优点是,链接为我们提供了有效地重新排列项的能力。 塞奇威克,第91页
推荐文章
- 实体框架核心:在上一个操作完成之前,在此上下文中开始的第二个操作
- 如何为构造函数定制Visual Studio的私有字段生成快捷方式?
- 为什么Visual Studio 2015/2017/2019测试运行器没有发现我的xUnit v2测试
- 如何使用JSON确保字符串是有效的JSON。网
- AppSettings从.config文件中获取值
- 通过HttpClient向REST API发布一个空体
- 如何检查IEnumerable是否为空或空?
- 自动化invokerrequired代码模式
- 没有ListBox。SelectionMode="None",是否有其他方法禁用列表框中的选择?
- 在c#代码中设置WPF文本框的背景颜色
- 在c#中,什么是单子?
- c#和Java中的泛型有什么不同?和模板在c++ ?
- c#线程安全快速(est)计数器
- HyperLogLog算法是如何工作的?
- 如何将此foreach代码转换为Parallel.ForEach?