We use often data structures for whatever application we build, but since ActionScript itself offers them as base classes (Array, ArrayCollection,Vector, Dictionary) you probably never stop to think about them. I was forced when working on casual games, since speed is a must in this context, even going against the best practices. Sometimes, and specially in heavy process context (100 enemies coming around) is not possible to just use an array because processing get out of control. If you add some artificial intelligence to your enemies, should find the best path and should avoid some bullets, you get the picture. Anyway I’m not saying that applications or heavy sites don’t need also code optimizations, but as ActionScript developers probably casual games is the field where this situation is more evident.
To see the running sample click here
Table of contents
How to install the example
Array
Linked List
Binary Search Tree
Binary Heap
Hash Table
Graph
Summary
Files to run the example locally
This example was built using Flash Builder, amfphp and a mysql database, so in order to run it you should have some available server. Anyway there’s no need to run your own version, you can download the flex project to just read the source and check the running example here. Anyway if you want to run your own version follow this steps
- Download the source code from here , source include sql to generate the database and the php file to create the service.
- Import the project into Flex.
- You will find a rar file inside the main folder of the project with the SQL to generate the database table, the database is named “structures” but you can use any name as far as you change the PHP accordingly.
- You will find services.php file inside the main folder of the project that need to be copied to amfphp/services … if you dont know what amfphp is, probably you need to read first the Remoting tutorial
- Data structures are heavily based on dpdk opensource package. A copy is included in the lib folder of the project, but you can update with the latest source from http://www.dpdk.nl/opensource/source-code.
My example is just to feature the algorithms, his structure is probably a little messy, with sorting in the main mxml file while data structures manipulation lives each one in his own component.
Array
Probably the most widely used in ActionScript and the base structure for other more sophisticated data structures. Array is a simple list of elements that can be accessed by index.

Complexity
Insertion/deletion average: O(n)
Indexing: Θ(1)
Insertion/deletion at end: Θ(1)
Insertion/deletion in middle: Θ(n)
Wasted space (average): Θ(n)
Family: Bit array, Circular buffer, Heightmap, Lookup table, Sparse matrix
We will no give much more details since you should be familiar with it, but we want to mention that array is the base element for may of the other classes, and is widely used for general purpose data storing. Just is important to note that in AS3 there are some methods that comes very handy to manipulate arrays, like Array.every, forEach, map, some, reverse, that even being available since AS3, are not often used.
Linked List
Each record of a linked list is often called an element or node.
The field of each node that contains the address of the next node is usually called the next link or next pointer. The remaining fields are known as the data, information, value, cargo, or payload fields. The head of a list is its first node, and the tail is the last node (or a pointer thereto). If the last node contains a link to the first node, then we call it a circular linked list.
Insertion/deletion average: O(n)
They can be used to implement several other common abstract data structures, including stacks, queues, associative arrays, and symbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation. It’s principal advantage when inserting/deleting data is that you don’t need to reorder the entire list, you just change the reference of the adjacent nodes. In AS3 object access is faster than array access, so it competes very well in terms of performance when iterating over the list.
Binary Search Tree
Also named as sorted binary Tree, this is a tree of nodes following this principles:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. So retrieving data (specially when there’s a large list) is very fast. The BST as the hash table is very fast to search, but the approach is different: the BST uses a recursive approach to split up large amounts of data into smaller sets.
Binary Heap
A binary heap is a heap data structure created using a binary tree . It can be seen as a binary tree with two additional constraints:
The shape property: the tree is a complete binary tree ; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure.
If the tree is ordered from greater to smallest is called max-heaps, while the opposite is called min-heaps, that are often used to implement priority queues. It is possible to modify the heap structure to allow extraction of both the smallest and largest element in O(log n) time
Hash Table
A hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys. The hash function is used to transform the key into the index (the hash) of an array (slot or bucket) In the simplest case each key map to a single value (i.e names and telephone numbers) but value could be anything. That means that a good hash function is a must to have a good look-up average. A perfect hashing function will not repeat any hash for different inputs, but this is almost impossible. To allocate collisions (two keys mapping to the same location) there are many strategies, that vary from have a rule to find an different bucket using a progression (open addressing) or use dynamic arrays to store many entries in the same slot, so the look-up should scan the list to find the value, and of course the key itself should be stored.
ActionScript have his own implementation of the Hash table named Dictionary, but you can build your own, and in fact in our example we use a custom class for this purpose.
Hash table are very fast to look-up data as far as you don’t expect a lot of collisions, in which case probably a tree fits better.
Graph
A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references.
Graph are very used in path finding, where some character should find the best path between two points. In fact there are many algorithms to do this, being one of the most used the named A* algorithm
Related to this (how to move and interact with he world) , Artificial Intelligence also use graph structures, and also soft-body dynamics.
Summary
As noted in the beginning of this quick walk trough principals sorting algorithms and data structures, there are a lot of chances that you never face to the need of selecting in a fine grain fashion which kind of algorithm or structure you need, since many times the language you use have built-in mechanism or classes that priories the choice. Anyway, when you should face some complexity, in example when building games, where performance is a priority, having this concepts clear is a plus.
I want to emphasize here that the classes we have used to showcase the whole thing are from the open source library you can find here the package http://www.dpdk.nl/opensource/source-code and here an explanation http://www.dpdk.nl/opensource/the-collections-package, thanks to them to give the real power to this example










