Data structures example: linked lists

What’s a linked list ?

A linked list is very similar to an array in a way that both are structures capable of storing elements sequentially. However, taking a closer look reveals that they work totally different internally. Like all arrays the build-in array class in ActionScript stores multiple elements in a single array instance accessed by indexing, while a linked list uses a separate object instance for each data element. This object is called a node, and besides storing the data it also needs to hold a reference to the next node in the list. The result is the most simple form of a linked list, the singly linked list:

If a node also stores a reference to the previous node it can move in both directions, forth and back; this is obviously called a doubly linked list, which is shown below.

The SLinkedList and DLinkedList classes in the data structure package act as containers for storing the nodes and provide methods for manipulating (appending/deleting etc.) the list, taking care of everything. But a linked list can also be solely defined by a bunch of node objects, without using a manager class. For example, in a singly linked list, a node object could be defined like this:

class Node
{
    var data:*;
    var next:Node;
}

Then a basic functional list could be created like this:

var a:Node = new Node();
var b:Node = new Node();
var c:Node = new Node();

a.next = b;
b.next = c;
c.next = null;

Pretty simple, right? Note that you don’t have to store node ‘b’ and ‘c’ explicitly – as long as node ‘a’ is stored properly, the garbage collector has no way of removing them, so they stay alive.

A doubly linked list is more flexible and some operations like unlinking nodes from the list are faster. So why didn’t I omit the singly linked version? Because if you know in advance that you’ll only move in one direction and seldom modify the list, the singly linked version is a good choice because it needs less memory and you get a slight performance gain, as the node management is a little bit simpler behind the scenes.

Arrays vs. Linked Lists

A weakness from which an array suffers is that although it gives direct access to any array cell, it’s clumsy when it comes to modifying the array, like removing or inserting elements after it has been initialized. This is demonstrated below, where you can click a cell and drag it to remove it from the array, which is essentially a splice(nodeIndex, 1) operation.

Now the resulting ‘gap’ is filled, and all elements right of the gap are shifted one position to the left. This takes time and gets worse the bigger the array gets. On very large arrays this operation can lead to a hefty slow down (see also the queue post) and should be avoided for real time applications. The worst-case happens when you remove the first element (shift()), while only the last element can be removed instantly (pop()). The same of course applies for inserting elements. So in the end an array is great for a stack, but bad for a queue if implemented in a naive way.

Now this is where a linked list shines, because data can be removed or inserted almost instantly, making it perfect for situations where you need a structure that constantly changes.

As with the array demo, you can drag a node to the screen edge to unlink it from the list. In addition, you can also insert a node by pressing the ‘I’ key. Watch what happens: no large chunks of data have to be moved around in memory, just the references, visualized by the arrows, need to be updated, which is fast and simple. If you hold a node near an edge of the screen, you see how the links would change. Grey arrows represent obsolete links that will be removed together with the dragged node. The transparent blue and purple links are rerouted to ‘bridge’ the current node.
Looking at the code, each node has a small helper function to unlink it from the list that looks like this:

function unlink():void
{
    //new purple link
    if (prev != null) prev.next = next;

    //new blue link
    if (next != null) next.prev = prev;

    //obsolete grey links
    next = prev = null;
}

If the first (head) or last (tail) node is removed, this gets even simpler:

if (node == head)
{
    head = head.next;
}
else if (node == tail)
{
    tail = tail.prev;
}

If you want to remove a node from the list using the SLinkedList or DLinkedList class, you first create an iterator object pointing to the node, and then remove it later on at any time calling the remove() method on the iterator itself or the linked list:

var itr:DListIterator = new DListIterator(myList, myNode);

itr.remove();

//or
myList.remove(itr);

This is even possible if the list was modified before. With an array, you have to keep an eye on the array index of the stored item whenever you modify the array.

Another advantage of linked lists is that they are more human-readable. Modifying indices by hand is error-prone and I think the most common mistakes come from the zero-based nature of arrays (the last element is n-1 and not n). To show you the difference, the common brute force method for checking a number of objects against each other (e.g. for collision queries), implemented with arrays and linked lists are shown below.

