Henry Instructions - Net Data Structure Object Silent Single List (1)
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) 'Initial head node protected tail as listnode = head' pointing to the reference tail
Protected nodecount as integer = 0 'Save Number Number, return to the count method
Protected version as integer = 0 'records the version number of chain list
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
----
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/
