BlitzMax/Modules/Data structures/Linked lists

A linked list allows you to efficiently add and remove objects to and from a collection of objects. To create a linked list, use the CreateList function. Add objects to a linked list using ListAddFirst or ListAddLast. Both functions return a link object which can be used to later remove the object with the RemoveLink function. You can also remove objects with the ListRemove function. However this is not as efficient as using RemoveLink because the list must first be searched for the object to be removed. To visit all the objects in a linked list, you can use an EachIn loop. Lists versus Arrays It is important to keep in mind that index-based access in a linked list is relatively slow. For each item that you wish to index, the linked list must iterate through its internal links until it finds the requested index, whereas an array can directly access any value at any position. "So why use linked lists at all?" you might ask. Inserting a value into the middle of an array is an "expensive" operation, you must move all items after the insert position down in the array by one, then insert the new value in the space created. In a linked list, you must simply redirect the pointers between links and you have instantly inserted a value in the middle of the list. It is generally best to use a linked list when you need to make many changes to data and an array when you need to frequently access data at random. If you need to make many insertions and deletions to an array you can convert it to a list with ListFromArray and then convert the edited list back to an array with ListToArray. Types TLink Link Object used by TList Methods Value NextLink PrevLink Remove TLink: Methods Value Method Value:Object() Description: Returns the Object associated with this Link. Example: ' value.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local link:TLink = list.FindLink("Item 2") Print String(link.Value()) NextLink Method NextLink:TLink() Description: Returns the next link in the List. Example: ' nextlink.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local link:TLink = list.FindLink("Item 2") Print String(link.NextLink().Value()) PrevLink Method PrevLink:TLink() Description: Returns the previous link in the List. Example: ' prevlink.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local link:TLink = list.FindLink("Item 2") Print String(link.PrevLink().Value()) Remove Method Remove() Description: Removes the link from the List. TListEnum Enumerator Object use by TList in order to implement Eachin support. TList Linked List Methods Clear IsEmpty Contains AddFirst AddLast First Last RemoveFirst RemoveLast FirstLink LastLink InsertBeforeLink InsertAfterLink FindLink ValueAtIndex Count Remove Swap Copy Reverse Reversed Sort ToArray Functions FromArray TList: Methods Clear Method Clear() Description: Clear a linked list Information: Removes all objects from list. IsEmpty Method IsEmpty() Description: Check if list is empty Returns: True if list is empty, else false Contains Method Contains( value:Object ) Description: Check if list contains a value Returns: True if list contains value, else false AddFirst Method AddFirst:TLink( value:Object ) Description: Add an object to the start of the list Returns: A link object AddLast Method AddLast:TLink( value:Object ) Description: Add an object to the end of the list Returns: A link object First Method First:Object() Description: Returns the first object in the list Information: Returns Null if the list is empty. Example: ' first.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Print String(list.First()) Last Method Last:Object() Description: Returns the last object in the list Information: Returns Null if the list is empty. Example: ' last.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Print String(list.Last()) RemoveFirst Method RemoveFirst:Object() Description: Removes and returns the first object in the list. Information: Returns Null if the list is empty. Example: ' removefirst.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") list.RemoveFirst() Local item:Object For item = EachIn list Print String(item) Next RemoveLast Method RemoveLast:Object() Description: Removes and returns the last object in the list. Information: Returns Null if the list is empty. Example: ' removelast.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") list.RemoveLast() Local item:Object For item = EachIn list Print String(item) Next FirstLink Method FirstLink:TLink() Description: Returns the first link the list or null if the list is empty. Example: ' firstlink.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local link:TLink = list.FirstLink() Print String(link.Value()) LastLink Method LastLink:TLink() Description: Returns the last link the list or null if the list is empty. Example: ' lastlink.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local link:TLink = list.LastLink() Print String(link.Value()) InsertBeforeLink Method InsertBeforeLink:TLink( value:Object,succ:TLink ) Description: Inserts an object before the specified list link. Comment: This method does not check if the given link is Null (can cause compiler errors). InsertAfterLink Method InsertAfterLink:TLink( value:Object,pred:TLink ) Description: Inserts an object after the specified list link. Comment: This method does not check if the given link is Null (can cause compiler errors). Example: ' insertafterlink.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") list.AddLast("Item 4") list.Remove("Item 3") Local link:TLink = list.FindLink("Item 2") If link <> Null Then list.InsertAfterLink("New Item 3!", link) Local item:Object For item = EachIn list Print String(item) Next FindLink Method FindLink:TLink( value:Object ) Description: Returns the first link in the list with the given value, or null if none found. ValueAtIndex Method ValueAtIndex:Object( index ) Description: Returns the value of the link at the given index. Information: Throws an exception if the index is out of range (must be 0..list.Count()-1 inclusive). Example: ' valueatindex.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Print String(list.ValueAtIndex(1)) Count Method Count() Description: Count list length Returns: The numbers of objects in list. Remove Method Remove( value:Object ) Description: Remove an object from a linked list Information: Remove scans a list for the specified value and removes its link. Swap Method Swap( list:TList ) Description: Swap contents with the list specified. Copy Method Copy:TList() Description: Creates an identical copy of the list. Example: ' copy.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local clone:TList = list.Copy() Local item:Object For item = EachIn clone Print String(item) Next Reverse Method Reverse() Description: Reverse the order of the list. Reversed Method Reversed:TList() Description: Creates a new list that is the reversed version of this list. Example: ' reversed.bmx Local list:TList = New TList list.AddLast("Item 1") list.AddLast("Item 2") list.AddLast("Item 3") Local reversed:TList = list.Reversed() Local item:Object For item = EachIn reversed Print String(item) Next Sort Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects ) Description: Sort a list in either ascending (default) or descending order. Information: User types should implement a Compare method in order to be sorted. ToArray Method ToArray:Object[]() Description: convert a list to an array Returns: An array of objects TList: Functions FromArray Function FromArray:TList( arr:Object[] ) Description: Create a list from an array Returns: A new linked list Functions CreateList Function CreateList:TList() Description: Create a linked list Returns: A new linked list object Example: ' createlist.bmx ' create a list to hold some objects list:TList=CreateList() ' add some string objects to the list ListAddLast list,"one" ListAddLast list,"two" ListAddLast list,"three" ' enumerate all the strings in the list For a$=EachIn list Print a$ Next ClearList Function ClearList( list:TList ) Description: Clear a linked list Information: Removes all objects from list. Example: ' clearlist.bmx Local list:TList = CreateList() ListAddFirst(list, "Item 1") ListAddFirst(list, "Item 2") ClearList(list) Local item:Object For item = EachIn list Print String(item) Next CountList Function CountList( list:TList ) Description: Count list length Returns: The numbers of objects in list. Comment: Keep in mind that this function iterates through every object in the list which can be slow when calling it often or when list is big. Example: ' countlist.bmx Local list:TList = CreateList() ListAddFirst(list, "Item 1") ListAddFirst(list, "Item 2") Print CountList(list) ListIsEmpty Function ListIsEmpty( list:TList ) Description: Check if list is empty Returns: True if list is empty, else false Example: ' listisempty.bmx Local list:TList = CreateList() Print ListIsEmpty(list) ListAddFirst(list, "Item 1") Print ListIsEmpty(list) ListContains Function ListContains( list:TList,value:Object ) Description: Check if list contains a value Returns: True if list contains value, else false Example: ' listcontains.bmx Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") Print ListContains(list, "Item 2") Print ListContains(list, "Item 3") SortList Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object ) Description: Sort a list Comment: The optional ascending and compareFunc allow the default sorting method to be altered. Example: ' sortlist.bmx Local list:TList = CreateList() ListAddLast(list, "Item 3") ListAddLast(list, "Item 1") ListAddLast(list, "Item 4") ListAddLast(list, "Item 2") SortList(list) Local item:Object For item = EachIn list Print String(item) Next ListFromArray Function ListFromArray:TList( arr:Object[] ) Description: Create a list from an array Returns: A new linked list Example: ' listfromarray.bmx Local array:String[] = ["Item 1", "Item 2", "Item 3"] Local list:TList = ListFromArray(array) Local item:Object For item = EachIn list Print String(item) Next ListToArray Function ListToArray:Object[]( list:TList ) Description: convert a list to an array Returns: An array of objects Example: ' listtoarray.bmx Local array:Object[] Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") ListAddLast(list, "Item 3") array = ListToArray(list) Local index:Int For index = 0 To array.Length - 1 Print String(array[index]) Next SwapLists Function SwapLists( list_x:TList,list_y:TList ) Description: Swap the contents of 2 lists Example: ' swaplists.bmx Local list:TList = ListFromArray(["Item 1", "Item 2", "Item 3"]) Local list2:TList = ListFromArray(["Item A", "Item B", "Item C"]) SwapLists(list, list2) Local item:Object For item = EachIn list Print String(item) Next For item = EachIn list2 Print String(item) Next ReverseList Function ReverseList( list:TList ) Description: Reverse the order of elements of a list Example: ' reverselist.bmx Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") ListAddLast(list, "Item 3") ReverseList(list) Local item:Object For item = EachIn list Print String(item) Next ListFindLink Function ListFindLink:TLink( list:TList,value:Object ) Description: Find a link in a list Returns: The link containting value Comment: Returns Null if no value found. ListAddLast Function ListAddLast:TLink( list:TList,value:Object ) Description: Add an object to a linked list Returns: A link object Example: ' listaddlast.bmx Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") Local item:Object For item = EachIn list Print String(item) Next ListAddFirst Function ListAddFirst:TLink( list:TList,value:Object ) Description: Add an object to a linked list Returns: A link object Example: ' listaddfirst.bmx Local list:TList = CreateList() ListAddFirst(list, "Item 1") ListAddFirst(list, "Item 2") Local item:Object For item = EachIn list Print String(item) Next ListRemove Function ListRemove( list:TList,value:Object ) Description: Remove an object from a linked list Information: ListRemove scans a list for the specified value and removes its link. Comment: This only removes the first instance of the value. Example: ' listremove.bmx Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") ListAddLast(list, "Item 3") ListAddLast(list, "Item 2") ListRemove(list, "Item 2") ' remove an object Local item:Object For item = EachIn list Print String(item) Next RemoveLink Function RemoveLink( link:TLink ) Description: Remove an object from a linked list Information: RemoveLink is more efficient than ListRemove. Example: ' removelink.bmx Local list:TList = CreateList() ListAddLast(list, "Item 1") ListAddLast(list, "Item 2") ListAddLast(list, "Item 3") Local link:TLink = ListFindLink(list, "Item 2") ' find a link If link <> Null Then RemoveLink(link) ' remove it Local item:Object For item = EachIn list Print String(item) Next