//arrayed version
var k:int = myArr.length;
for (var i:int = 0; i < k - 1; i++)
{
    oi = myArr[i];
    for (var j:int = i + 1; j < k; j++)
    {
        oj = myArr[j];
        collide(oi, oj);
    }
}

//linked version
var node:SListNode = head;
while (node)
{
    //check node against all following nodes
    var walker:SListNode = node.next;
    while (walker)
    {
        collision(node, walker);
        walker = walker.next;
    }
    //repeat with next node
    node = node.next;
}

Iterating over a linked list

Here are the basic ways to iterate over a list, starting with the 'cleanest' way using the iterator pattern. It decouples the iteration from the implementation resulting in a common interface all data structures in the package support.

//get iterator instance
var itr:DListIterator = new DListIterator(list);

//or simply
itr = list.getListIterator();

//start iteration
for (itr.start(); itr.valid(); itr.forth())
{
    trace(itr.node, itr.data);
}

This can also be written using a while loop:

//restart
itr.start();

while (itr.valid())
{
    tr(itr.node, itr.data);
    itr.forth();
}

Both iteration styles are fine in most cases, but when performance is critical you should definitely avoid using the iterator interface. Although it offers a unified way of accessing data, the iterator pattern needs many function calls. Therefore we modify the second iteration method and change it slightly to arrive at a very lightweight iteration method:

//take the first node
var walker:DListNode = list.head;
while (walker)
{
    trace(walker, walker.data);
    walker = walker.next;
}

The code above just uses the node's pointer to the next node to successively jump from node to node until a dead end is reached, and that happens when the tail node is referenced, which obviously has no valid next node.

Performance & optimization

Comparing the latter while loop with a standard for loop yields that it's slightly slower, but there isn't really a big difference between the loop bodies. Keep in mind that it's more important what you are actually doing inside the loop body than purely looking at the loop code itself, so the numbers won't have a measurable impact on performance. Anyway here are some numbers:

But let's move from empty loop bodies and try to access the data, which is much more interesting:

var val:*
//arrayed version, [] access
for (var i:int = 0; i < 1e+7; i++)
{
    val = myArray[i];
}

//linked version, '.' access
while (walker)
{
    val = walker.data;
    walker = walker.next;
}

Quick note: leaving val untyped is surprisingly a lot faster than strongly typed.

So, no difference here, meaning that linked lists can be a perfect replacement for arrays in terms of data access speed, at the same time offering superior performance when modifying big data sets.

Instead of using a list manager like the DLinkedList class, you can implement a custom 'low-level' linked list if you want to get the most out of the AVM. All you need is a basic node class, capable of storing data and and a reference to other nodes. But be aware that if you start playing around with references, you should assure that every reference is removed properly if unused, otherwise you quickly run into hairy problems resulting in strange behavior and memory waste/leak...

That should be all you need to know about linked lists. As usual you can download the examples for this article here.

See also:
The graph class
The queue class
The tree class

Data structures example: the graph class

In the last data structures post I talked about the tree structure, now let’s head towards graphs. As usual I’m also providing the source files for all included examples, which you can download here.
The code is a bit rough and there is plenty room for optimizations, but nevertheless I hope you understand what’s going on. Also make sure you have the latest release, because I have modified almost all graph-related classes.

What’s a graph?

Graphs (also known as Networks) are very powerful structures and find their applications in path-finding, visibility determination, soft-bodies using mass-spring systems and probably a lot more. A graph is similar to a tree, but it imposes no restrictions on how nodes are connected to each other. In fact each node can point to another node or even multiple nodes at once.

A node is represented by the GraphNode class, and the connections between GraphNode objects are modeled by the GraphArc class. The arc has only one direction (uni-directional) and points from one node to another so you are only allowed to go from A to B and not in the opposite direction. Bi-directional connections can be simulated by creating an arc from node A to B and vice-versa from B to A. Also, each arc has a weight value associated with it, which describes how costly it is to move along the arc. This is optional though, so the default value is 1.

Putting it together, the graph is implemented as an uni-directional weighted graph. The Graph manages everything: it stores the nodes and the arcs in separate lists, makes sure you don’t add a node twice, or mess up the arcs (for example if you remove a node from the graph, it also scans the arc list and removes all arcs pointing to that node) and provides you with tools to traverse the graph.

Building the graph structure

In figure 1, you see a simple graph containing 8 nodes. You can add additional nodes, which will be placed at the position of the cursor by pressing ‘a’ or start with a fresh graph by pressing ‘r’. To create an arc point from node A to Node B, simply click both nodes successively. Traversal is also possible: First press ‘t’ to switch to ‘traverse’ mode, then click a node to find all nodes which are connected to the this node.

Graph traversal

If you have tried out the traversal in the example above, you may wonder how it’s done. The answer lies in two common algorithms to accomplish this: Breadth-first search (BFS) and depth-first search (DFS). (The demonstration above used the breadth-first search.)

The BFS algorithm visits all nodes that are closest to the starting node first, so it gradually expands outward in all directions equally. This looks like a virus infecting the direct neighborhood at each search iteration. BFS utilizes a queue and proceeds as follows:

1. Mark the starting node and enqueue it.
2. Process the node by calling a user-defined function on it.
3. Mark all connected nodes and also put them into the queue.
4. Remove the node at the front of the queue.
5. Repeat steps 2-5 with the node that is now at the front of the queue.
6. Stop if the queue is empty.

The depth-first search (DFS) on the other hand takes the starting node, follows the next arc it finds to get to the next node, and continues this until the complete path has been discovered, then goes back to the starting node and follows the next path until it reaches a dead end and so on. It’s currently implemented as a recursive function, that means that it probably can fail for very large graphs when the call-stack exceeds the maximum size (I don’t know how big it is in AS3 though).

Both algorithms have in common that they mark a node when it’s added to the queue, otherwise the node would be enqueued and unnecessarily processed multiple times, because different nodes can all point to a common node. So before you start a BFS or DFS it’s very important to reset all markers by calling the clearMarks() function on the graph.

The two algorithms are visualized in figure 2 below. I’ve created a rectangular grid of nodes (similar to a tilemap) by connecting each node with the top, bottom, left and right neighbors (I left out the arcs because it would be a total mess). I have also deleted some nodes to show you that both algorithms don’t rely on a regular structure and can look like anything. Just click a node to start the traversal. You can toggle between both algorithms by pressing ‘b’ BFS and ‘d’ (guess what ;-)).

BFS is much more useful than DFS in most situations. But DFS is likely to be faster, for example when you only want to modify all connected nodes in some way.

A graph-based A* pathfinder

Now for the cool part. I have created a pathfinder to demonstrate the power of the BFS algorithm. When building the graph it’s important that all arcs are bi-directional, so the pathfinder can figure out the shortest path between two locations.

I can’t explain how a pathfinder works in detail, because it’s a vast subject, but actually it’s not that different from the tile-based version, which you probably realized when looking at figure2: in a tilemap, you have 8 directions (N, S, W, E, NW, NE, SW, SE) and you go from one tile to another by adjusting the x and y tile index, in a graph you just follow all arcs of the current node. The implementation is a little chaotic, because I have to render and compute the path simultaneously, so it needs definitely some refactoring to make it clean and reusable, but for demonstration purposes it should hopefully do the work.

After finding a path through the A* algorithm, I store the nodes in a queue. You could then use a command queue so a character can follow the path. In contrast to tile-based path finding, the graph based version is lightning fast and there is still plenty room for optimizations: for example you could run a breath-first search on the graph to precompute all distances between the nodes. That’s all I have to say about graphs, next time I take an closer look at my favorite structure – linked lists!

See also:
Linked lists
The queue class
The tree class

Data structures example: the queue class

FIFO – First In, First Out

The queue class is rather basic, which saves me a lot of writing :-). The idea is simple: Think of waiting in a line at a movie theater; you get in line at the end to buy a ticket (enqueue); you reach the head of the line (peek) and finally buy the ticket and leave the line (dequeue). To use the queue class you only need three basic methods. Here are the method signatures:

var success:Boolean = myQueue.enqueue(obj);
var obj:* = myQueue.peek();
var obj:* = myQueue.dequeue();

