** Henry ** ** 手记 —.NET ** ** 数据结构对象补遗之单链表（二） **
韩睿 ( 06/15/2003)
** 3.4 ** ** 根据索引位置或数据元素值在链表中查找 ** ** **
在链表中定位是对其进行操作的基础，我们在类的内部定义两个 Protected 的查找函数：
Protected Overridable Function FindByIndex( ByVal index As Integer ) As ListNode
'通过index来查找链表中的结点
Dim tempIndex As Integer = 0
Dim current As ListNode = head.NextNode '从头结点后的第一个结点开始
Dim returnValue As ListNode = Nothing '初始化返回结点
Do '循环查找
If index = tempIndex Then
returnValue = current
Else
current = current.NextNode
tempIndex += 1
End If
Loop Until current Is Nothing Or Not returnValue Is Nothing
Return returnValue
End Function
Protected Overridable Function FindByValue( ByVal value As Object ) As Integer
'通过数据值来查找链表中的结点的index
Dim tempIndex As Integer = 0
Dim current As ListNode = head.NextNode '从头结点开始
Dim returnValue As Integer = -1 '初始化返回值
Do '循环查找
If value.Equals(current.Data) Then
returnValue = tempIndex
Else
current = current.NextNode
tempIndex += 1
End If
Loop Until current Is Nothing Or returnValue > -1
Return returnValue
End Function
有这样的基础，我们就可以实现 IList 接口的 IndexOf 索引方法了：
Public Overridable Function IndexOf( ByVal value As Object ) _
As Integer Implements IList.IndexOf
'通过结点数据值返回结点索引
Validate(value) '先验证值
Return FindByValue(value) '调用protected的查找方法
End Function
这样，我们在使用链表来查找某个值的索引时，如果 value 为空，会抛出一个异常；如果没有找到，会返回 -1 ；找到了会返回该数据元素所在的索引位置。是不是与 ArrayList 的处理方法很相似？
另外，我们还需要实现 Contains 功能，用于判断链表中是否存在某个值：
Public Overridable Function Contains( ByVal value As Object ) _
As Boolean Implements IList.Contains
'在链表中查找value值
Validate(value)
If FindByValue(value) = -1 Then
Return False '找不到
Else
Return True '找到了
End If
End Function
** 3.5 ** ** 添加结点 ** ** **
在上文第 1 节就提到过，添加结点有两种情况，向链表尾添加与按索引值插入：
Public Overridable Function Add( ByVal value As Object ) _
As Integer Implements IList.Add
'向链表尾添加结点
Validate(value) '先验证值
tail.NextNode = New ListNode(value) '将现有尾结点的下一结点引用指向新结点
tail = tail.NextNode '将新添加的结点设为尾结点
version += 1 '更改版本号
nodeCount += 1 '添加链表计数
Return nodeCount - 1 '返回尾结点索引
End Function
Public Overridable Sub Insert( ByVal index As Integer , _
ByVal value As Object ) Implements IList.Insert
'向指定的索引处添加结点
Validate(index, value) '验证索引与数据值
Dim tempNode As ListNode = FindByIndex(index) '找到索引处的现有结点
'定义新结点，新结点的下一结点引用指向索引号为index的结点
Dim newNode As ListNode = New ListNode(value, tempNode)
'将index-1处的结点的下一结点引用指向新结点
FindByIndex(index - 1).NextNode = newNode
version += 1 '更改版本号
nodeCount += 1 '添加链表计数
End Sub
** 3.6 ** ** 删除结点 ** ** **
Protected Overridable Sub RemoveNode( ByVal node As ListNode, ByVal index As Integer )
'在类内部使用的删除结点
'删除结点的方法是将它前一结点的下一结点引用指向它的后一结点
Dim tempNode As ListNode = FindByIndex(index - 1) '找到欲删除结点的前一结点
tempNode.NextNode = node.NextNode
If node Is tail Then
tail = tempNode
End If
version += 1 '更改版本号
nodeCount -= 1 '减少链表计数
End Sub
Public Overridable Sub Remove( ByVal value As Object ) _
Implements IList.Remove
'类实现接口的删除方法
Validate(value)
RemoveAt(FindByValue(value))
End Sub
Public Overridable Sub RemoveAt( ByVal index As Integer ) _
Implements IList.RemoveAt
'类实现接口的按索引进行删除的方法
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt; LINE-HEIGHT: 12pt; TEXT-ALIGN: left; mso-