Henry手记—.NET数据结构对象补遗之单链表（二）
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
'类实现接口的按索引进行删除的方法
Validate(index)
Dim node As ListNode = FindByIndex(index)
RemoveNode(node, index)
End Sub
Public Overridable Sub Clear() Implements IList.Clear
'清空链表
head.NextNode = Nothing
tail = head
nodeCount = 0
version = 0
End Sub
从上面的三个Remove方法来看，其实都是通过类内部的RemoveNode方法来进行删除，只不过向用户提供了两个接口：一个是根据索引值来删除，一个是通过比对数据元素值来删除。在这里要说明一下，单链表因为不能反向查找前一结点，因此删除的效率比双向链表低，这一点我们以后在实现双链表的时候还会提及。
3.7 复制
将链表中的数据元素按某一索引为起始，将元素复制到Array中去。这一方法在实际操作中分外有用：
Public Overridable Sub CopyTo(ByVal array As System.Array, _
ByVal index As Integer) Implements IList.CopyTo
'从链表的索引处开始将元素复制到列表中去
If array Is Nothing Then
Throw New ArgumentNullException()
ElseIf index < 0 Then
Throw New ArgumentOutOfRangeException("索引越界")
ElseIf index >= array.Length _
Or (array.Length - index - 1) > nodeCount _
Or array.Rank <> 1 Then
Throw New ArgumentException()
End If
Dim current As ListNode = head.NextNode
Dim position As Integer = index
'循环复制
While Not current Is Nothing
array(position) = current.Data
current = current.NextNode
position += 1
End While
End Sub
----
声明：本文版权与解释权归韩睿所有，如需转载，请保留完整的内容及此声明。
QQ: 18349592
E-Mail: henry7685@hotmail.com
请访问本人专栏：http://www.csdn.net/develop/author/netauthor/Latitude/