In other languages data structures like linked lists (and other variations) are common.
In Xojo though a lot of developers tend use arrays and/or dictionaries instead. There’s nothing wrong with this but there may be reasons where you want to use a different structure.
So we’ll start with one that is really common; a linked list.
In a linked list there is a “head” or starting point that is the beginning of the list. And each member has a link to the next member. This allows a list to become arbitrarily large.
As well, since a “List” is both a data structure and a well defined set of operations we’ll need to add a number of methods to it (see List (abstract data type) - Wikipedia ) which outlines the kinds of methods we typically want to add.
- an operation for creating an empty list
- an operation for testing whether or not a list is empty
- an operation for prepending an entity to a list
- an operation for appending an entity to a list
- an operation for determining the first component (or the “head”) of a list
- an operation for referring to the list consisting of all the components of a list except for its first (this is called the “tail” of the list.)
- an operation for accessing the element at a given index.
In Xojo it makes sense to describe this in a class as that allows us to encapsulate both the data and the operations. That might be expressed as something like :
Class List
Constructor()
IsEmpty() as boolean
Prepend(newitem as Variant)
Append(newitem as Variant)
Head() as ListNode
Tail() as List
Item(index as integer) as ListNode
Count() as integer
Private Constructor(startNode as ListNode) // this constructor will be explained later
Private firstItemInList as ListNode
End Class
Class ListNode
Property data as variant
Property nextItem as ListNode
End Class
Note we need both a container for the List class and then a class for each element in the list. In some other languages you may or may not have things structured similarly. (1)
The no parameter constructor requires no code whatsoever. (note we’ll discuss the second constructor that uses a ListNode as its parameter later)
IsEmpty is similarly simple
Function IsEmpty() as boolean
return firstitemInList is nil
end function
Prepending is the act of inserting a new item before the current first item and this new item then being made to be the first item
Sub Prepend(newitem as Variant)
dim newListNode as new ListNode
newListNode.Data = newItem
newListNode.nextItem = self.firstItemInList
self.firstItemInList = newListNode
End Sub
Appending is the act of inserting a new item after the current last item in the list. If the list is currently empty then this new item is now the first item.
Sub Append(newitem as Variant)
dim newListNode as new ListNode
newListNode.Data = newItem
if self.IsEmpty then
self.firstItemInList = newListNode
else
// now the tedious part
// we have to start at the beginning and traverse all the
// nextitem links to get to the one that has no next item and add our new one on
dim currentNode as ListNode = self.firstItemInList
while currentNode.nextItem <> nil
currentNode = currentNode.nextItem
wend
// we're at the last item that has NO next item so add our new node to the end
currentNode.nextitem = newListNode
end if
End Sub
The Head method simply returns the First node in the list, if there is one.
Function Head() as ListNode
return self.firstItemInList
end function
The Tail method returns the list with the head item missing.
This should be a new list that may or may not have elements.
Function Tail() as List
// this requires the SECOND constructor that takes a ListNode
// as a parameter
// we do not ALTER the original list
// we just make our new "head" be whatever used to be the second item
return new List( self.firstItemInList.nextItem )
end function
Private Sub Constructor(startNode as ListNode)
self.firstItemInList = startNode
End Sub
Item is a reasonably simple method the access an item by index
Function Item(index as integer) as ListNode
if self.firstitemInList is nil then
return nil
end if
dim counter as integer
dim currentNode as listnode = self.firstItemInList
while currentNode <> nil and counter < index
currentNode = currentNode.nextItem
counter = counter + 1
wend
if currentNode is nil then
return nil
else
return currentNode
end if
End Function
And count returns a total count of items in the list
Function Count() as integer
dim counter as integer
dim currentNode as listnode = self.firstItemInList
while currentNode <> nil
currentNode = currentNode.nextItem
counter = counter + 1
wend
return counter
End Function
and thats the entire code for a List
Now something to note. Implementing a list this way has rather terrible perfomance characteristics.
Adding an element takes increasing long as the list gets larger. Counting elements gets slower as the list gets longer.
And, if you compare what operations are possible on the list vs a Xojo array you would find that for the most part Xojo arrays are “Lists” (2)
But this gives us a good start to moving on to other types of similar data structures
// === foot notes
(1) In some other languages you may see a notation like
// creates a new List that holds integers
dim myList as List<Integer>
// creates a new List that holds Strings
dim myList as List<String>
This is “generics” where the class “List” can take a “parameter” for what kind of data it should hold but the basic operations that lists perform are common across all instances of a List
Xojo does not support this so we have to do extra work to get around this limitation yet still provide a reasonably robust implementation.
(2) I’ve asked that Xojo apply certain “interfaces” to some of the framework classes and
datatypes, list a List interface, so that we can write reasonably generic code that
handle “any kind of list” in a generic way. If the List interface was defined as I outlined in Interfaces – Writings from the sticks then a person could write methods like :
Sub InsertInvoiceItemsToList(whatInvoideItems() as InvoiceItem, whatList as List)
// code here to add the items to a list
// ...
End Sub
a only write that once to insert to ANY kind of item that implemented the List interface. As it is now you have to write this code each time for a ListBox, popupmenu, combobox, etc since they only have commonly named methods but do not implement an interface.
