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