Data structures in Xojo - Part 1 - Linked lists

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.

3 Likes

Fab article @npalardy. Thank you.

FYI, the code for the Count() and Item() methods is empty :face_with_monocle:

fixed

code for singly linked lists

1 Like