Linked Double.docx

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!