# Data structures in Xojo - Part 1 - Linked lists **URL:** \ **Category:** Xojo\ **Tags:** tutorials, xojo\ **Created:** [28 February 2020 18:52 UTC](https://ifnotnil.com/t/data-structures-in-xojo-part-1-linked-lists/148 "2020-02-28T18:52:45Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![npalardy](https://ifnotnil.com/user_avatar/ifnotnil.com/npalardy/32/10_2.png) [@npalardy](https://ifnotnil.com/u/npalardy)\ **Post date:** [28 February 2020 18:52 UTC](https://ifnotnil.com/t/data-structures-in-xojo-part-1-linked-lists/148/1 "2020-02-28T18:52:45Z")
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](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 : ```plaintext 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 ```plaintext 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 ```plaintext 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. ```plaintext 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. ```plaintext 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. ```plaintext 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 ```plaintext 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 ```plaintext 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 ```plaintext // creates a new List that holds integers dim myList as List // creates a new List that holds Strings dim myList as List ``` 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](https://www.great-white-software.com/blog/2019/08/06/interfaces/) then a person could write methods like : ```plaintext 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. ---
**Author:** ![Garry](https://ifnotnil.com/user_avatar/ifnotnil.com/garry/32/2_2.png) [@Garry](https://ifnotnil.com/u/Garry)\ **Post date:** [28 February 2020 19:45 UTC](https://ifnotnil.com/t/data-structures-in-xojo-part-1-linked-lists/148/2 "2020-02-28T19:45:02Z")
Fab article @npalardy. Thank you. FYI, the code for the `Count()` and `Item()` methods is empty 🧐 ---
**Author:** ![npalardy](https://ifnotnil.com/user_avatar/ifnotnil.com/npalardy/32/10_2.png) [@npalardy](https://ifnotnil.com/u/npalardy)\ **Post date:** [28 February 2020 20:07 UTC](https://ifnotnil.com/t/data-structures-in-xojo-part-1-linked-lists/148/3 "2020-02-28T20:07:38Z")
fixed ---
**Author:** ![npalardy](https://ifnotnil.com/user_avatar/ifnotnil.com/npalardy/32/10_2.png) [@npalardy](https://ifnotnil.com/u/npalardy)\ **Post date:** [2 March 2020 23:55 UTC](https://ifnotnil.com/t/data-structures-in-xojo-part-1-linked-lists/148/4 "2020-03-02T23:55:57Z")
[code for singly linked lists](http://great-white-software.com/miscellaneous/Singly%20linked%20list.zip)