The linked list data structure is useful when programmers need to do frequent inserts into a list of information, and it is also useful for data that needs to grow and shrink. Even though it is possible to achieve the same thing in an array, the manipulation on an array would require much more work. For example, if an insert is made in the middle of an array, all of the information below the insert would need to be moved. In a linked list, programmers can insert data into the middle of a list by adjusting two variables. In visual basic, linked lists can be implemented quickly, and programmers can use them to solve many problems. 'Example of a node for use in a link list Public Class clsNode Private m_FirstName As String 'First Name of customer. Sub New() End Sub Public Property FirstName() As String Get End Get Set(ByVal StrName As String) End Set End Property Public Property LastName() As String Get End Get Set(ByVal strLastName As String) End Set End Property Public Property SSN() As String Get End Get Set(ByVal strSSN As String) End Set End Property Public Property NextNode() As clsNode Get End Get Set(ByVal clsNextNode As clsNode) End Set End Property End Class Now that the node class is created, lets move on to creating a linked list class. The following code is an example of how to create a single linked list. The example linked list is just going to have simple functionality, and programmers should add more to it in order to better understand linked list data structures. A method to insert a node into a specified position of the list, remove a single node from any position in the list, and the ability to sort the list would be interesting functions for programmers to add. Public Class clsSingleList 'Member Data Private m_Head As clsNode 'Stores the first node. 'Funciton New - Default Constructor Sub New() End Sub 'Function InsertAtHead Public Sub InsertAtHead(ByVal vNode As clsNode) 'If head is set to data. 'The new node should be linked to head. 'set head as new node. Else End If 'update count m_count = m_count + 1 End Sub 'Function InsertAtTail Public Sub InsertAtTail(ByVal vNode As clsNode) 'if head is set to data 'Link last tail to new node 'Update tail to the new node. Else End If 'update count m_count = m_count + 1 End Sub 'Function GetNode Public Function GetNode(ByVal index As Integer) As clsNode Dim cur As clsNode 'Temp var used to walk list. 'If client requested a position in the list that If index > m_count Then End If 'Start at the top of the list. 'Walk the list until the desired position is located. Do While i <> Loop 'Return the node GetNode = cur End Function 'Function: Count Public Function Count() As Long End Function 'Function Empty Public Sub Empty() m_Tail = Nothing m_count = 0 'Walk through list to remove all references to While IsNothing(m_Head) = False End While End Sub End Class Finally, the following is an example of how to work with the linked list. Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click Dim i As Integer 'Create a new node. 'Give it some data. 'Add it to the front of the list. 'Create a new node 'Give it some data 'Add it to the tail of the list 'Print Count 'Walk list mynode = mylist.GetNode(i) Debug.Print(mynode.FirstName) Debug.Print(mynode.LastName) Debug.Print(mynode.SSN) Next ' Empty List mylist.Empty() Debug.Print(mylist.Count) End Sub In conclusion, linked list data structures are easy to create in visual basic. Since linked lists work on generic data, visual basic programmers can reuse their linked list code in many programs. After programmers build up a collection of different data structures, they can use them to solve many complex problems.
Linked Lists are created out of user defined types called nodes. A node is a class or data structure that is used to store a group of information. For example, a node may contain information about customers like their first names, last names, and social security numbers. In a single linked list, a node will also contain a special variable that points to the next node if one exists. When a new node is created, the last node of the listed will update its special variable to point to the new node. Since only one variable is used in a single linked list, it can only be traveled in one direction from head to tail. The following figure is a diagram of how a single linked list is structured.
In visual basic, nodes can be created with classes. The following code is an example of how to create a class node. The node is going to be used to store some example information of a customer.
Private m_LastName As String 'Last name of customer.
Private m_SSN As String 'Social Security Number.
Private m_next As clsNode 'Pointer to next nodem_next = Nothing 'Default to nothing
FirstName = m_FirstName
m_FirstName = StrName
LastName = m_LastName
m_LastName = strLastName
SSN = m_SSN
m_SSN = strSSN
NextNode = m_next
m_next = clsNextNode
Private m_Tail As clsNode 'Stores the last node
Private m_count As Long 'Count of nodes
'Called when class is initialized.m_count = 0 'The list has no nodes.
m_Head = Nothing 'Set head and tail to nothing.
m_Tail = Nothing
'Purpose: Clients should call this function to insert
'a node at the head of the list.
'Input: Node to be inserted.
'Output: none
'--------------------------------------------------------------------
If Not IsNothing(m_Head) Then
vNode.NextNode = m_Head
m_Head = vNode'First node in the list.
m_Head = vNode
m_Tail = vNode
'Purpose: Clients should call this function to insert
'a node at the tail of the list.
'Input: Node to be inserted.
'Output: none
'------------------------------------------------------
If Not IsNothing(m_Head) Then
m_Tail.NextNode = vNode
m_Tail = vNode'Only node in the list.
m_Head = vNode
m_Tail = vNode
'Purpose: Clients should call this function to retrive
' a node in the list.
'Input: Position of node in the list.
'Output: The node in the requested position. If no node
' exists, the function will set the clsNode to nothing.
'------------------------------------------------------
Dim i As Integer = 1 'Temp Counter
'does not exist, set the return node to nothing,
'and exit funciton.GetNode = Nothing
Exit Function
cur = m_Headcur = cur.NextNode
i = i + 1
'Purpose: Clients should call this function to retrive
'the number of nodes in the linked list.
'Input: none
'Output: Number of nodes in list.
'------------------------------------------------------'Return Count
Count = m_count
'Purpose: Clients should call this function to remove
'all nodes in the list.
'Input: none
'Output: none
'------------------------------------------------------
'node objects. The garbage collector will take
'care of the actual freeing for us after it sees
'no references to the nodes.m_Head = m_Head.NextNode
Dim mynode As clsNode
Dim mylist As New clsSingleList 'Our list
mynode = New clsNode
mynode.FirstName = "John"
mynode.LastName = "Jones"
mynode.SSN = "555-55-5555"
mylist.InsertAtHead(mynode)
mynode = New clsNode
mynode.FirstName = "John"
mynode.LastName = "Homes"
mynode.SSN = "555-55-5555"
mylist.InsertAtTail(mynode)
Debug.Print(mylist.Count)
For i = 1 To mylist.Count
Friday, June 12, 2009
Single Linked List in Visual Basic.Net
Subscribe to:
Post Comments (Atom)
hey I saw your post about using
ReplyDeleteVirtualQueryEx, I was wondering if you got it working , ive been looking for how to use it scanning bytes in memory and i have nor been sucsesfull doing so, would you like to share your ideas on this.
thanks for your time!
/Martin