Creating a linked list
Let's look at an example of a circular doubly linked list where each node has a pointer to the previous and next elements in the list, as shown in Figure 7-2. Notice in the code that we have a "notional" starting point, pHead, which initially points to the head of the list.
Figure 7-2 A node in the list
The Node Class
Option Explicit ' "Pointers" to previous and next nodes. Public pNext As Node Public pPrev As Node ' Something interesting in each node - ' the creation number (of the node)! Public nAttribute As Integer Private Sub Class_Initialize() Set pNext = Nothing Set pPrev = Nothing End Sub Private Sub Class_Terminate() ' When an object terminates, it will already have ' had to set these two members to Nothing: ' this code, then, is slightly redundant. Set pNext = Nothing Set pPrev = Nothing End Sub
The Test Form
Option Explicit Private pHead As New Node Private pV As Node Public Sub CreateCircularLinkedList() Dim p As Node Dim nLoop As Integer Static pLast As Node ' Points to last node created ' pHead if first node. pHead.nAttribute = 0 Set pLast = pHead ' 501 objects in list - the pHead object exists ' until killed in DeleteList. For nLoop = 1 To 501 Set p = New Node p.nAttribute = nLoop Set pLast.pNext = p Set p.pPrev = pLast Set pLast = p Next ' Decrement reference count on object. Set pLast = Nothing ' Join the two ends of the list, making a circle. Set p.pNext = pHead Set pHead.pPrev = p Exit Sub End Sub Public Sub PrintList() Debug.Print "Forwards" Set pV = pHead Do Debug.Print pV.nAttribute Set pV = pV.pNext Loop While Not pV Is pHead Debug.Print "Backwards" Set pV = pHead.pPrev Do Debug.Print pV.nAttribute Set pV = pV.pPrev Loop While Not pV Is pHead.pPrev End Sub Public Sub DeleteList() Dim p As Node Set pV = pHead Do Set pV = pV.pNext Set p = pV.pPrev If Not p Is Nothing Then Set p.pNext = Nothing Set p.pPrev = Nothing End If Set p = Nothing Loop While Not pV.pNext Is Nothing ' Both of these point to pHead at the end. Set pV = Nothing Set pHead = Nothing End Sub
The routines CreateCircularLinkedList, PrintList, and DeleteList should be called in that order. I have omitted building in any protection against deleting an empty list. To keep the example as short as possible, I've also excluded some other obvious routines, such as -InsertIntoList.
In Visual Basic, a node will continue to exist as long as an object variable is pointing to it (because a set object variable becomes the thing that the node is set to). For example, if two object variables point to the same thing, an equality check of one against the other (using Is) will evaluate to True (an equivalence operator). It follows, then, that for a given object all object variables that are set to point to it have to be set to Nothing for it to be destroyed. Also, even though a node is deleted, if the deleted node had valid pointers to other nodes, it might continue to allow other nodes to exist. In other words, setting a node pointer, p, to Nothing has no effect on the thing pointed to by p if another object variable, say, p1, is also pointing to the thing that p is pointing to. This means that to delete a node we have to set the following to Nothing: its pPrev object's pNext pointer, its pNext object's pPrev pointer, and its own pNext and pPrev pointers (to allow other nodes to be deleted later). And don't forget the object variable we have pointing to p to access all the other pointers and objects. Not what you might expect!
It's obvious that an object variable can be thought of as a pointer to something and also as the thing to which it points. Remember that Is should be used to compare references, not =. This is why we need Set to have the variable point to something else; that is, trying to change the object variable using assignment semantically means changing the value of the thing to which it points, whereas Set means changing the object variable to point elsewhere. In fact nearly any evaluation of an object variable yields the thing to which the object variable is pointing to. An exception is when an object variable is passed to a routine as a parameter, in which case the pointer is passed, not the value (the object) that it's pointing to. (The object also has an AddRef applied to it.)
Linked lists that are created using objects appear to be very efficient. They are fast to create and manipulate and are as flexible as anything that can be created in C.