This is one of my favourite data structures :-)

 

A linked list is a data structure which consists of a set of nodes that are arranged in such a way that, the first node in the list points to the second and the second node in the list points to the third and so on. Each node also contains some data of interest. The first node in the list is called the head and the last node in the list is called the tail. Linked lists are used in situations wherein the number of items to store for a given situation is not known (for example, a list of employees). The following figure shows how a linked list can be visualized:

 

 

Implementing a linked list in .NET is very simple. In fact, the .NET Framework has classes that simulate the concept of a linked list, but implementing this data structure ourself is fun!! There are also many ways by which you can implement a list, but here we will see one simple method.

 

So, fire up Visual Studio .NET and try this VB.NET program: 

Module Module1

    Public Class NodeList
        Private nextNode As NodeList    ' Points to the next node
        Private nodeData As Object      ' Data for the current node

        ' The default constructor that takes in the data for the node and a pointer
        ' to the next node in the list
        Public Sub New(ByVal oData As Object, ByVal oNode As NodeList)
            nodeData = oData
            nextNode = oNode
        End Sub

        ' We override the default function so that we can do some extra processing before
        ' printing the list
        Public Overrides Function ToString() As String
            Dim strReturn As String

            strReturn = nodeData

            ' Check if the next node is empty. If not, then call the function
            ' in a recursive manner untill all nodes are exhausted
            If (Not IsNothing(nextNode)) Then
                strReturn = strReturn & " " & nextNode.ToString()
            End If

            ' Return the final value
            Return (strReturn)
        End Function
    End Class

    Sub Main()
        Dim oNode As NodeList

        ' This represents the tail of the linked list
        oNode = New NodeList("of this simple version of a linked list.", Nothing)

        ' This represents the head of the linked list
        oNode = New NodeList("Welcome to the implementation", oNode)

        ' Print the list
        Console.WriteLine(oNode.ToString())
        Console.ReadLine()
    End Sub

End Module

 

The NodeList class represents the linked list by using two members: nextNode and nodeData. We also provide a constructor that takes two arguments. One which contains the data to be stored and one which indicates the next node to link to. The data is stored as an object so that it can be generic. The next node to point to is stored into the nextNode variable. That's a suprisingly small amount of code for a linked list storage!! (C or C++ enthusiasts might remember here that we would need to take care of memory allocation etc etc, but all that is abstracted away by .NET and its wonderful garbage collector).

 

Each node also provides an overloaded version of the ToString method. The ToString method is available as part of the default inheritance from Object. We need to overload this method to ensure that we can modify the data that is to be printed when the user calls the method. The version of the ToString method that we have works in a recursive fashion to walk across all the nodes in the list and return the data that is contained in them (in reality, the walking over the various nodes in the list is present as a seperate function. This function would then call the ToString method to get the string equivalent of the current node). The recursion happens until the nextNode data item does not point to anything. This is characterized by the check that we make in the code using IsNothing.

 

The recursive method of implementation that we have provided allows us to print the entire list using a single call like the one shown below. We can also start the printing from anywhere in the list by providing the appropriate node object.

Console.WriteLine(oNode.ToString())

Note how in the main() method we create the tail of the list first and then create the head of the list and pass to the constructor the next node, which then creates the link. When you run this program, you get the output Welcome to the implementation of this simple version of a linked list.

 

That's it!! We have a functional linked list implemented in very less code and no concern whatever to memory management, which is great news!! The .NET garbage collector takes care of the memory management for us. You can add lots of functuonality to a linked list like searching though a list, sorting a list etc. I leave it to you to experiment these out. Have fun!!