Data Structures with AS3 – The Linked List

Posted by Alan in Actionscript, Code, Flash, OOP Nov 27th, 2009 | no responses

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.



Leave a Reply