** Henry 手记 —.NET数据结构对象补遗之单链表（一） **
韩睿 ( 06/15/2003)
.NET Framework 提供了众多常用的数据结构对象，放在 System.Collections 命名空间中。现有 Arraylist 、 Queue 、 Stack 、 SortList 、 HashTable 等。但是奇怪的是，微软没有在 Framework 中加入链表、二叉搜索树等相当重要的数据结构对象。从本篇开始，我们将陆续将它们补充进我们自己的 .NET 类库，让它们更有效地成为工作的利器。同时，大家也会通过这些基本数据结构的实现，达到对 Framework 类与接口编程的深入理解，所以，不要错过。同时，我们也一起复习一下数据结构的内容吧。
Arraylist 是近来被大家不断提及与关注的列表类，它是由数组构成的。虽然 microsoft 对数组作了大量的改进，提高了增减元素操作的效率、实现了动态扩充的性能。但是数组始终是数组：在对元素的排序、删除、添加操作时，效率仍很低；更重要的是，数组的大小是固定的，即使是动态数组，只不过是加入了重新分配空间的能力 ; 同时，为了避免频繁地重新分配，不得不将数组初始化大小设得较大，这样就会大量地浪费内存。而事实上， Framework 对 Queue 、 Stack 、 Hashtable 等数据集合的实现，也部分或全部地使用了链表的方法，所以，自己动手实践一次，是分外有益的， Let’s go!
** 1. ** ** 单链表 ** ** (singly linked list) **
单链表是最简单的链表表示，因此我们先来对它进行分析与实现。用它来表示线性表时，每一个数据元素占用一个结点 (node) 。一个结点一般由两个域组成，一个域存放数据元素 data ；另一个域存放一个指向链表中下一个结点的指针 link ，它指出下一个结点的开始存储地址。
单链表的类实现，在每一本《数据结构》课本上都有详细的介绍：需要定义结点类和链表类，在链表类中实现对结点的操作。
在本文所要分析的链表类，我们采用嵌套定义的方式，将结点类定义在链表类的内部。所能进行的操作包括：添加（向链表尾插入结点）、插入（向链表中指定的索引位置插入结点）、按索引位置删除结点、按数据元素值删除结点、搜索数据元素值的索引、用 For Each 遍历链表中的值等。在我们的程序中，还会向大家展示如何在类中设计抛出异常、嵌套枚举器类等不常被提及的处理。
为了避免发生在链表头部或尾部进行插入或删除操作这样特殊的情况，给链表加一个数据为空的头节点。并加入尾结点指针，以方便添加功能的实现。
** 2. ** ** ArrayList ** ** 类分析 ** ** **
我们的单链表实现方法是模仿 Framework 现有的数据集合类的做法，而不是仅仅按照《数据结构》课本的 C++ 定义方法来实现。因此需要先来学习一下 Arraylist 类的定义：
** Public Class ArrayList ** ** ** ** **
** Implements IList, ICollection, IEnumerable, ICloneable ** ** ** ** **
也就是说 ArrayList 是实现了四个接口，我们当然要分别看一下这些接口的作用才好进行仿制工作。
1)IEnumerable ： IEnumerable 是公开枚举数，该枚举数支持在集合上进行简单迭代。必须对它进行实现才能支持 Microsoft Visual Basic 的 ForEach 语义。
ICollection ：派生自 IEnumerable 接口，定义所有集合的大小、枚举数和同步方法。 ICollection 接口是 System.Collections 命名空间中类的基接口。
IList ： Ilist 派生自 ICollection 。 IDictionary 和 IList 是基于 ICollection 接口的更专用的接口。 IDictionary 实现是键 / 值对的集合，如 Hashtable 类。 IList 实现是可被排序且可按照索引访问其成员的值的集合，如 ArrayList 类。
另：某些集合（如 Queue 类和 Stack 类）限制对其成员的访问，它们直接实现 ICollection 接口。或者当 IDictionary 接口和 IList 接口都不能满足所需集合的要求时，则从 ICollection 接口派生新集合类以提高灵活性。
以上三个接口的继承关系为： IEnumerable-> ICollection-> IList 。也就是说 ArrayList 其实是通过对 IList 的实现，同时实现了 ICollection 和 IEnumerable 。因此我们只需要实现 IList 接口即可。
4)ICloneable ：这个接口的作用就是实现克隆，即用与现有实例相同的值创建类的新实例。为纯粹我们的目标，这个接口不在本文中进行实现。留待后续文章中进行分析。
通过以上的分析，我们可以这样来定义我们即将要实现的单链表类了：
** Public Class SLList ** ** ** ** **
** Implements IList ** ** ** ** **
要实现接口，即要实现接口中定义的方法或属性。 IList 接口的实现需要声明的方法与属性如图 1 所示，一共有 15 个。分属于 IEnumerable 、 ICollection 和 IList 。
图 1 单链表类 SLList 需要实现的来自于接口的方法与属性
** 3. ** ** 实际演练 ** ** **
由于单链表类要能够在用户扩展时当成基类使用，所以它所有的字段、方法和属性是 Public 或者是 Protected 的，并且在必要的地方用 Overridable 进行标记。
接下来，我们依序从类定义到功能实现一一来详细说明：
3.1 类定义
我们用嵌套类定义的方式来定义结点类与链表类：
Imports System.Collections
Public Class SLList
Implements IList
Protected Class ListNode
Public NextNode As ListNode '指向下一个结点的引用
Public Data As Object '用object类型来声明数据，可以达到template的效果
Public Sub New ( ByVal data As Object , _
ByVal nextNode As ListNode)
'初始化结点
Me .Data = data
Me .NextNode = nextNode
End Sub
Public Sub New ( ByVal data As Object )
'作为尾结点的结点
Me .New(data, Nothing )
End Sub
End Class
……
3.2 类内公用变量初始化
Protected head As ListNode = New ListNode( Nothing ) '初始化头结点
Protected tail As ListNode = head '指向链表尾的引用
Protected nodeCount As Integer = 0 '保存节点数目，通过Count方法返回
Protected version As Integer = 0 '记录链表变化的版本号
这里使用了 version 这个变量，它的作用在后面我们会详细讨论的。
3.3 验证索引与数据元素
在类里定义了验证函数，验证失败，会抛出异常，这样用户在调用时可以用 Try … End Try 来处理：
Protected Overridable Overloads Sub Validate( ByVal index As Integer )
'验证index是否在可用范围内
If index < 0 Or index >= nodeCount Then
Throw New ArgumentOutOfRangeException("索引越界.")
End If
End Sub
Protected Overridable Overloads Sub Validate( ByVal value As Object )
'验证输入的数据是否存在
If value Is Nothing Then
Throw New ArgumentNullException()
End If
End Sub
Protected Overridable Overloads Sub Validate( ByVal index As Integer , ByVal value As Object )
'同时验证索引与数据元素
Validate(index)
Validate(value)
End Sub
----
声明：本文版权与解释权归韩睿所有，如需转载，请保留完整的内容及此声明。
QQ: 18349592
E-Mail: [email protected]
请访问本人专栏： <A href="http://www.csdn.net/develop/aut