Single Linked List in Visual Basic.Net

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.

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.

'Example of a node for use in a link list

Public Class clsNode

Private m_FirstName As String 'First Name of 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 node

Sub New()

m_next = Nothing 'Default to nothing

End Sub

Public Property FirstName() As String

Get

FirstName = m_FirstName

End Get

Set(ByVal StrName As String)

m_FirstName = StrName

End Set

End Property

Public Property LastName() As String

Get

LastName = m_LastName

End Get

Set(ByVal strLastName As String)

m_LastName = strLastName

End Set

End Property

Public Property SSN() As String

Get

SSN = m_SSN

End Get

Set(ByVal strSSN As String)

m_SSN = strSSN

End Set

End Property

Public Property NextNode() As clsNode

Get

NextNode = m_next

End Get

Set(ByVal clsNextNode As clsNode)

m_next = clsNextNode

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.
Private m_Tail As clsNode 'Stores the last node
Private m_count As Long 'Count of nodes

'Funciton New - Default Constructor
'Called when class is initialized.

Sub New()

m_count = 0 'The list has no nodes.
m_Head = Nothing 'Set head and tail to nothing.
m_Tail = Nothing

End Sub

'Function InsertAtHead
'Purpose: Clients should call this function to insert
'a node at the head of the list.
'Input: Node to be inserted.
'Output: none
'--------------------------------------------------------------------

Public Sub InsertAtHead(ByVal vNode As clsNode)

'If head is set to data.
If Not IsNothing(m_Head) Then

'The new node should be linked to head.
vNode.NextNode = m_Head

'set head as new node.
m_Head = vNode

Else

'First node in the list.
m_Head = vNode
m_Tail = vNode

End If

'update count

m_count = m_count + 1

End Sub

'Function InsertAtTail
'Purpose: Clients should call this function to insert
'a node at the tail of the list.
'Input: Node to be inserted.
'Output: none
'------------------------------------------------------

Public Sub InsertAtTail(ByVal vNode As clsNode)

'if head is set to data
If Not IsNothing(m_Head) Then

'Link last tail to new node
m_Tail.NextNode = vNode

'Update tail to the new node.
m_Tail = vNode

Else

'Only node in the list.
m_Head = vNode
m_Tail = vNode

End If

'update count

m_count = m_count + 1

End Sub

'Function GetNode
'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.
'------------------------------------------------------

Public Function GetNode(ByVal index As Integer) As clsNode

Dim cur As clsNode 'Temp var used to walk list.
Dim i As Integer = 1 'Temp Counter

'If client requested a position in the list that
'does not exist, set the return node to nothing,
'and exit funciton.

If index > m_count Then

GetNode = Nothing

Exit Function

End If

'Start at the top of the list.
cur = m_Head

'Walk the list until the desired position is located.

Do While i <>

cur = cur.NextNode

i = i + 1

Loop

'Return the node

GetNode = cur

End Function

'Function: Count
'Purpose: Clients should call this function to retrive
'the number of nodes in the linked list.
'Input: none
'Output: Number of nodes in list.
'------------------------------------------------------

Public Function Count() As Long

'Return Count
Count = m_count

End Function

'Function Empty
'Purpose: Clients should call this function to remove
'all nodes in the list.
'Input: none
'Output: none
'------------------------------------------------------

Public Sub Empty()

m_Tail = Nothing

m_count = 0

'Walk through list to remove all references to
'node objects. The garbage collector will take
'care of the actual freeing for us after it sees
'no references to the nodes.

While IsNothing(m_Head) = False

m_Head = m_Head.NextNode

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
Dim mynode As clsNode
Dim mylist As New clsSingleList 'Our list

'Create a new node.
mynode = New clsNode

'Give it some data.
mynode.FirstName = "John"
mynode.LastName = "Jones"
mynode.SSN = "555-55-5555"

'Add it to the front of the list.
mylist.InsertAtHead(mynode)

'Create a new node
mynode = New clsNode

'Give it some data
mynode.FirstName = "John"
mynode.LastName = "Homes"
mynode.SSN = "555-55-5555"

'Add it to the tail of the list
mylist.InsertAtTail(mynode)

'Print Count
Debug.Print(mylist.Count)

'Walk list
For i = 1 To mylist.Count

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.