什么时候使用List和LinkedList更好?
当前回答
我之前的回答不够准确。 D是正确答案 但现在我可以发布更有用和正确的答案。
我做了一些额外的检查您可以通过以下链接找到它的源代码,并在您自己的环境中通过https://github.com/ukushu/DataStructuresTestsAndOther.git重新检查它
短的结果:
Array need to use: So often as possible. It's fast and takes smallest RAM range for same amount information. If you know exact count of cells needed If data saved in array < 85000 b (85000/32 = 2656 elements for integer data) If needed high Random Access speed List need to use: If needed to add cells to the end of list (often) If needed to add cells in the beginning/middle of the list (NOT OFTEN) If data saved in array < 85000 b (85000/32 = 2656 elements for integer data) If needed high Random Access speed LinkedList need to use: If needed to add cells in the beginning/middle/end of the list (often) If needed only sequential access (forward/backward) If you need to save LARGE items, but items count is low. Better do not use for large amount of items, as it's use additional memory for links.
更多的细节:
有趣的是:
LinkedList<T> internally is not a List in .NET. It's even does not implement IList<T>. And that's why there are absent indexes and methods related to indexes. LinkedList<T> is node-pointer based collection. In .NET it's in doubly linked implementation. This means that prior/next elements have link to current element. And data is fragmented -- different list objects can be located in different places of RAM. Also there will be more memory used for LinkedList<T> than for List<T> or Array. List<T> in .Net is Java's alternative of ArrayList<T>. This means that this is array wrapper. So it's allocated in memory as one contiguous block of data. If allocated data size exceeds 85000 bytes, it will be moved to Large Object Heap. Depending on the size, this can lead to heap fragmentation(a mild form of memory leak). But in the same time if size < 85000 bytes -- this provides a very compact and fast-access representation in memory. Single contiguous block is preferred for random access performance and memory consumption but for collections that need to change size regularly a structure such as an Array generally need to be copied to a new location whereas a linked list only needs to manage the memory for the newly inserted/deleted nodes.
其他回答
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中,LinkedList<T>甚至没有实现IList<T>。在链表中没有真正的索引概念,即使看起来有。当然,类中提供的方法都不接受索引。
链表可以是单链,也可以是双链。这是指链中的每个元素是否只与下一个元素有链接(单链),还是与前一个/下一个元素都有链接(双链)。LinkedList<T>是双重链接。
在内部,List<T>由一个数组支持。这在内存中提供了一个非常紧凑的表示。相反,LinkedList<T>涉及额外的内存来存储连续元素之间的双向链接。因此LinkedList<T>的内存占用通常会比List<T>的内存占用大(需要注意的是,List<T>可以有未使用的内部数组元素,以提高追加操作期间的性能)。
它们也有不同的表现特征:
附加
LinkedList<T>.AddLast(item)常量时间 List<T>.Add(item)平摊常数时间,线性最坏情况
预谋
LinkedList<T>.AddFirst(item)常量时间 列表> < T。插入(0,项)线性时间
插入
LinkedList < T >。AddBefore(节点,项目)常量时间 LinkedList < T >。AddAfter(节点,项目)常量时间 列表> < T。插入(索引、项)线性时间
删除
删除(项目)线性时间 删除(节点)常量时间 列表<T>.删除(项目)线性时间 List<T>.RemoveAt(index)线性时间
数
LinkedList < T >。计算常数时间 列表> < T。计算常数时间
包含
包含(项目)线性时间 列表<T>.包含(项)线性时间
清晰的
LinkedList<T>.Clear()线性时间 List<T>.Clear()线性时间
如你所见,它们基本上是相等的。实际上,LinkedList<T>的API使用起来更麻烦,其内部需求的细节会泄漏到代码中。
然而,如果你需要在一个列表中做很多插入/删除,它提供了常数时间。List<T>提供线性时间,因为列表中的额外项必须在插入/删除之后重新排列。
使用LinkedList<>时
你不知道有多少东西会通过防洪闸门。例如,令牌流。 当你只想在结尾删除\插入。
对于其他内容,最好使用List<>。
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
希望这能有所帮助,
链表提供了快速插入或删除列表成员的功能。链表中的每个成员都包含指向链表中下一个成员的指针,因此要在位置i插入一个成员:
更新成员i-1中的指针,使其指向新成员 将新成员中的指针设置为指向成员I
链表的缺点是不能进行随机访问。访问成员需要遍历列表,直到找到所需的成员。
推荐文章
- 防止在ASP中缓存。NET MVC中使用属性的特定操作
- 转换为值类型'Int32'失败,因为物化值为空
- c#中有任何连接字符串解析器吗?
- 多维数组如何在内存中格式化?
- 在Linq中转换int到字符串到实体的问题
- 是否可以动态编译和执行c#代码片段?
- 创建自定义MSBuild任务时,如何从c#代码获取当前项目目录?
- MSBuild路径
- c#和Java的主要区别是什么?
- 在c#中创建一个特定时区的DateTime
- .NET中的属性是什么?
- csproj文件中的“Service Include”是干什么用的?
- 如何使用try catch进行异常处理是最佳实践
- 替换字符串中第一次出现的模式
- .NET中字节的字面后缀?