Han Rui (06/15/2003)
The .NET Framework provides a wide range of common data structural objects, in the System.Collections namespace. Existing ArrayList, Queue, Stack, Sortlist, Hashtable, etc. But strangely, Microsoft did not add a quite important data structure object such as a linked list, a binary search tree in Framework. From this article, we will renew them to our own .NET class library, let them become a worker that works more effectively. At the same time, everyone will also achieve in-depth understanding of the Framework class and interface programming through these basic data structures, so don't miss it. At the same time, we also review the contents of the data structure together.
ArrayList has recently concluded that the list of concerns is constituted by the array. Although Microsoft logs a large number of improvements, it improves the efficiency of the increase or decrease element operation, and realizes the performance of dynamic expansion. However, the array is always an array: the efficiency is still very low when sorting, deleting, adding operations; more importantly, the size of the array is fixed, even if it is a dynamic array, it is just the ability to reassign space. At the same time, in order to avoid frequent redistribution, it has to be largely set to the array initialization, so it will waste memory. In fact, Framework implements a list of Queue, Stack, HashTable and other data sets, and some of them use the latheclable method, so I have practicated itself, it is existence, Let's Go!
Single-link list (Singly Linked List)
Single-lapse list is the simplest linked list, so we will first analyze and implement it. When using it to indicate the linear table, each data element takes up a node (Node). A node is typically composed of two domains, a domain stores data element data; another domain stores a pointer link to the next node in the linked list, which indicates the start storage address of the next node.
The class implementation of single-strand tables, every "data structure" class has a detailed introduction: You need to define node classes and linked tables, and implement the operation of nodes in the chain table class.
In this article, the chain table you want to analyze, we use nested definitions to define the node class inside the chain class. The operation can include: add (to the chain tail plug node), insert (insertion node to the index position specified in the list), press the index position to delete the node, select the data element value, search the data element value Index, use the value of the plane to traverse the chain table. In our program, you will also show you how to do an abnormally, nested enumerator classes, etc.
In order to avoid the occurrence of special conditions such as the chain head or the end of the tail, add a data empty head node to the linked list. And add a tailpoint pointer to facilitate the addition of functionality. 2. ArrayList class analysis
Our single-link table implementation method is to imitate the practice of Framework's existing data set classes, rather than just in accordance with the "data structure" textbook C definition method. Therefore, you need to learn the definition of the ArrayList class:
Public class arraylist
Implements ILIST, ICOLLECTION, IENUMERABLE, ICLONEABLE
That is to say, ArrayList is a four interfaces, which we must find out what these interfaces are good for impression.
1) IENUMERABLE: IENUMERABLE is an open enumeration number, which supports simple iteration on a collection. It must be implemented to support the Foreach semantics of Microsoft Visual Basic.
2) iCollection: Deleted from the IEnumerable interface to define all sets of size, enumeration, and synchronization methods. The iCollection interface is the base connection between the system.collections namespace. 3) IList: IList is derived from Icollection. IDictionary and ILIST are more dedicated interfaces based on ICollection interfaces. The IDictionary implementation is a collection of key / value, such as the HashTable class. ILIST implementation is a collection of values that can be sorted and can access their members in accordance with the index, such as the ArrayList class.
Also: Some collections (such as Queue Class and STACK classes) restrict access to their members, they directly implement the iCollection interface. Or when the iDictionary interface and the ILIST interface can meet the required collection requirements, new set classes are derived from the ICollection interface to improve flexibility.
The inheritance relationship of the above three interfaces is: ienumerable-> iCollection-> ILIST. That is, ArrayList is actually achieved by ILIST while achieving iCollection and IEnumerable. So we only need to implement the ILIST interface.
4) iCloneable: The role of this interface is to achieve clones, which is created with a new instance of the same value as existing instance. For pure our goals, this interface is not implemented herein. Leave a follow-up article for analysis.
Through the above analysis, we can define the single-link table class we are about to be implemented:
Public Class Sllist
Implements ILIST
To implement an interface, you want to implement the method or properties defined in the interface. The method and attribute of the ILIST interface need to be declared, as shown in Figure 1, a total of 15. It belongs to IENUMERABLE, ICOLLECTION and ILIST.
Figure 1 Method and attributes from interfaces required for single-strand table SLLIST
3. Actual drill
Since the single-strand table class is capable of use as a base class as a base class, it is all the fields, methods, and attributes are public or protected, and marked with OverridABle in the necessary place.
Next, we are defined from the class to the classification to implement a detailed description:
3.1 Class definition
We define node classes and link classes in a nested class:
Imports system.collections
Public Class Sllist
Implements ILIST
Protected class listNode, PROTECTED CLASTNODE
Public nextnode as listNode 'points to the next node
Public Data As Object 'Declaring data with the object type to achieve the effect of Template
Public Sub New (Byval Data As Object, _
Byval nextnode as listnode
'Initialization node
Me.Data = data
Me.nextNode = NextNode
End Sub
Public Sub New (ByVal Data As Object)
'As a node of the tail point
Me.New (Data, Nothing)
End Sub
END CLASS
......
3.2 Internal variables Initialization
Protected head as listnode = new listnode (nothing) 'Initialization head node
Protected tail as listnode = head 'references to the tail of the chain table
Protected NodeCount AS Integer = 0 'Save Number Number, Returns Protected Version AS Integer = 0' Record Lin List VERINY
This variable is used here, and its role will be discussed in detail later.
3.3 Verify Index and Data Elements
Defining a verification function in the class, the verification fails, will throw an exception, so that the user can use TRY ... END TRY to process when calling:
Protected Overridable overloads Sub Validate (BYVAL INDEX AS INTEGER)
'Verify that INDEX is within available range
IF index <0 or index> = NodeCount Then
Throw new ArgumentOutofrangeException ("index liner.")
END IF
End Sub
Protected Overridable overloads Sub Validate (BYVAL VALUE As Object)
'Does verify that the input data exists
IF value is nothing then
Throw new argumentnullexception ()
END IF
End Sub
Protected Overridable overloads Sub Validate (Byval Value As Object)
'VERE verification index and data elements
Validate (INDEX)
Validate (Value)
End Sub
3.4 Find in the linked list according to the index position or data element value
Location in the list is the basis for operation, we define two protected findings in the category:
Protected Overridable Function Findby Index (Byval Index As Integer) AS ListNode
'Look for nodes in the list through index
DIM Tempindex as integer = 0
DIM CURRENT As ListNode = Head.NextNode 'starts from the first node after the head knot
DIM RETURNVALUE As ListNode = Nothing 'Initialization Return Node
DO 'loop lookup
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
'Take the data value to find the index of the node in the list
DIM Tempindex as integer = 0
DIM CURRENT As ListNode = Head.NextNode 'starts from the head knot
DIM RETURNVALUE AS INTEGER = -1 'Initialization Return Value
DO 'loop lookup
IF value.equals (current.data) THEN
ReturnValue = Tempindex
Else
Current = current.nextNode
Tempindex = 1END IF
Loop unsil current is nothing or returnValue> -1
Return ReturnValue
END FUNCTION
With this basis, we can implement the ILIST interface indexof index method:
Public overridable function indexof (Byval value as object) _Dexof (BYVAL VALUE As Object)
As integer imports ilist.indexof
'Return node index by node data value
Validate (Value) 'First verification value
Return FindByValue (Value) 'Call Protected Finding Method
END FUNCTION
In this way, when we use the list to find an index of a value, we will throw an exception if Value is empty; if not found, it will return -1; find the index position where the data element is returned. Is it similar to ArrayList?
In addition, we also need to implement the Contains function, used to determine if there is a value in the list:
Public Overridable Function Contains (Byval Value As Object)
As Boolean Implements IList.Contains
'Find value values in the list
Validate (Value)
IF FindByValue (Value) = -1 Then
Return False 'can't find
Else
Return True 'found
END IF
END FUNCTION
3.5 Add Node
In the first quarter above, it is mentioned that there are two cases, add the end of the linked list and insert the index value:
Public Overridable Function Add (Byval Value As Object)
As integer imports ilist.add
Add a node to the linked list
Validate (Value) 'First verification value
TAIL.NEXTNODE = New ListNode (Value) 'points the next node of the existing tailpoint to the new node
Tail = tail.nextnode 'Sets the newly added node to the tailpoint
Version = 1 'Change version number
NodeCount = 1 'Add a chain table count
Return NodeCount - 1 'Returns the tail node index
END FUNCTION
Public overridable subinsert (byval index as integer, _
IMPLEMENTS ILIST.Insert
'Add a node to the specified index
Validate (Index, Value) 'Verify Index and Data Value
DIM TEMPNODE As ListNode = FindbyIndex (Index) 'found an existing node at the index
'Define new nodes, the next node of the new node references the index of index to index
DIM NewNode As ListNode = New ListNode (Value, TempNode)
'Pointing the next node of Index-1 points to the new node
FindbyIndex (Index - 1) .nextNode = NewNode
Version = 1 'Change version number
NodeCount = 1 'Add a chain table count
End Sub
3.6 Delete Node
Protected Overridable Sub Removenode (Byval Node As ListNode, Byval Index As INTEGER)
'Delete node used inside the class
'Delete node method is to reference the next node of its previous junction to the next node
DIM TEMPNODE AS LISTNODE = FindByindex (INDEX - 1) 'found the previous node to delete nodes
TempNode.nextNode = node.nextNode
IF node is tail kil
Tail = TempNode
END IF
Version = 1 'Change version number
NodeCount - = 1 'Reduced Lin Try
End Sub
Public Overridable Sub Remove (Byval Value As Object)
Implements IList.remove
Delete method of "class implementation interface
Validate (Value)
Removeat (FindByValue (Value)
End Sub
Public Overridable Sub Removeat (BYVAL INDEX AS INTEGER) _
Implements ilist.removeat
The method of deleting the index in the interface
Validate (INDEX)
Dim node as listnode = findbyindex (index)
Removenode (Node, INDEX)
End Sub
Public Overridable Sub Clear () IMPLEments IList.Clear
'Empty linked list
Head.nextNode = Nothing
Tail = HEAD
NodeCount = 0
Version = 0
End Sub
From the above three Remove methods, it is actually deleted through the RemoveNode method inside the class, but only provides two interfaces to the user: one is deleted according to the index value, one is by comparing the data element value. delete. Here, you will explain it here, the single-link sheet is not to look forward to the previous junction, so the efficiency of deletion is lower than the bidirectional linked list, which will later mention when the double-linked list will be mentioned.
3.7 replication
Press the data element in the list to start with an index, copy the element to the Array. This method is useful in actual operations:
Public Overridable Sub Copyto (Byval Array As System.Array, _
IMPLEMENTS ILIST.COPYTO
'Start copying the elements to the list from the index of the list
IF array is nothing then
Throw new argumentnullexception ()
Elseif Index <0 THEN
Throw new ArgumentOutofrangeException ("index matte")
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
'Cycle replication
While Not Current Is Nothing
Array (position) = current.datacurrent = current.nextnode
Position = 1
End while
End Sub
----
3.8 ITEM properties
The Item property is supplied to VB.NET (2) to operate the list in such a way, which will also give a single-strand list and an ArrayList array, although it is not as good as an array, but such a convenient operating means we can't let go :
Default Public Overridable property item (_
Byval Index as integer) AS Object Implements IList.Item
The 'Item property, the data value of the index of the read and written list
Get
Validate (INDEX)
Return FindbyIndex (Index) .DATA
END GET
SET (ByVal Value As Object)
Validate (INDEX, VALUE)
Findbyindex (index) .data = value
End set
End Property
Similarly, we also provide a counting function, which is used by the NodeCount members in the above various operations.
Public overridable readonly property count () AS integer_
Implements ilist.count
'Return to the total number of linked tables
Get
Return NodeCount
END GET
End Property
Here, is we have implemented basic listing operations? However, there are still some important mechanisms that have not revealed to readers, let us continue. 3.9 Implementation of for Each Cycle Enumeration
For each is a very strong traversal method. To implement this feature, the chain table must implement the IEnumerable interface, and we reach this in ILIST we have achieved this goal by implementing the GetEnumerator function from the Ienumerable. But the function returns the IEnumerator enumerator type, so we have to achieve its own enumerator to achieve the handling of the list:
IEnumerator is a base interface for all enumerations. The number of enumerations only allows data in the collection. The number of enumerations cannot be used to modify the base collection. The Ienumerator interface supports two methods and an attribute. The MOVENEXT method can move a record in a collection. The reset method enables the enumerator to reset the start of the collection. Current read-only performance returns the current record from a collection.
Initially, the number of enumerated numbers is positioned in front of the first element in the collection. RESET also returns the enumeration number to this location. At this location, calling Current will trigger an exception. Therefore, before reading the value of the CURRENT, MoveNext must be called to advance the enumeration number to the first element of the collection.
Current returns the same object before calling MoveNext or RESET. MoveNext Sets Current to the next element.
After passing to the end of the collection, the enumeration number is placed behind the last element in the collection, and the calling MoveNext will return false. If the last time call MoveNext returns false, calling Current will lead to an exception. To set the current to the first element of the collection again, you can call the RESET and then call MoveNext.
As long as the collection remains the same, the number is maintained. If the collection is changed (eg, add, modify, or delete an element), the number of the enumeration will be invalid and unrecoverable, and the next time the next time the call will raise InvalidOperationException. If the collection is modified between MoveNext and Current, even if the number of enumerated is invalid, the Current will return the elements it set. Now you will understand the usage of the Version we have continuously seen in front. Since we have defined ListNode as nested classes, we need to call members of the SLLIST class, so place the custom implementation IENUMERATOR interface into the SLLIST class, becoming the second nested class:
Public overridable function genumerator () AS IENUMERATOR _
Implements IList.GeteNumerator
Return New SllistenceUmerator (ME)
END FUNCTION
Below is a class that implements the Ienumerator interface.
Protected Class SllistenceUmerator
Implements IENUMERATOR
'Nested countercraft in SLLIST
Protected List as Sllist
Protected Currentelement As Object
Protected currentnode as listNode 'Nested internally can use this class
Protected version as integer 'internal version records for comparison if there is a change in the chain list
Public Sub New (Byval List as Sllist)
'initialization
Me.list = list
Me.Version = list.version
Me.currentelement = list
Me.currentnode = list.head
End Sub
Protected Overridable Sub VerifyListisunchanged ()
'The determination version has changed after the enumerator is created.
If not version = list.version then
Throw new INVALIDOPERATIONEXCEPTIONEXCEPTIONEXCEPTION
"This chain list changes after the enumerator is created")
END IF
End Sub
Public overridable readonly property current () AS Object_
Implements IENUMERATOR.CURRENT
'Return to the current record
Get
'Determine if it has reached the tail or whether to call MoveNext Find Record
IF currentelement is listim
IF currentnode is list.Head Then
Throw new INVALIDOPERATIONEXCEPTIONEXCEPTIONEXCEPTION
"The Current method is invalid before the MoveNext is called.")
Else
Throw new INVALIDOPERATIONEXCEPTIONEXCEPTIONEXCEPTION
"I have reached the collection tail, so the Current method is invalid")
END IF
END IF
Return Currentelement
END GET
End Property
Public overridable function moveXExt () as boolean _
Implements IENUMERATOR.MOVENEXT
'Continue your enumerator to the next object
VerifyListisunchanged ()
IF not currentnode.nextnode is nothingatenode = currentnode.nextNode
Currentelement = currentnode.data
Return True
Else
Currentelement = LIST
CurrentNode = list.head
Return False
END IF
END FUNCTION
Public Overridable Sub Reset () Implements IENUMERATOR.RESET
'Reset the enumerator to its initial position
VerifyListisunchanged ()
CurrentNode = list.head
Currentelement = LIST
End Sub
END CLASS
----
3.10 Other properties
This article does not fully implement all ILIST interface methods and properties, but it is still to be declared as follows. Since the single-chain table class in this article does not provide a built-in thread synchronization (all finished, what is the next time I say. Haha), Issynchronized returns to false, Syncroot returns to the reference. The number of enumerations do not have an exclusive access to the collection; therefore, enumerating a collection in essence is not a thread security process. Even when synchronizing the collection, other threads can still modify the collection, which will cause an enumeration number to trigger an exception. To ensure thread security during enumeration, you can lock a collection through the SYNCLOCK throughout the enumeration process, or capture exceptions caused due to changes in other threads. The processing like the SSLIST class, each lock will block all objects, to provide a smaller thread safety, we will continue to discuss later.
Public overridable readonly property issynchronized () as boolean _
Implements ilist.issynchronized
Get
Return False
END GET
End Property
Public overridable readonly property syncroot () as object _
Implements ilist.syncroot
Get
Return ME
END GET
End Property
The isFixedSize property refers to a value when analog is implemented, which indicates whether the ilist has a fixed size. The chain table category does not have a fixed size, so the return is of course FALSE.
Public overridable readonly property isfixedsize () as boolean _
Implements IList.isfixedsize
Get
Return False
END GET
End Property
The isReadOnly property refers to a value indicating whether iList is read-only when an implementation is implemented. Of course, returning false.
Public overridable readonly property isreadonly () as boolean _
Implements IList.isreadOnly
Get
Return False
END GET
End Property
4. Call the example
Above we have analyzed in detail with the implementation of the SSLIST class, now come and see its structure, as shown in Figure 2:
Figure 2 structure (including two nested classes)
So how do you use our single-link table? In fact, it is easy, it is quite similar to the usage method of the ArrayList class, but we don't have to set the length of the list. In another VB file, let's operate on the SLLIST class: 'Example of use
DIM LST AS New SLLIST ()
Try
Lst.Add ("Henry") Add
Lst.Add ("jjj")
Lst.Insert (1, "kkk") 'insert
Lst.Remove ("jjj") 'Press value to delete
Lst.Removeat (1) 'Delete according to the index number
LST (0) = "jerry" "change
Dim i as integer = lst.indexof ("jjj") 'Removing the code number
'Multiple loop traverses
DIM CollectionItem As Object
Dim loopcounter as integer
DIM ENUMCOLLECTION As IEnumerator
'The first
For Each CollectionItem in LST
Console.writeline (CollectionItem)
NEXT
'Second
For loopCounter = 0 to Lst.count - 1
Console.WriteLine (LST.Item (LoopCounter))
NEXT
'Third
Enumcollection = Lst.GeteNumerator ()
Do While Enumcollection.Movenext
Console.writeline (Enumcollection.current)
Loop
Catch exception
MsgBox (ex.toswoting)
END TRY
Now let's take a look at the role of Version:
'Third
Enumcollection = Lst.GeteNumerator ()
Lst.Add ("Kelly")
Do While Enumcollection.Movenext
Console.writeline (Enumcollection.current)
Loop
At this point, you will get an exception, prompt to:
System.invalidOperationException: This chain list has changed after the enumerator was created.
Isn't this an error message we defined in the VerifyListisunchanged method? Now everyone will understand why we have the corresponding prompt text when you operate ArrayList or other .NET classes. Imaginate the error prompts that we define our definition prompts will also be captured in this example. Please test it yourself.
5. Summary and Prospect
In this article, you will go deep into the implementation of the Collections collection class, and we use ArrayList (I am also, huh) in the actual work. However, the insertion of the linked list is much higher than that of ArrayList (single-linked list plus the front flute pointer will increase efficiency), of course, the ability of the index value is not as good as ArrayList. When we deal with certain lists of frequently deleting and insert, we are still worth considering whether to use a linked list to implement our needs.
Limited to space and time, for sorting, synchronization, etc. ARRAYLIST has no excessive involvement, interested friends, please continue to pay attention to my column. see you later!
----
Disclaimer: The right to copyright and interpretation of this article belongs to Han Rui, if you need to reprint, please keep your full content and this statement.
QQ: 18349592
E-mail: Henry7685@hotmail.com Please visit my column: http://www.9cbs.net/develop/author/netauthor/ilatitude/
Author Blog:
http://blog.9cbs.net/latitude/
