The linked list is one of the foundation concepts of programming and it's supported directly by VB.NET language elements. For example, you can read The Useful Generic List in VB.NET to learn more about one of the higher level ways to uses lists in VB.NET.
But you can code a list "the hard way" too. This article shows one way to do that for a double linked list. But unlike other articles you might see, we're going to approach the solution with a lot of explanation because understanding this example is a great way to make sure you understand what's really happening in your code.
The Linked List
A linked list is simply an array of structures where each element contains a "pointer" to the next one. This basic structure underlies many of the collections and arrays in most programming languages - in concept at least. (The actual code that Microsoft uses ... well ... ) And in many languages such as C++, it continues to be implemented in code. In any case, understanding how one works genuinely qualifies as a fundamental concept.
The simplest linked list is a single linked list. Here's a logical diagram of one:
--------
Click Here to display the illustration
--------
The arrows are the "pointer" values, that is "links", and they're addresses of some type. A language like C++ will give you direct access to memory addresses that you can use in your code that are called pointers. In Visual Basic, pointers are handled for you. (In VB.NET, you can use a Delegate and the AddressOf function which is the equivelent to a pointer in C++ more or less.) You can learn about Delegate in the article, Using Delegates in Visual Basic .NET for Runtime Flexibility.
The node value is the information "payload" in the list. Note that these nodes don't have to be kept together in memory. Since a node always points to the next one, you can move them around and change the links to modify the list.
For example, the links let you insert or remove individual nodes by simply changing where the links point. If the last node points to the first one, then it's called a circular linked list. And if each node has a pointer to both the next node and the previous node, then it's called a double linked list.
The Double Linked List
This is the most complex linked list, but it has the advantage that you can directly add or delete nodes with only the address of that node. A double linked list also gives you sequential access to the list in both directions. Here's a logical diagram of a double linked list.
--------
Click Here to display the illustration
--------
Since VB.NET doesn't support memory pointers directly, one way to accomplish something similar is illustrated in the (somewhat dated now) book Visual Basic Design Patterns in the chapter on interface and abstract classes. The authors provide this code to accomplish the job. (This version has been cleaned up just a bit to make it easier to understand, and I also added a property to hold one data item, ElementContent.)
Public Class theElement
Inherits AbstractDoubleLink
Public Property ElementContent As Integer
End Class
Public Interface IDoubleLink
Property PreviousElement As IDoubleLink
Property NextElement As IDoubleLink
End Interface
Public MustInherit Class AbstractDoubleLink
Implements IDoubleLink
Private _PreviousElement As IDoubleLink
Private _NextElement As IDoubleLink
Public Property PreviousElement As IDoubleLink _
Implements IDoubleLink.PreviousElement
Get
Return _PreviousElement
End Get
Set(value As IDoubleLink)
_PreviousElement = value
End Set
End Property
Public Property NextElement As IDoubleLink _
Implements IDoubleLink.NextElement
Get
Return _NextElement
End Get
Set(value As IDoubleLink)
_NextElement = value
End Set
End Property
End Class
When I looked at this code, I said to myself, "Gee! I'll just whip out some code to use this class." It turned out to be easier said than done. I hate it when that happens! It would have been nice if the authors had included a more complete sample. (You can see more sample code in the article The Abstract Base Class.)
This is a really interesting piece of code. Notice that the properties of the Interface IDoubleLink are themselves IDoubleLink types. This allows a sort of recursive data structure that is easier to code than you might think:
Dim thisElement As New theElement
thisElement.NextElement = thisElement
--------
Click Here to display the illustration
--------
I did it a couple of times by mistake while writing the example code to use theElement. Although code like this ...
thisElement.NextElement.PreviousElement = thisElement
... turned out to have some real debugging headaches, the eventual code that accomplishes a double linked list looks like this:
Dim theList As New ArrayList
Private Sub Form1_Load(
sender As System.Object, e As System.EventArgs
) Handles MyBase.Load
' Starting the List
Dim thisElement As New theElement
theList.Add(thisElement)
End Sub
Private Sub btnAddLink_Click(
sender As System.Object, e As System.EventArgs
) Handles btnAddLink.Click
' Adding to the List
Dim thisElement As New theElement
thisElement.NextElement =
theList(CInt(txtInsertAt.Text)).NextElement
thisElement.PreviousElement =
theList(CInt(txtInsertAt.Text))
thisElement.ElementContent = theList.Count
theList.Add(thisElement)
theList(CInt(txtInsertAt.Text)).NextElement = thisElement
If thisElement.NextElement IsNot Nothing Then _
thisElement.NextElement.PreviousElement = thisElement
txtInsertAt.Text = CStr(thisElement.ElementContent)
End Sub
Private Sub btnDelLink_Click(
sender As System.Object, e As System.EventArgs
) Handles btnDelLink.Click
' Deleting from the List
If theList(CInt(txtInsertAt.Text)).PreviousElement IsNot Nothing Then
theList(CInt(txtInsertAt.Text)).PreviousElement.NextElement =
theList(CInt(txtInsertAt.Text)).NextElement
End If
If theList(CInt(txtInsertAt.Text)).NextElement IsNot Nothing Then
theList(CInt(txtInsertAt.Text)).NextElement.PreviousElement =
theList(CInt(txtInsertAt.Text)).PreviousElement()
End If
theList.RemoveAt(CInt(txtInsertAt.Text))
txtInsertAt.Text = CStr(theList.Count - 1)
End Sub
The property ElementContent is used in this code to "keep track" of which node is which. (Otherwise, it's really hard to tell because nothing in VB.NET helps tell which node is which.) That value is assigned only once when nodes are added ...
thisElement.ElementContent = theList.Count
... so you know it doesn't change.
If you trace through the code a few times while you add and delete nodes, you will see that the relative location of the nodes (in theList) jumps all over the place, but the double links keep track of where the previous and next nodes are. And, I wrote this myself for this article ... so there could be bugs! If you find any, please let me know! Enjoy!