Creating dynamic data structures.
In the first part of this series - Creating custom collections - I showed how to wrap a .NET collection class to create a new enumerable collection with a custom name. In that article I used an ArrayList as my underlying storage container. Was that a good choice? Should I have used a HashTable? What's the difference anyway?
Well, as you are probably aware, there are many differences between a HashTable and an ArrayList, but what you may not already know is that these differences can dictate how the underlying data is stored in memory. In this article I'll explain the different structures that are used to store data in memory and demonstrate why different collection classes require different underlying structures.
What are collections
Collections are structures that allow programs to store and retrieve various items of data in a structured manner. The standard .NET collections include:
·     Hashtable
·     ArrayList
·     Stack
·     Queue
An important feature of collections is that the total number of items that they contain is (generally) unknown until runtime, i.e.: each time an item is added to a collection the actual structure that houses the data is altered.
Dynamic Vs. Static data storage
Many data structures - such as Int32 and arrays - are static. This means that their structure is completely defined at design time. While the field values of these structures can be altered by the program, the structure itself cannot.
Dynamic data structures allow their structure to by altered by the actual program, and because of this, they are ideal candidates to act as the underlying storage container for the items of a collection. A dynamic data structure that underlies a collection can expand or contract as items are added or removed from the list.
Two examples of common dynamic data structures are linked lists and binary trees.
Linked List
Without going into any great depth, a linked list is a list of items; each item is, itself a structure, and contains a value and a pointer (or reference) to the next item in the list. Adding a new item to a linked list simply means creating a new instance of an item and adding a reference to it from the item that is currently at the tail of the list.
The following snippet of psuedo-code shows how you might create a linked list of Fish, and then graphically displays what that structure would look like:
Class MyFishes
    Public Property HeadFish As Fish
    Public Property TailFish As Fish
    
    Public Method AddFish( newFish As Fish )
        
        If IsNothing( Me.HeadFish ) Then
            Me.HeadFish = newFish
            Me.TailFish = newFish
        Else
            Me.TailFish.NextFish = newFish
            Me.TailFish = newFish
        End If
    End Method
End Class

Class Fish
    Public Property Name As String
    Public Property NextFish As Fish
End Class

Dim TheListOfFishes As New MyFishes()

TheListOfFishes.AddFish( New Fish( "Fred" ) )
TheListOfFishes.AddFish( New Fish( "Martin" ) )
TheListOfFishes.AddFish( New Fish( "Rob" ) )
TheListOfFishes.AddFish( New Fish( "Karen" ) )
        
        +--------------------+
        |  TheListOfFishes   |
        +--------------------+
                |
    +-----------------------------------+
    |                                   |
+--------+  +--------+  +--------+  +--------+
|        |  |        |  |        |  |        |
|  Fred  |->| Martin |->|  Rob   |->|  Karen |-> Nothing
|        |  |        |  |        |  |        |
+--------+  +--------+  +--------+  +--------+

NOTE: The last child in a linked list contains a pointer with
      a null reference
You use a linked list when it is important to retrieve items in a manner that is relevant to the order in which they were added to the list. Take the following psuedo-code snippet which shows how you might normally retrieve these records from this type of structure: