Creation of new data types in AS3: Linked List
In computer programming, a data type (or datatype) is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, stating the possible values for that type, the operations that can be done on that type, and the way the values of that type are stored. (source: Wikipedia).
Obviously any language is capable to create new data structures. I did not find any complete AS3 complete tutorial to create a new data type from scratch with AS3, so I am writing it by myself.
We are going to define a simple linked list data type.
A linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
(source and image: Wikipedia. Yes, I made a donation so I feel free to copy/paste :)).
In this example, we are going to reproduce the same linked list you see in the picture. Usually the “records” Wikipedia is talking about are called “nodes”, so we’ll define a node datatype.
This is the class, in a file called node.as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | package triqui{ public class node { public var node_data:*; public var next_node:node; public function node(node_content:*) { node_data=node_content; next_node=null; } public function get_node_data():* { return node_data; } public function insert_prev(n:node):void { n.next_node=this; } public function insert_next(n:node):void { next_node=n; } public function get_next_node():node { return next_node; } } } |
Line 1: package definition. Notice there is a name after the package to preserve class name uniqueness. Whithout boring you with useless theory, just remember that since package name is triqui, you will need to save it in a triqui folder in the same path of you main .fla file. Refer to the downloadable source code available at the end of the post for a concrete example.
Line 2: definition of the class. It’s called node.
Line 3: node_data is the container of the information we need to store. Referring to Wikipedia example, the numbers 12, 99 and 37. Giving * as data type makes it capable of having any data type, such as strings, arrays, integers or even other nodes.
Line 4: next_node is the link to the next node in the list and obviously is a node type.
Line 5: the main function, or constructor. It wants the content of the node (12, 99 or37 in the example) as argument. Notice the type is * because we said it will accept any kind of data types.
Line 6: assigning node_content (the constructor argument) value to node_data (the information container of the node).
Line 7: assigning null to next_node. The node will not link any other node.
Line 9: function to retrieve the information stored in a node (notice the *: you should know why).
Line 10: simply returning the content of node_data variable.
Line 12: function to insert the previous node to a node, that is the node in the argument will link the current node.
Line 13: assigning the current node to next_node variable of the node passed in the argument.
Line 15: function to insert the next node to a node, that is the node in the argument will be linked by the current node.
Line 16: assigning the node passed as argument to next_node variable
Line 18: function to get the next node of a node. Returns (obviously) a node.
Line 19: returning next_node content
And this is an example of the class at work… in a file called datatype.as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | package { import flash.display.Sprite; import triqui.node; public class datatype extends Sprite { public function datatype() { var n1:node=new node(12); var n2:node=new node(99); var n3:node=new node(37); n2.insert_prev(n1); n2.insert_next(n3); trace(n1.get_next_node().get_next_node().get_node_data()); } } } |
Line 3: importing node library
Lines 6-8: creating the three nodes as in the example
Line 9: setting n1 node as the previous of n2
Line 10: setting n3 node as the next of n2
Line 11: This will output the content of n3 node starting from n1… 37.
During next days we’ll see various more complex data types such as double linked lists and trees.
(4 votes, average: 5.00 out of 5)
Loading ...
They can be easily customized to meet the unique requirements of your project.
This post has 14 comments
Rolpege
What’s the difference between a data type or a normal class in Actionscript 3? I mean, is there a difference in the code or simply it’s our use of it? (sorry if I don’t explain myself well :P)
Rich Rodecker
Nice tutorial, but lowercase class names…argh!
fudo
I think ‘data structure’ is better name than ‘data type’.
Dog
A datatype is different because it is used to hold and manipulate data in a specific way. For example, your “normal use of a class” is probably something like Enemy or Hero or something, a data type is something that will hold the data… for example a Line class which will hold two points, can calculate slope, y-intercept, perpendicular line, etc.
Andreas Renberg
Do you think you could provide a few examples where Linked Lists would be useful in actual application?
vega
@Andreas
You can use a linked list interchangable with arrays (atleast in all cases i can think of atm – if it makes sense is another question ^^).
Both options got pros/cons tho.
performance diff:
Linked lists shine in random inclusion/deletion of elemts – its a constant time to do so.
Array shine in directly accessing specific elements.
memory:
You dont need to know the size/memory of the list at the moment u create it.
Harack
Linked lists are probably most commonly used in flash in Box2d, you get a list of the bodies or fixtures or contacts and which has a getNext();
I think your implementation of a SLL (singly linked list) is nice however you need to keep track of the first and last node (head and tail) to use them efficiently. Well at least the first node.
In all i would like to see a follow up tutorial as the implementation you are showing everyone here has no real benefit. Could show all the insertion methods (insert to first, last or in the middle) along with deletion methods.
Maybe even do a doubly linked list tutorial which is essentially same yet each node has a previous and next pointer.
-Harack
Weekly Shared Items – 6. September, 2010 | TOXIN LABS - weblog of a german design student from wuerzburg
[...] Creation of new data types in AS3: Linked List [...]
Illniyar
Not sure if you are aware, however there is a beautifully implemented library called ds (formerly “AS3 Data Structures For Game Developers”), that features most of the common datatypes.
Because it is implemented in HaXe, it also uses some amazing Alchemy features, which makes the implementation lightning fast, as well as allowing such features as Generics and low memory usages (you actually have a bit and Byte implementation I believe).
You can find it here:
http://code.google.com/p/polygonal/wiki/DataStructures
Flo - derhess.de
For link lists. You should check the great library AS3 Data Structure
http://lab.polygonal.de/ds/
Alex Nino (yoambulante)
Hi, this is really interesting, nice list, I’ve been facing similar situations coding AS3 where I couldn’t find a proper way of simulating data types, find a proper dimension for variables, objects, reuse memory blocks… there is something that I used to use a lot in c++ and it’s the union (I have no clue how to simulate that behaviour in AS3)…
union {
float f;
int i;
} tmp;
my closer approach was by using a ByteArray writing and reading it’s same block from memory, which is something extremely slow. I would like to make a faster Math.sqrt function in AS3, but the approach/idea/algorithm in C++ which works perfect uses union :(
Anyway dude, I did like this article, it is really cool but unfortunately this approach is a bit slow in terms of CPU time (performance), especially using that wild card :* where the flash player doesn’t have a way to allocate properly the data type in memory but we can use this most of the times if our application doesn’t require intensive processes, thanks for writing, cheers!
Test — GuruWatch On The Internet Marketing Experts
[...] Creation of new data types in AS3: Linked List – Emanuele Feronato [...]
Hardik
u r not geek,ur awesome programmer.
Hank
Great article explaining LinkedList in as3, however, I still don’t see the benefit of it over arrays, when is it more useful to use LinkedList rather than arrays?