Enqueue() obviously enqueues an item, peek() returns an instance to the front item and dequeue() removes and returns the front item at the same time. Here is a simple demonstration (first click flash to get focus):

Use key e to enqueue an item and d to dequeue the front item (blue colored circle). The numbers indicate the order of the items inside the queue. Lower numbers leave the queue before higher numbers. Also if the queue is full, all nodes are purple colored.

Size matters

A limitation of the queue class is that it has be to initialized with a fixed size. So in case the queue is full, the enqueue() method does nothing and just returns false:

var success:Boolean = myQueueInstance.enqueue(obj);

Defining a size for a new queue is also a bit different from other classes in the package because it has to be a multiple of two – this is needed for a fast bitwise modulo to speed up the array access. A queue is used so often in game programming that it should run as fast as possible, although it wasts some memory – the array might be bigger than actually needed. Instead of passing the target size directly, you pass the exponent by which 2 is raised:

var myQueueInstance:ArrayedQueue = new ArrayedQueue(4);

The queue above can store 16 items, because 2^4 (eq. 1 << 4) is 16. To be able to store 32 items, pass 5 (2^5) and so on.

Performance

If you now think “Who needs a class for it ? I keep it real and just use the native flash array methods push() and shift() !” then I have a surprise for you. Lets create a really big queue with more than 100,000 elements (131,072 to be exactly, which is 2^17). Now we enqueue items until its full, then empty it with dequeue.

The push/shift version (or unshift/pop, it doesn’t matter) takes 13 seconds(!) on my machine:

var size:int = 1 << 17;
var que:Array = [];
for (var i:int = 0; i < size; i++)
{
    que.push("foo");
}
for (var i:int = 0; i < size; i++)
{
    var result:String = que.shift();
}

Now the queue class, which takes only 40 milliseconds:

var aq:ArrayedQueue = new ArrayedQueue(17);
var success:Boolean;
do
{
    success = aq.enqueue("foo");
}
while (success);

var result:String;
do
{
    result = aq.dequeue();
}
while (result);

Here is a comparison table using a queue with a more realistic size:

As you see, the queue class grows linearly in processing time, while the array methods increases more drastically. This is because the flash player has to move a lot of data around inside the memory every time you add or remove the first element of an array (or any other in between except for the last one).

For very small queues, the class is a little bit slower. On the other hand it manages the size of the queue for you and also provides an iterator and implements the collection interface.

So this should be all you need to know about queues. Besides, the package contains also the LinkedQueue, which is based on a linked list, thus has no size limitations and performs the same no matter how many elements are stored inside it. The class itself is simple - it just defines some wrapper functions for a the linked list to provide queue-like access.

A command queue

Finally a little real-world example of what is called a command queue. I used it to create a very basic waypoint system. Click on the flash to add a waypoint, and the 'plane' (the colored circle) follows all waypoints until the queue is empty.

The sources for the flash examples can be downloaded here (Flash CS3 required). Next in the series will be the graph class, so stay tuned :-)

See also:
Linked lists
The tree class
The graph class

Data structures example: the tree class

First, I have updated the data structures source to version 0.7.3, so make sure you have the latest version. The source code for the SWFs in this post can be obtained here (Flash CS3 required).

Using the tree iterator

Before we build a tree its important to understand how the tree iterator works. Normally the iterator is used to iterate over the structure’s data – in this case the iterator additionally acts as a ‘marker’ and points to the node at which we may modify the tree.
Also, the tree iterator is somewhat special, because it allows you to iterate through the tree in two directions: horizontally and vertically. Therefore it has to manage two node references simultaneously, making it more complex than other iterators.

In the figure below, the purple colored node is the vertical iterator and is used to move up and down the tree using the treeNodeInstance.parent property, while the blue node is obviously the horizontal iterator and can only step left and right through the node’s children.

I think a simple demonstration is worth more than thousand words, so you can try it yourself by playing around with the tree using the keys below (first click the flash to get focus):

