为什么LinkedList(T)不实现IList(T)接口?

IList<T> 接口包含索引器,索引器不是您在 LinkedList .

List<T> 可以确保访问 O(1) , 链表 根据IT结构的定义,无法提供对 O(1) .

参见a的定义 linked list 你会明白的。

主要问题是,LinkedList可以包含循环引用,因此没有索引。

链表是最简单的 以及最常见的数据结构;它们 为 几个重要的抽象数据 结构,包括堆栈、队列, 关联数组和符号 表达。

链表的主要好处 在传统阵列上, 链接项的顺序可以是 不同于数据的顺序 项目存储在内存或磁盘上。 因此,链接列表允许 在任意位置插入和移除节点 点在列表中,带有一个常量 操作数。

另一方面,链接列表 它们本身不允许随机访问 对数据或任何形式的有效 索引。因此,许多基本操作 例如获取 列表,或查找 包含给定的基准或定位 新节点应该位于的位置 插入“可能需要扫描大多数 列表元素的。

接口提供三种类型的保证,一种是程序性的,另一种是概念性的。

程序保证您可以调用存在的方法或属性。.NET执行此担保。

第一个概念上的保证是它会起作用。这经常被打破(不实现例外和不支持例外正好存在于打破这一点上),但这样做应该有一个很好的理由。不过,这更像是一个承诺,而不是一个保证。

第二个概念上的保证更像是一个承诺,而不是一个保证,即方法或属性将像其他情况一样工作。

人们习惯于使用IList的索引器以相当快的速度工作—O(1)或更糟的O(log n),并且违反概念承诺会导致人们严重地使用您的对象。

这里没有具体的规则。您当然可以将IList实现为一个链表,并接受O(N)索引GET。您还可以实现一个链接列表,这样它就不会保留其计数的记录(就像框架提供的那样),并且具有O(N)计数属性。但是人们更容易滥用它。

组件设计的一部分不只是确保事情正常工作,而是指导它们的使用。实现IList的链接列表在后一点上会失败,因此可以有力地证明它的设计不如所提供的那样好。

LinkedList实际上是一种众所周知的列表数据结构,具有以下操作复杂性:

Insertion: O(N)

Removal: O(1)

Indexing: O(N)

而list是一个连续数组,它具有以下算法复杂性:

Insertion*: O(1)

Removal*: O(N)

Indexing: O(1)

它们不提供公共接口,因为它会误导用户的接口,使程序的效率无法预测。 有关更多信息,请参阅有关算法和数据结构的书籍。

LinkedList不是列表。列表是对象的一维集合。LinkedList是一个节点集合,与字典更紧密地对齐。它的需求与常规列表不同,但更专门化以允许节点遍历和组织行为。

“列表”是指数据结构术语是 不 链接列表;它实际上是一个数组——使用索引器可以直接访问列表项,而索引器在链接列表中不可用(不实用)。

历史怪癖:在.NET 1.1中,arraylist是一个类,其作用类似于动态长度数组。

在.NET 2+中,list内部组织为一个数组。这意味着,实际上,IList需要数组语义。

在.NET中,列表是 类数组 不是名单… (博宁)

真正的链表具有恒定的插入、删除时间,但枚举速度较慢,随机访问速度较慢。

数组具有快速枚举和随机访问,但插入/删除成本高昂(O(N),重新分配会导致完全不同的行为)

这也让我吃惊。传统上,列表只是一种可以依赖元素顺序的东西,而链接列表则遵循这一点,并且它应该实现IList而不是ICollection(集合不说明元素顺序)。

我认为,不实现IList是错误的,因为某些操作的复杂性比某些人预期的要差。

但是,链表不是设计为可由索引访问的数据结构, IList<T> 提供索引访问功能。

因此,由于无法按索引访问链接列表中的项目,因此无法提供尝试执行此操作的方法。

因为按索引访问链接列表不是O(1)。