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:
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:
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.