up/down, left/right: moves the vertical (V) and horizontal (H) iterator
home: deletes the whole tree
a: appends a child node to the (V) node
i: inserts a node after the (H) node
d: recursively removes all child nodes from the (V) node
r: removes the (H) node

Building a simple tree

Now let’s look how to build a tree in ActionScript. First we create the root of the tree and get an iterator pointing to this node:

var tree:TreeNode = new TreeNode("root");
var itr:TreeIterator = tree.getTreeIterator();

The root has three children, so lets add them:

for (var i:int = 0; i < 3; i++)
{
    itr.appendChild("node" + i);
}

Now the root's second child ('node1') has children by itself. To insert them, we first have to adjust the vertical iterator so it points to 'node1'. First one step to the right, then one step down the tree:

itr.nextChild();
itr.down();

Now we can add 'node3' and 'node4', this time in a reverse order:

itr.prependChild("node" + 3);
itr.prependChild("node" + 4);

The first time we add a child node to an empty node, the horizontal iterator is automatically initialized to point to the first child, which in this case is 'node4'. So to create 'node5' and 'node6' we only need to go another step down.

itr.down();
itr.appendChild("node" + 5);
itr.appendChild("node" + 6);

Finally we want to add 'node7'. Therefore we 'bubble up' the tree until we arrive at the root node, go to the rightmost child, one step down and add it:

itr.root();
itr.childEnd();
itr.down();
itr.appendChild("node" + 7);

The dump() method invoked on the root node prints out the complete tree, as you can see it matches the tree above.

[TreeNode > (root) has 3 child nodes, data=root]
+---[TreeNode > (leaf), data=node0]
+---[TreeNode >  has 2 child nodes, data=node1]
|    +---[TreeNode >  has 2 child nodes, data=node4]
|    |    +---[TreeNode > (leaf), data=node5]
|    |    +---[TreeNode > (leaf), data=node6]
|    +---[TreeNode > (leaf), data=node3]
+---[TreeNode >  has 1 child nodes, data=node2]
|    +---[TreeNode > (leaf), data=node7]

Preorder and postorder traversal

Now that you have created a tree structure, you need a way of traversing the nodes so you access the node's data. There are two common recursive algorithms for doing this. The preorder function first visits the node that is passed to the function and then loops through each child calling the preorder function on each child. The postorder on the other hand does the opposite: It visits the current node after its child nodes.
To see this in action just click a node in the demo below. The numbers indicate the order in which the nodes are visited.

The TreeNode class also supports a regular iterator using hasNext() and next(). This matches the preorder iterator, but is implemented in a non-recursive way.

See also:
Linked lists
The queue class
The graph class

as3ds

AS3 Data Structures For Game Developers (AS3DS)

• Latest Version: 1.04
• Download source: as3ds_1.04.zip, licensed under MIT

The as3ds library is no longer developed. Try ds!

Description

‘AS3 Data Structures For Game Developers’ is a package containing common data structures useful for flash game programming and application development. The project was started because I wanted a unified library which I could reuse in my games.

Design Decisions

I have tried to provide just the bare algorithms, coupled with a minimum set of methods I think are most useful to work with. Simplicity and performance were the key guidelines for the whole package. Therefore,

- all structures are untyped and can be fed with any kind of data. This makes usage more flexible and simple, since you don’t have to create special container classes which extend base classes and/or implement interfaces.

- I’m often not following strict design patterns and OOP-practices. For example, to access a classes’ property, I just define it as public instead of writing functions to read/write the property (which is also faster).

- all classes reside in a single package, simply because its hard to separate them – e.g. a linked list can bee seen as a tree, and a tree on the other side is a loose linked list.

- many structures use custom code rather that utilizing the data structure classes themselves – for example the graph structure could be implemented by using the linked list and queue classes, but a plain array works faster behind the scenes.

Collections

Almost all classes implement the Collection interface, which defines the following methods:

contains(obj:*), for checking if an item exists
clear(), for removing all items
getIterator(), for creating an iterator object to step through all items
size, the total number of items and
toArray(), which simply converts the structure into an array.

Using Iterators

Every class that implements the Collection interface is also able to create an iterator object using the getIterator() method. Once you have an iterator, you can walk through the data and read/write the values like so:

