# 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
* Value
* NextLink
* PrevLink
* Remove

## TLink: Methods

Method Value:Object
Description: Returns the Object associated with this Link.
Example:
Method NextLink:TLink
Description: Returns the next link in the List.
Example:
Method PrevLink:TLink
Description: Returns the previous link in the List.
Example:
Method Remove
Description: Removes the link from the List.

## TListEnum

Enumerator Object use by TList in order to implement Eachin support.

## TList

Linked List
* Clear
* IsEmpty
* Contains
* AddFirst
* AddLast
* First
* Last
* RemoveFirst
* RemoveLast
* FirstLink
* LastLink
* InsertBeforeLink
* InsertAfterLink
* FindLink
* ValueAtIndex
* Count
* Remove
* Swap
* Copy
* Reverse
* Reversed
* Sort
* ToArray
* FromArray

## TList: Methods

Method Clear
Description: Clear a linked list
Information: Removes all objects from list.
Method IsEmpty
Description: Check if list is empty
Returns: True if list is empty, else false
Method Contains( value:Object )
Description: Check if list contains a value
Returns: True if list contains value, else false
Method AddFirst:TLink( value:Object )
Description: Add an object to the start of the list
Returns: A link object
Method AddLast:TLink( value:Object )
Description: Add an object to the end of the list
Returns: A link object
Method First:Object
Description: Returns the first object in the list
Information: Returns Null if the list is empty.
Example:
Method Last:Object
Description: Returns the last object in the list
Information: Returns Null if the list is empty.
Example:
Method RemoveFirst:Object
Description: Removes and returns the first object in the list.
Information: Returns Null if the list is empty.
Example:
Method RemoveLast:Object
Description: Removes and returns the last object in the list.
Information: Returns Null if the list is empty.
Example:
Method FirstLink:TLink
Description: Returns the first link the list or null if the list is empty.
Example:
Method LastLink:TLink
Description: Returns the last link the list or null if the list is empty.
Example:
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).
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:
Method FindLink:TLink( value:Object )
Description: Returns the first link in the list with the given value, or null if none found.
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:
Method Count
Description: Count list length
Returns: The numbers of objects in list.
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.
Method Swap( list:TList )
Description: Swap contents with the list specified.
Method Copy:TList
Description: Creates an identical copy of the list.
Example:
Method Reverse
Description: Reverse the order of the list.
Method Reversed:TList
Description: Creates a new list that is the reversed version of this list.
Example:
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.
Method ToArray:Object
Description: convert a list to an array
Returns: An array of objects

## TList: Functions

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:

## ClearList

Function ClearList( list:TList )
Description: Clear a linked list
Information: Removes all objects from list.
Example:

## 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:

## ListIsEmpty

Function ListIsEmpty( list:TList )
Description: Check if list is empty
Returns: True if list is empty, else false
Example:

## ListContains

Function ListContains( list:TList,value:Object )
Description: Check if list contains a value
Returns: True if list contains value, else false
Example:

## 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:

## ListFromArray

Function ListFromArray:TList( arr:Object )
Description: Create a list from an array
Returns: A new linked list
Example:

## ListToArray

Function ListToArray:Object( list:TList )
Description: convert a list to an array
Returns: An array of objects
Example:

## SwapLists

Function SwapLists( list_x:TList,list_y:TList )
Description: Swap the contents of 2 lists
Example:

## ReverseList

Function ReverseList( list:TList )
Description: Reverse the order of elements of a list
Example:

## 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:

## ListAddFirst

Function ListAddFirst:TLink( list:TList,value:Object )
Description: Add an object to a linked list
Returns: A link object
Example:

## 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:

## RemoveLink

Function RemoveLink( link:TLink )
Description: Remove an object from a linked list
Information: RemoveLink is more efficient than ListRemove.
Example: