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

Question

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

在C#中,LinkedList(T)类不实现IList(T)接口.但是,List(T)类确实实现了IList(T).为什么会出现这种差异？从功能上讲,它们都是列表,所以这个设计选择看起来很奇怪.现在很难将实现从List(T)切换到LinkedList(T).

Answer 1

Eli*_*sha 27

IList<T>interface包含一个索引器,索引器不是你期望的功能LinkedList.

List<T>可以确保访问O(1)中的项目,LinkedList根据它的定义,它的结构不能提供对O(1)中项目的访问.

请注意[确保在O(1)时间内访问列表中的项目是*实现*(`List <T>`)所做的承诺](http://msdn.microsoft.com/en-us /library/0ebtbkkc.aspx),[*不**合约的要求*(`IList <T>`)](http://msdn.microsoft.com/en-us/library/ewthkb10.aspx).您的答案是错误的,因为提供索引访问*可以通过遍历链表完成.当然,这样做对于一般情况来说效率不高,花费O(N)时间. (7认同)
谢谢大家的回答.我忽略了IList的定义是"表示可以通过索引单独访问的对象集合".它与我对列表的想法不符,但是,嘿,这是他们的语言,他们可以选择定义.许多人声称链表不支持索引,但Java语言的链表确实有索引(他们的文档没有对它的时间效率提出任何要求). (3认同)
索引器不必一定是O（1），是的，速度越快越好，通常情况下，索引器会很快返回值，但是没有什么可以阻止您使用O（n）时间... (2认同)

Answer 2

Arc*_*rus 12

查看链接列表的定义,您将理解.

主要问题,LinkedLists可以包含循环引用,因此没有索引.

链表是最简单和最常见的数据结构之一; 它们为几个重要的抽象数据结构提供了简单的实现,包括堆栈,队列,关联数组和符号表达式.

链接列表相对于传统阵列的主要好处是链接项的顺序可能与数据项存储在内存或磁盘上的顺序不同.因此,链接列表允许在列表中的任何位置插入和删除节点,并且操作数量恒定.

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

但这并不排除通过索引访问.如果您定义索引器,使列表中的每个连续"跃点"递减索引,那么您将拥有一个索引器.一个非常低效的索引器,但是一个索引器.因此,我认为索引器没有在链表上实现,以防止你在脚下射击自己,就像它们不直接支持`IEnumerable <T>`. (3认同)

归档时间：	15 年，3 月前
查看次数：	4228 次
最近记录：	11 年，3 月前