Back to CList for Iterators

I skipped some of the most important methods of the CList class with no explanation. For example, you might have wondered why I didn’t explain the Item method. Or you might have cheated and looked ahead. If so, you realized that Item finds a specified entry the same way you would find it from outside the class; it creates a local iterator and uses it to search through the list.

This is another reason to make CListWalker a separate class. Although this code is long and messy, it would be even more so if iteration weren’t abstracted in a separate class.

Here’s the code for the Property Get. The Property Let and Property Set procedures use a similar technique. Although it takes a lot of code to find the appropriate item, returning it in the Get procedure or modifying it in the Set or Let procedures is a simple operation.

‘ Default property
Property Get Item(Optional vIndex As Variant = 1) As Variant
    If lnkHead Is Nothing Then Exit Property
    ‘ Walk through to find the item
    Dim walker As New CListWalker, v As Variant
    Dim i As Long, iIndex As Long, sIndex As String
    
    ‘ Find the matching link
    walker.Attach Me
    If VarType(vIndex) = vbString Then
        ‘ Search by string key
        sIndex = vIndex
        ‘ Ignore error for entries that can’t be string compared
        On Error Resume Next
        Do While walker.More
            With walker.CurLink
                If .Item = sIndex Then
                    If IsObject(.Item) Then
                        Set Item = .Item
                    Else
                        Item = .Item
                    End If
                    Exit Property
                End If
            End With
        Loop
    Else
        ‘ Search by numeric index
        iIndex = vIndex
        Do While walker.More
            i = i + 1
            With walker.CurLink
                If iIndex = i Then
                    If IsObject(.Item) Then
                        Set Item = .Item
                    Else
                        Item = .Item
                    End If
                    Exit Property
                End If
            End With
        Loop
    End If
    ‘ Item = Empty
End Property

The Remove member works essentially the same way. It creates an iterator and walks through the list until it finds the item to be removed.

If you study this code carefully, you’ll begin to see why a linked list has limited utility. If you have 100 entries in the list and you want entry 99, you have to iterate through 99 entries to get there.

The advantage of a linked list is that it can grow or shrink, and it contains exactly the number of entries you put in. It’s easy to get at the first entry, and it’s easy to iterate from the front to the back. Accessing entries in the middle is not a strong point of lists. If these features meet your needs, fine. If not, you might prefer a doubly linked list—one with references to both the previous and the next links. The iterator for such a list should be able to move either forward or backward. The trade-off is more data for each link and more code for managing both links.

Perhaps you’re starting to get the idea that no data structure can be ideal for every kind of data. There’s always a trade-off. That’s why programmers in low-level languages like to have lots of data structures; you can pick the one that best fits your needs. Visual Basic programmers now have greater flexibility (and confusion) in choosing among multiple data structures.

CHALLENGE Although the CList class proves that lists based on objects are possible, these lists have more overhead and are bound to be slower than comparable lists based on pointers. If you really want an efficient linked list class, consider implementing it as an ActiveX component in C++ rather than in Visual Basic. This leads to my main point: the component industry has let us down. By now, we Visual Basic programmers ought to have a lot of fast, efficient collection components, giving us a wide choice of how we want to organize our data. Sure, we ought to be able to create collections in Visual Basic, and, as you’ll see later in this chapter, it is possible, although Visual Basic won’t help much. But I would use Visual Basic mainly for creating specific collections such as disks, drives, Registry nodes, and so on. I don’t think Visual Basic is the best language for creating generic container classes such as stacks, queues, dictionaries, lists, sparse arrays, etc. That’s what C++ is for. I want better collection classes, and I don’t think it’s Microsoft’s responsibility to provide them. If someone wants to step up and provide these tools, I’ll be first in line with cold cash. Otherwise, I might have to take on the job myself.