UtterAccess HomeUtterAccess Wiki

Welcome Guest ( Log In | Register )

Custom Search
Edit Discussion
> Linked List    

This is intended as a theoretical implementation of a simple linked list in pure VBA. The purpose is to illustrate how one would create a chain of elements without requiring an array. Note that VBA already offers an built-in class, Collection which share many of features (and has more) and is also built-in. However, in cases where one want more customization/control over the implementation, that can provide a base.

The biggest problem with using an array is that you have to allocate ahead of time a number of elements. For situations where we have well-defined numbers of elements that doesn't change, that is usually no problems but there are also times where we may need to add new items and we wont' know how much we need to allocate. Arrays can be resized using Redim Preserve, but this can be an expensive operation because internally, a brand new array has to be allocated, old array copied into the new array. With a linked list (as well VBA's Collection), there is no such restriction; you can add as many items because each individual element are allocated as you add it to the list. Because the class maintains a private variable to the first node which also point to the second node that points to third node and so on, those nodes don't get disposed of until you release the other node pointing at that node.

To implement a simple Linked List requires two classes; one representing the nodes, other representing the actual list.

Node Class

CODE
Public PrevNode As Node
Public NextNode As Node
Public Member As Variant 'Could be other datatype if you wanted...

Node simply has 3 public members; 2 of it references to other instances of Nodes which enables us to preserve those nodes in memory beyond the scope of a procedure that added the node.

List Class

CODE
Private FirstNode As Node
Private CurrentNode As Node

Public Sub Add(Data As Variant)
   If FirstNode Is Nothing Then
       Set FirstNode = New Node
       FirstNode.Member = Data
       Set CurrentNode = FirstNode
   Else
       Set CurrentNode.NextNode = New Node
       With CurrentNode.NextNode
           Set .PrevNode = CurrentNode
           .Member = Data
       End With
       Set CurrentNode = CurrentNode.NextNode
   End If
End Sub

Public Sub EnumNodes()
   Dim LocalNode As Node
   Set LocalNode = FirstNode
   Do Until LocalNode Is Nothing
       Debug.Print LocalNode.Member
       Set LocalNode = LocalNode.NextNode
   Loop
End Sub

Private Sub Class_Terminate()
   'Ensure the chain is properly deallocated before disposing of the class.
   'Otherwise, the chain will be orphaned and won't free the consumed memory.
   Dim LocalNode As Node
   If Not FirstNode Is Nothing Then
       Set LocalNode = FirstNode
       Do Until LocalNode.NextNode Is Nothing
           If Not LocalNode.PrevNode Is Nothing Then
               Set LocalNode.PrevNode.NextNode = Nothing
           End If
           Set LocalNode.PrevNode = Nothing
           Set LocalNode = LocalNode.NextNode
       Loop
   End If
End Sub

We work through the List class which takes care of allocating the nodes and fixing up the nodes so they now have a NextNode and PrevNode associated, enabling us to walk the chain of nodes. When we add the very first item, a new Node is made and set as list's first node. When we add 2nd element, we add new node to first node's NextNode. Because FirstNode is a private variable of List class, it will continue to hold onto the 2nd node even after we've left the Add procedure. it may not be directly accessible, especially when it's deeper in the list, all elements in the chain will persist in memory as long it's still referenced by some other element.

IMPORTANT!!: Do not set FirstNode to Nothing without first walking through the whole chain of List, setting each Node to Nothing. Otherwise, the memory consumed by the chain will NOT be freed until you quit Access and if the list is sufficiently large or there were several lists, the quitting process will be that much slower.

Here's a sample code for usage:

CODE
Public Sub testlist()

Dim l As List
Set l = New List

l.Add 1
l.Add 2
l.Add 3
l.Add 4

l.EnumNodes

Set l = Nothing

End Sub


Creative Commons License
Linked List by UtterAccess Wiki is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
Editing and revision of the content is freely encouraged; for details, see Expected Usage.

Edit Discussion
Custom Search
Thank you for your support!
This page has been accessed 7,368 times.  This page was last modified 05:04, 27 April 2011 by BananaRepublic.   Disclaimers