logo标签列表

为什么LinkedList(T)没有实现IList(T)接口？

c#.net
30
在C#中，LinkedList(T)类没有实现IList(T)接口。然而，List(T)类确实实现了IList(T)接口。为什么会有这种差异？从功能上来说，它们都是列表，所以这个设计选择似乎有些奇怪。现在，从List(T)切换到LinkedList(T)的实现变得困难。
1
LinkedList<T>相比于List<T>，提供更快的插入和删除操作，但同时不提供索引操作。这是LinkedList<T>为了获得更快的插入和删除而做出的一种权衡。同样的，List<T>也在另一个方向上做出了相同的权衡。 - nawfal
11个回答
30

IList<T> 接口包含一个索引器，索引器并不是你在 LinkedList 上期望的功能。

List<T> 可以确保在 O(1) 的时间内访问项目，而根据其结构定义，LinkedList 不能在 O(1) 的时间内提供对项目的访问。

3
谢谢大家的回答。我忽略了 IList 的定义是“表示可以通过索引单独访问的对象集合。”它与我的列表理念不符，但是嘿，这是他们的语言，他们可以选择定义。许多人声称链表不支持索引，然而 Java 语言的链表确实具有索引（他们的文档没有说明其时间效率）。 - Michael Venable
我曾经遇到过这个问题，最终自己编写了一个IndexedLinkedList类（听起来很蠢，但是是最好的选择）。跟踪差异是很有用的。 - NickAldwin
12
请注意，保证在列表中以O(1)时间访问项是实现(List<T>)所做出的承诺，而不是合同(IList<T>)的要求。您的答案是错误的，因为提供索引访问可以通过遍历链表来实现。当然，对于一般情况下这样做效率不高，需要O(N)的时间。 - casperOne
2
索引器不一定要是O(1)，没错，速度越快越好，“通常”情况下，索引器应该能够很快地返回一个值，但是你也可以拥有一个O(n)时间复杂度的索引器... - Natalie Perret
12

阅读链表的定义，您就会理解。

主要问题在于，链表可以包含循环引用，因此没有索引。

链表是最简单和最常见的数据结构之一；它们为几个重要的抽象数据结构（包括栈、队列、关联数组和符号表达式）提供了易于实现的方法。

链表相对于传统数组的主要优点是，链接项的顺序可以与存储在内存或磁盘上的数据项的顺序不同。因此，链表允许在列表中的任何位置插入和删除节点，且仅需进行固定数量的操作。

另一方面，链表本身不允许随机访问数据，也不允许任何形式的高效索引。因此，许多基本操作（例如获取列表的最后一个节点、查找包含给定数据的节点或定位应插入新节点的位置）可能需要扫描大部分列表元素。

我不同意它们是最简单或最常见的数据结构的观点。你自己实现它们很麻烦，还有各种问题需要考虑。而且我几乎从来没有看到它们被实现。另一方面，栈经常被使用，并且非常容易实现。 - Jimmy Hoffa
3
但这并不排除通过索引访问。如果你定义了一个索引器，使得列表中每个连续的“跳跃”操作都会递减索引，那么你就有了一个索引器。虽然效率非常低下，但还是一个索引器。因此，我认为链表上没有实现索引器是为了防止自己被“打脚”，就像不能直接支持IEnumerable<T>一样。 - Kent Boogaart
1
@Kent：用那种方式建立自己的索引，如果存在循环引用，也会变得相当无用。 ;) - Arcturus
@Jimmy Hoffa：栈通常使用链表实现，其中push和pop方法使用FILO实现。 - Wix
@Kent：这是正确的。但如果你没有预料到它，那么很可能很难检测出来，并且性能也会非常糟糕 ;) - Arcturus
显示剩余5条评论
2

LinkedList是一种广为人知的链表数据结构，其具有以下操作复杂度：

Insertion: O(N)

Removal: O(1)

Indexing: O(N)

List（列表）是一个连续的数组，其算法复杂度如下：

Insertion*: O(1)

Removal*: O(N)

Indexing: O(1)

他们不提供常见接口，因为这会误导用户的接口，并使程序效率不可预测。有关更多信息，请查阅有关算法和数据结构的书籍。

是的，@Jason 是正确的，插入是 O(N) - 实际上它是摊销 O(N)。追加是摊销 O(1)。有趣的是，在链表中按索引插入是 O(N)，但在 List 中是摊销 O(N)。 - Jon Hanna
我开始思考，“相同的接口”是否意味着相同的功能和相同的计算复杂度？ - Gqqnbig
谢谢，插入复杂度已修复。 - Grozz
2
这也让我感到惊讶。传统上，列表仅仅是一些元素的有序集合，而链表遵循这个规则，应该实现IList而不是ICollection（集合并不保证元素的顺序）。在我看来，因为某些操作的复杂度比人们预期的要差，就不实现IList是不正确的。
2
接口提供的保证分为三种类型：1. 可编程保证；2. 概念保证。可编程保证是指您可以调用已存在的方法或属性，.NET强制执行此保证。第一种概念保证是它会正常工作，这通常会被打破（NotImplementedException和NotSupportedException存在于此目的），但应有充足的理由。但这更像是一个承诺而非保证。第二种概念保证也更像是一个承诺，即方法或属性将与其他情况类似地工作。人们习惯于IList的索引器在合理的时间内运行 - O(1)或最坏情况下约为O(log n)，打破这个概念上的承诺会导致人们错误地使用您的对象。这里没有具体的规则。您当然可以将IList实现为链接列表，并遭受O(n)索引获取的影响。您还可以以不记录其计数（由框架提供的）并具有O(n)计数属性的方式实现链表。但是，人们更容易使用它错误。组件设计的一部分不仅是确保事物正常工作，而且还要指导它们的使用。实现IList的链接列表在后者方面失败，因此可以有力地主张它不如所提供的设计好。
感谢您详细的回复。我可以一整天都谈论设计。我之前与Java进行了比较，并提到Java链接列表支持索引。看起来关键区别在于.NET中的索引器是一个属性，而属性通常不会执行长时间的计算。Java没有属性，也不遵守它们的约定，因此它们的链接列表索引器可能以O(n)运行。太糟糕了...如果它们共享IList接口，基于哪个实现更有效率，我想切换我的列表实现会更容易。 - Michael Venable
没有什么可以阻止您在支持IList的封装中包含链接列表，但我不赞同，因为我同意它不支持默认值的推理。同样，如果LinkedList确实更有效地完成工作，那么最好不要使用IList完成该工作。 - Jon Hanna
1

LinkedList不是List。List是对象的单维集合。LinkedList是节点集合，更接近于Dictionary。它的需求与常规List不同，更专门为了允许节点遍历和组织行为。

0

历史上的怪事：在 .NET 1.1 中，ArrayList 是类似于动态长度数组的类。

在 .NET 2+ 中，List 在内部组织为数组。这意味着 IList 期望数组语义，实际上。

在 .NET 中，列表 像数组，而不是列表......(boing)

真正的链表具有恒定时间的插入、删除，但枚举较慢并且随机访问更慢。

数组具有快速枚举和随机访问，但插入/删除成本高（O(n) 和重新分配可能会很快导致完全不同的行为）

-1

因为通过索引访问链表的时间复杂度不是O（1）。

-1

链表不是一种旨在通过索引访问的数据结构，然而，IList<T> 提供了索引访问功能。

因此，由于无法通过索引访问链表中的项目，因此不能提供试图执行此操作的方法。

-1
一个“List”在数据结构中并不是指一个链表；实际上它是一个数组--列表项可以直接访问，使用索引器，而这在链表中是不可用的（也不切实际）。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接