| Ship builders know
that all they need to do in order to make a ship float is have
it displace the ship's weight in water—that and not have
any holes.
Now, a big metal box would satisfy this rule just fine. The problem
is, although a metal box would float just fine, it doesn't exactly
make an efficient ship. That is to say, there's more to designing
a good ship than just making sure it floats, and there's more
to designing a good data structure than just making sure it holds
data.
Arrays: not just simple lists
The most basic type of data structure, and the first one that
most programmers learn, is the array. Arrays are all
about lists. Anytime you need to store a list of data in a single
structure but still want to be able to manipulate the individual
pieces of data, you use an array.
In most other programming languages an array is just a list of
values stored at numeric indices, but in ActionScript they are
much more. For example, in most other languages an array is defined
to have a certain size when it is created. After that point the
number of "slots" in the array cannot be modified. If
you need a bigger or smaller array you have to create a new one
and copy the contents over. In Macromedia Flash, however, arrays
can grow and shrink as needed—which obviously simplifies
many things. You can still "suggest" a size to an array
in Macromedia Flash but you're never tied to that value.
Another big difference between ActionScript arrays and other
arrays is that ActionScript allows you to place any data type
you like in the array. For example, this code is perfectly legal:
myArray = new Array();
myArray[0] = 123;
myArray[1] = "this is a string";
myArray[2] = false;
This wouldn't be legal in most other languages because arrays
are usually only allowed to hold a single type of data type—numbers,
strings, Booleans, and so on.
Finally, here's one of the biggest differences between arrays
in ActionScript and those in other languages: ActionScript arrays
are actual objects and, as such, they have their own methods.
Some of these methods—like push,
pop, shift,
and unshift—allow ActionScript
arrays to act like entirely other types of data structures: namely,
stacks and queues.
Both of these data structures work like arrays, in that they
store lists of data, but they limit how you can add and remove
data from them. In both cases you can only add or remove a single
element from the list at a time. For example, a stack acts like
a Pez dispenser—the last candy you added is the first one
removed. If you want to use an array in ActionScript like a stack,
don't use array syntax ([]) to access it. Instead, use the push
method to add items to the array and the pop
method to remove them. Stacks are particularly good for holding
"undo lists."
Queues, on the other hand, are what is called a first-in-first-out
(FIFO) structure. Just like a line at the movie theater, the first
person in line is the first person to get in. If you want to use
an array as a queue, don't use array syntax ([]). Instead, use
the push method to add data
and the shift method to remove
data. (Alternately, you could use unshift
to add and pop to remove. It
doesn't matter; just be consistent.) Queues are well-suited for
any part of a program where there is some sort of limit on resources,
so a "line" needs to form.
Latchkey data: associative arrays
As you can see, arrays in ActionScript are quite powerful beasts.
The biggest problem with arrays is that because they are so powerful,
many developers never think of using anything else. Besides this
simple fact, an array is great for looping through data inside
itself but poor at finding data stored within itself. Unless the
data stored inside an array is sorted, you may have to check each
and every element in the array to find the data you want. Obviously,
this isn't terribly efficient.
It turns out that ActionScript lets you turn any object into
another type of array, one that's much more suited to finding
data. This type of array, known as an associative array
or dictionary, is based on the idea of keys. That is,
each element in the array has a unique key that you use to access
that piece of data (rather than the numerical index you use in
normal arrays).
Associative arrays are extremely easy to create and use in ActionScript
because they are based on intrinsic features of the language.
The first feature is that you can add properties to objects, and
remove them, whenever you'd like. So doing something like this
is perfectly legal:
foo = new Object();
foo.a = 12;
foo.b = "some text";
The second feature of ActionScript that makes associative arrays
so simple to implement is the fact that you can access the properties
of an object using two different syntaxes—dot syntax and
array syntax. This code is functionally identical to the code
just above:
foo = new Object();
foo["a"] = 12;
foo["b"] = "some text";
Thus you can treat any object you want as an associative array
by using properties of the object as keys. However, if you are
planning to do this you probably will want to just use an Object
object for the job (like the code above). Because objects of this
type are essentially empty, you can add any properties you want
without fear of overwriting anything important.
Associative arrays are perfect for any code where it's important
to be able to access individually elements quickly. For example,
I often use an associative array to hold the "state"
information about an application (the current tool selected, the
current element in use, the user name, and so on).
Hot-potato data: linked lists
Another problem with arrays is the fact that you can't just remove
an element in the middle of one. If you do, you'll just have an
empty hole and the size of the array will remain the same. To
correct this you'd have to shift all the elements to take up the
slack. This isn't exactly efficient. If you need the looping capabilities
of an array, but are going to need to add and remove elements,
then you want to create what is known as a linked list.
Unlike arrays and associative arrays, a linked list actually
consists of a number of objects. In fact, each element in a linked
list is its own object, known as a node. Each node contains
at least two pieces of information: The first is the actual data
stored in the node; the second is a reference to the next node
in the list. It's common to have a third node that points back
to the previous node in the list. This turns the data structure
into what's known as a doubly-linked list. If you connect
the front and end of the list so that the first node points to
the last node, and vice-versa, then you have a circular-linked
list:
fooNode = new Object();
fooNode.data = "some data";
barNode = new Object();
barNode.data = 123;
wozNode = new Object();
wozNode.data = false;
fooNode.prev = wozNode;
fooNode.next = barNode;
barNode.prev = fooNode;
barNode.next = wozNode;
wozNode.prev = barNode;
wozNode.next = fooNode;
rootNode = fooNode;
tempNode = rootNode;
do{
trace(tempNode.data);
tempNode = tempNode.next;
} while (tempNode != rootNode);
As you can see, linked lists are sort of like Tinker Toys: It's
the connections between one node and the other that make up the
actual structure. You can remove any node you like and patch up
its neighbor's back and next references to cover the "hole."
Anytime you need to add and remove data many times, and loop through
the data, think about creating a linked list.
Hopefully this article has gotten you thinking more about data
structures in ActionScript. There are dozens of other types of
data structures out there, such as trees, priority queues, and
graphs. Each of these types has its own specific purpose so the
more you know, the better the chances that you'll end up using
one that's efficient for your needs.
If you want to know more about data structures in ActionScript
you may want to check out a new book that I coauthored, called
Object-Oriented
Programming with ActionScript. There's a whole chapter
devoted to data structures. |
