ActionScript 3.0 Design Patterns

Recursive Linked List

To understand Skip Lists we need to understand Linked Lists. Linked lists are nothing new to programming, dating back to the early days of digital computing in the 1950′s. I found an old Macromedia DevNet article by Branden Hall on creating linked lists in an earlier version of ActionScript. So while nothing new to programming, they are often overlooked.

Why Linked Lists?

Before we look closely at linked lists, we should briefly discuss their utility. After all, we’ve got Arrays (and Vectors) for storing data. Further, arrays are easy to sort, and ActionScript 3.0 structures are available to iterate through them.

One problem with arrays is that it’s difficult to insert elements between existing elements. Using linked lists, you can put the data in any order at all, including between existing nodes (elements). The linkage is not the order of the array because arrays have no linkage between elements.

In its most basic form, a linked list is a series of nodes with each node having a value and a reference to the next node. The value can be anything and the link must be to the next node using whatever sequence the programmer wants. Some linked lists have references to the previous and next node and some are even circular—the last node links to the first node. However, I’m going to stick with the singly-linked linear lists. First it is a recursive data structure, and second it is useful for what we’ll be doing with skip lists. Figure 1 shows this kind of list with its various parts:

Figure 1: Linked list and its components

In looking at the linked list, the most important aspect of such a list is the Next Field. The Next Field is a pointer to the linked node—the next node. Remember, a pointer is simply a reference to another object. With linked lists, that makes all the different in the world. Array elements are linked to nothing. (Numeric or string keys are not pointers so much as they are labels.)

Before going on to create an example of a linked list in ActionScript 3.0, we need to consider node insertion. As noted above, inserting an element in an array can be tricky. However, you may be wondering about how easy it is to insert a node between existing nodes. Wouldn’t the pointer from the node before the new node have to be changed? That is, if Node 5a is inserted between Nodes 5 and 6, wouldn’t we have to change the pointer in Node 5 to Node 5a? Yes. Node 5′s pointer would have to be changed from Node 6 to Node 5a. Node 5a would point to Node 6.

An ActionScript 3.0 Linked List

Without further ado, let’s whip up a linked list in ActionScirpt 3.0. The contents of the list (placed in the data field) can be anything, but I decided to use strings sequentially listing the first six letters of the Greek alphabet. (It rhymes with “Geek,” and I couldn’t resist.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package
{
	import flash.display.Sprite;
 
	public class LinkedList extends Sprite
	{
		private var alphaNode:Object=new Object();
		private var betaNode:Object=new Object();
		private var gammaNode:Object=new Object();
		private var deltaNode:Object=new Object();
		private var epsilonNode:Object=new Object();
		private var zetaNode:Object=new Object();
		private var nullNode:Object=new Object();
		private var recursiveNode:Object=new Object();
 
		public function LinkedList()
		{
			alphaNode.contents="alpha";
			betaNode.contents="beta";
			gammaNode.contents="gamma";
			deltaNode.contents="delta";
			epsilonNode.contents="epsilon";
			zetaNode.contents="zeta";
 
			alphaNode.nextUp=betaNode;
			betaNode.nextUp=gammaNode;
			gammaNode.nextUp=deltaNode;
			deltaNode.nextUp=epsilonNode;
			epsilonNode.nextUp=zetaNode;
			zetaNode.nextUp=nullNode;
 
			recursiveNode=alphaNode;
 
			while (recursiveNode != nullNode)
			{
				trace(recursiveNode.contents);
				recursiveNode=recursiveNode.nextUp;
			}
		}
	}
}

Your output will be:
alpha
beta
gamma
delta
epsilon
zeta

At first glance, it looks like we just iterated through a loop, and indeed we did. However, instead of using an iterative sequence, we used the linked list pointers to go from one node to the next. Each of the nodes was recursively linked to the next node. The sequence began with the Head Node, with an object (recursiveNode) referencing itself through the entire list using the nextUp property to traverse the list. (The loop just served as an engine.) Further, you can see that our output is not ordered alphabetically—at least in non-Greek.

Reader Challenge: Ordering the Linked List

The first task is to figure out where the output is unordered as far as ActionScirpt 3.0 is concerned. The next task to to change the pointers so that the output is ordered. Use the Comment section to show your solution. If you can do that, you will be better prepared to understand how linked lists are used in skip lists in an upcoming post.

If you are interested in linked lists, check out this Stanford University lecture on the topic. It served as a useful guide in preparing this post and has everything you’ll ever want to know about linked lists.

Related posts:

1. A Funny Thing Happened on the way to Skip Lists: The ActionScript 3.0 Binary Search Algorithm