var myItr:Iterator = getIterator();
var value:*;

//read all values
while (myItr.hasNext())
{
    value = myItr.next();
}

//write new value
myItr.start();
while (myItr.hasNext())
{
    myItr.data = "newValue";
    next();
}

//the same with a for loop
for (myItr.start(); myItr.hasNext(); myItr.next())
{
    value = myItr.data;
}

Keep in mind that an iterator implies no order in which the items are processed. Some classes also support a more complex iterator like the linked list or the tree. This is necessary because you can iterate in more directions (forth, back, up, down..). You get those iterators by performing a downcast or simply calling a special method:

var listItr:ListIterator = myLinkedList.getIterator() as ListIterator;
var listItr:ListIterator = myLinkedList.getListIterator();

The Structures

Multi-Dimensional Arrays

The library contains a two-dimensional and three-dimensional array. They are both implemented by a single linear array rather than nested arrays. This is the fastest method in flash to simulate multi-dimensional arrays and outperforms the nested array method because multiple array lookups are slower compared to one lookup combined with a simple arithmetic expression (which you can also often precompute in the outer loop). The most obvious application would be a tilemap in 2d or a layered tilemap in 3d.

Queue

This is also called a FIFO structure (First In – First Out). The queue comes in two variations, which have the same methods, but differ in their implementations: There is the arrayed queue, which obviously uses an array internally, and the linked queue, which is build upon a linked list. They are both very similar, except that the arrayed version has a fixed size and is faster.
A common application would be a command queue – imagine you have a unit in a strategy game and apply many commands which the unit should follow. All commands are enqueued and afterwards dequeued and processed in order.

Stack

Also commonly know as a FILO structure (First In – Last Out). Like the queue, this comes in two flavors: arrayed and linked. A stack is often not used directly, but a very important concept in programming. Please note, that a queue and a stack are not real structures, because they just define how data is accessed rather then stored.

Tree

A node-based structure. Every tree starts from a single node, called the root node. The root node can contain any number of child nodes, and every child node can again contain children. A tree node with no children is called a leaf node. In fact if you draw the nodes of a tree it looking like a real tree with branches. The AS3 display architecture is also a tree structure, so you could use this to manage your display objects and update them by traversing through the tree. Also, this is useful for decision trees, BVHs, storing a plot line or storing data recursively by applying the composite pattern.

Binary Tree

This is just a specialized kind of tree where each node is only allowed to have up to two children, called the left and right node. Binary trees are very often used for parsing input data, for example arithmetic expressions or when building a scripting system.

Binary Search Tree (BST) and Hash Table

Both structures store data that can be retrieved quickly by using a key. The method however differers greatly: The BST uses a recursive approach to split up large amounts of data into smaller sets. A hash table stores sparse key-based data using a hash-key in a small amount of space.

Linked Lists

A linked list is similar to an array. The main difference is that in an array, each cell contains just the data and is accessed by an index. A linked list consists of several node objects, which in addition to storing the data, manage a reference to the next node (singly linked) or to the next and previous node (doubly linked) in the list. Think of it as a more natural approach to work with sequential data.
Other benefits are that you can insert and remove data quickly by just calling the appropriate method on the node itself – you don’t have to manage array indexes. Also in AS3 object access is faster than array access, so it competes very well in terms of performance when iterating over the list.

Heap and Priority Queue

A Heap is a special kind of binary tree in which every node is bigger than its child nodes. Whatever you throw into a heap, it’s automatically sorted so the item with the ‘most significant’ value (depending on the comparison function) is always the front item. A priority queue is build upon the heap structure, and can manage prioritized data – which can be used in limitless ways.

Graph

A graph is a loose node-based structure. Nodes are connected with arcs, and every node can point to any other node. They can also point to each other creating a bi-directional connection. It is essential for path finding, AI, soft-body dynamics with mass-springs systems and a lot more.

Bit Vector

A bit vector is some kind of array in which you can store boolean values (true/false – 1/0) as close as possible without wasting memory. I currently can’t think of a reasonable application, because usually you should have enough memory – but it’s nice to have because it shows basic bit masking operations.