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 https://en.wikipedia.org/wiki/List_(abstract_data_type) ) 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 https://www.great-white-software.com/blog/2019/08/06/interfaces/ 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.