Pages

Google+

Friday, November 27, 2009

Data Structures with AS3 - The Linked List

When programming, there are many things I avoid or  just squash out altogether:

  • If I see someone has written an event, I try to get rid of it - this goes 2x for custom events.

  • If I'm working on someone's production code and I see comments, I refactor and delete them.

  • I rarely use conditionals.




Sure....you may need to use a conditional to test: is 1 > 2?... but generally business logic doesn't need it.

One of my favorite data structures that enables me to avoid conditional logic is linked lists. Michael has some great data objects; however, his implementation is a little overkill for many of the simple things I do.

After using linked lists ( actually I use circular,  doubly linked list ) many times,  I end up always coming back to this one implementation over and over again.  I think it's successful because it's very, very simple. What ever your value object is, just have it implement this interface.  I usually just use a small algorithm to create all the links.
package
{
public interface DoublyLinkedListNode
{
function set nextLink(node:DoublyLinkedListNode) : void;
function get nextLink() : DoublyLinkedListNode;
function set previousLink(node:DoublyLinkedListNode) : void;
      function get previousLink() : DoublyLinkedListNode;
function get payload() : *;
}
}

It's self explanatory, save for maybe the 'payload' method.  That is what you'd use to return the object that implements the interface, example:
public function get payload() : *
{
return this;
}

An example of how I create my links:
private function add_linked_list_properties_to_array() : void
{
create_first_link();
create_middle_links();
create_last_link();
}

private function create_first_link() : void
{
var first_node = my_array[0];
var next_node = my_array[1];
var last_node = my_array[my_array.length - 1];

DoublyLinkedListNode(first_node).previousLink = DoublyLinkedListNode(last_node);
DoublyLinkedListNode(first_node).nextLink = DoublyLinkedListNode(next_node);
}

private function create_middle_links() : void
{
for (var i : int = 1;i [less than] my_array.length - 1;i++)
{
DoublyLinkedListNode(my_array[i]).previousLink = my_array[i - 1];
DoublyLinkedListNode(my_array[i]).nextLink = my_array[i + 1];
}
}

private function create_last_link() : void
{
var last_node = my_array[my_array.length-1];
var next_to_last_node = my_array[my_array.length-2];
var first_node = my_array[0];

DoublyLinkedListNode(last_node).previousLink = DoublyLinkedListNode(next_to_last_node);
DoublyLinkedListNode(last_node).nextLink = DoublyLinkedListNode(first_node);
}

If anyone has ever use pagination, sequential navigation, asynchronous navigation ( such as an image gallery with pagination and jump to item navigation ) or a carousel....you can use linked lists.