Data Structures: More on Linked Lists
November 26, 2007 on 2:57 pm | In Actionscript, data structures |I 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);
Hey! Nice work on the DataStructures!
Why you didn’t tried quicksort in the linked list too?
See ya!
Comment by Eduardo — November, 27 2007 #
the worst-case complexity for quicksort is O(n^2), for mergesort still O(N log N), so it should be better. Also I think quicksort operates slower on linked lists, but I have to check it. maybe I also provide a quicksort routine in the future.
Comment by Michael — November, 27 2007 #
sure.. the bottleneck of quicksort in flash may be the function calls in the recursion… Because the swaping that occurs in the “leafs” of the recursion tree probably will not cost that much..
about your engine.. finish it.. even if the Box2D is great C/C++ Physics Engine a port from C to Flash not always can be the fastest.. There are many tunning tricks in flash that C don’t need and can be forgoten.. Your engine is 100% flash and can be well-suited for the AVM after all..
Comment by Eduardo — November, 27 2007 #
Hi, are the updated classes not yet available from the SVN?
Comment by sascha/hdrs — December, 3 2007 #
I just made a full checkout from the google SVN repository - the latest revision is 59.
Comment by Michael — December, 3 2007 #
Hi Michael, I’ve just did a full checkout too (rev. 60 now) but I cannot find the methods like sort, reverse etc. in the Linkedlist classes.
Comment by sascha/hdrs — December, 4 2007 #
I don’t see a problem here, can you me send your repository ?
Comment by Michael — December, 4 2007 #
Now I’ve deleted the old project and made a fresh checkout and it worked. Seems it was because I’ve put it all in a src folder when checked out the first time. This time I just fetched the repository as it is. So now the de package starts in the projects root folder which is not really desired as I have to set the project root folder as a source folder. Either way this is ok for only using it as a class path.
Comment by sascha/hdrs — December, 4 2007 #
Dude. You. Rock.
Comment by Ralph — December, 5 2007 #
Hello,
First off, thanks for your awesome class package. I have an issue where I’m trying to create a doubly-linked list that is also random accessible.
I was using a hash before with just an object[key] = value methodology. I need to be able to add/remove the items directly and there can be no duplicate keys.
With a hash this is one line for remove or add.
Remove:
if (hash.hasOwnProperty(key)) delete hash[key];
Add:
if (!hash.hasOwnProperty(key)) hash[key] = item;
The DLinkedList class does not have random access like this and I need to iterate through the list to find out if the item exists or not and I am often adding/removing many items at once. When the number of items gets into the thousands, Flash can lock up. With a hash, I can add/remove tens of thousands of items in a moment. However, I also need the features of a DLinkedList.
Is there a way to manually remove nodes from a DLinkedList by some kind of id? I could create an index like
hash[key] = someNode;
If I could directly remove a node like this:
someNode.prev.next = someNode.next;
someNode.next.prrev = someNode.prev;
Not sure that’s allowed. Any guidance would be appreciated!
Comment by Steven Sacks — December, 11 2007 #
Solved it by adding this method to the DLinkedList class (for my purposes, the assumption is that the passed node belongs to the DLinkedList).
public function removeNode($node:DListNode):void
{
if (node == head)
head = head.next;
else
if (node == tail)
tail = tail.prev;
if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;
node.next = node.prev = null;
if (head == null) tail = null;
_count–;
}
Comment by Steven Sacks — December, 11 2007 #
whenever you add a node, you can create an iterator pointing to this node and then store it in your hash. for example:
var list:DLinkedList = new DLinkedList();
var node:DListNode = l.append(5);
yourHash[key] = new DListIterator(list, node);
then removing becomes simply:
yourHash[key].remove();
delete yourHash[key];
Comment by Michael — December, 12 2007 #
I just want to point one thing: I’ve made several tests using DLinkedList and it appears that removeTail and removeHead functions don’t work properly after using function like that: myList.sort(sortPlayers, SortOptions.INSERTION_SORT).
Comment by Kri — December, 13 2007 #
Hey,
I cannot get the following sort to work:
SortOptions.DESCENDING | SortOptions.CHARACTER_STRING
It ignores the descending and just sorts ascending.
Comment by Steven Sacks — December, 29 2007 #
Hey!
First off, I just want to say that you’ve saved my life this year. My senior project would be a sad shadow of its current self without your data structures. I did find a bug in your SListIterator code though, in the hasNext funtion, the code looks like this:
return Boolean(node);
which will always return true since you’re checking to see if the current node exists. Change it to this:
return Boolean(node.next);
and the problem goes away.
Comment by Sarah Ziegler — January, 27 2008 #
Hey Sarah,
i don’t think this is a bug. Image the iterator has just one element and you call start() to reset the iterator. Now hasNext() returns true and next() returns the one and only element of the iteration. next() then sets the node property to the next node, which is null. so Boolean(node) is false.
this can be quite confusing, because hasNext() or next() relate to the iteration, not the node.next properties of the nodes. this is needed so you can do something like this:
for (itr = list.getListIterator(); itr.hasNext();)
{
trace(itr.next());
}
Comment by Michael — January, 28 2008 #
I am trying to port this game’s internal algorithm to utilise one of these data structures.
At the moment, the game can fit about 100 bubbles and I can feel that it gets a bit slow when doing the calculation when it involves lots of bubbles.
What I did is a dodgy 6 direction check function that gets traversed/recursed manually twice and that works pretty well but I am thinking about doing something GREAT in the future with this game, so any one has any suggestions ideas on how I can approach this upgrade?
The game can be found here.
Comment by shuurai — March, 10 2009 #
[...] been noticed more widely. I was convinced about the power of linked lists after reading his post and been using them ever since. I build the evo3d and evoCunningParticleEngine based on [...]
Pingback by simppa.fi/blog » The fastest way to Z-sort and handle objects in AS3 — December, 6 2009 #