Data Structures: More on Linked Lists
November 26, 2007 on 2:57 pm | In Actionscript, data structures | 18 CommentsI received a bunch of emails asking how to use my linked lists so I decided to revise the classes by changing and adding some methods. I did this with the Array class in mind, so hopefully the classes are now more accessible if you are used to arrays. The newest release (0.9) also contains bug fixes (thanks for reporting them!) and performance improvements. Here is a table comparing the methods of the Array and Linked List classes:
| Array | SLinkedList / DLinkedList | |
| push(…args):uint | append(…args):NodeReference | |
| pop():Object | removeTail():* | |
| unshift(…args):uint | prepend(…args):NodeReference | |
| shift():Object | removeHead():* | |
| join(sep:*):String | join(sep:*):String | |
| reverse():Array | reverse():void | |
| indexOf(searchElement:*, fromIndex:int = 0) | nodeOf(obj:*, from:DListIterator = null):DListNode | |
| lastIndexOf(searchElement:*, fromIndex:int = 0×7fffffff):int | lastNodeOf(obj:*, from:DListIterator = null):DListNode *1 | |
| sort(… args):Array | sort(…args) *2 | |
| concat(… args) | concat(…args) and merge(…args) | |
| splice(startIndex:int, deleteCount:uint, … values):Array | splice(start:NodeIterator, deleteCount:uint, …args):LinkedList | |
| *1 only defined for doubly linked lists *2 default sort behavior is numeric | ||
New and changed methods
New methods include join, reverse, nodeOf, lastNodeOf, concat, merge, sort, splice, shiftUp, popDown. Because you can’t refer to a linked list node by index, the nodeOf and lastNodeOf methods return an iterator referencing the node that contains the searched element instead. lastNodeOf is only defined for a doubly linked list since the singly linked version can’t go backwards.
concat works exactly like the arrayed version. It takes a comma-separated list of linked list objects, connects them and returns a larger list. Whereas concat leaves the original and passed lists unchanged, merge directly modifies the existing list, making this method a lot faster, since it just juggles some node references around, but this also means that the passed lists become invalid, so keep that in mind.
append, prepend, insertAfter and insertBefore now accept multiple arguments (it’s also faster to add various items in one shot). This matches the array’s push() and unshift() methods. Speaking of arrays, removeTail and removeHead now return the data of the removed node, like Array.pop() and Array.shift() do.
Sorting linked lists
By far the biggest addition is the ability to sort linked lists, and the new sort() is a serious method. It almost works exactly like the arrayed version. One difference is that numeric sorting is the default behavior simply because sorting numbers is far more often used in game programming. It’s also the fastest solution because the comparison function is inlined.
Another difference is that you can switch between two sort algorithms. The default sort method is the merge sort algorithm, which has the same complexity as the array’s build in quick sort algorithm, namely ÃŽËœ(n log(n)). In terms of performance it’s almost exactly half as fast as quick sort, not too bad.
Once your list is sorted and you start adding or removing elements, you can switch to the insertion sort algorithm (a stable implementation that directly works on a linked lists caused me some headaches - moving references around can be really confusing!) to resort the list. Why? The worst-case time complexity of insertion sort is Θ(n^2), occurring when numbers in the unsorted list are sorted in decreasing order from left to right. Here every number encountered needs to be swapped to the start of the list, but if the list is almost sorted, insertion sort has a linear behavior and thus outperforms other sort methods, since only a few swaps need to be done. Here are some benchmarks:
| Input size | Array | Linked List | ||||||
| quick sort | insertion sort | merge sort | insertion sort | |||||
| unsorted | nearly sorted | unsorted | nearly sorted | unsorted | nearly resort | unsorted | nearly sorted | |
| 1e+3 | 1 | 1 | 20 | 0 | 1 | 0 | 5 | 0 |
| 1e+4 | 6 | 3 | 2300 | 2 | 11 | 10 | 370 | 1 |
| 1e+5 | 80 | 50 | fails* | 20 | 180 | 320 | fails* | 8 |
| 1e+6 | 1400 | 600 | fails* | 220 | 3000 | 4500 | fails* | 130 |
| all values: averaged execution time in milliseconds based on a random input set *exceeds script time limit |
||||||||
As a conclusion, you can’t beat the build in quick sort for an unknown input set, only for nearly sorted data using insertion sort. Using linked lists & insertion sort is the fastest choice for maintaining sorted data in Actionscript, as it even outperforms arrays. An interesting behavior is that resorting a list with either quick or merge sort still needs quite a lot of time, in case of the merge sort it’s even slower afterwards! Besides, an efficient insertion sort implementation is only possible for doubly linked lists (the singly linked list uses the arrayed version instead). Finally some code examples:
var myList:DLinkedList = new DLinkedList();
myList.append(4, 5, 1, 2, 6, 3);
//default: merge sort, numeric
myList.sort();
//numeric, descending, insertion sort
myList.sort(SortOptions.DESCENDING | SortOptions.INSERTIONSORT);
//character-string, caseinsenstive
myList.sort(SortOptions.CHARACTER_STRING | SortOptions.CASEINSENSITIVE);
//custom compare function, list stores Player objects
function sortPlayers(a:Player, b:Player) {
return a.health - b.health;
}
myList.sort(sortPlayers, SortOptions.INSERTIONSORT);
