Pointers

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.