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 8-3. Notice in the code that we have a “notional” starting point, pHead, which initially points to the head of the list.
Figure 8-3 A node in the list
The Node Class
Option Explicit
‘ “Pointers” to previous and next nodes.
Public pPrev As Node
Public pNext 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 SubThe 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 SubThe 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.
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.