Last time I began covering linked lists in AS3. As anyone who has ever taken a data structures class can tell you, this is definitely a core data structure. As such, it has numerous benefits compared to other single-dimensional data structures like arrays and hash tables. The Array class in AS3 is far from a C/C++ array, which is simply a contiguous block of memory. AS3’s Array class blurs the lines between arrays, linked lists, and hash tables. So as I implement a linked list class in AS3 it is quite interesting to see how the normal pros and cons change. I’ve expanded on the LinkedList class I started last week and done some more preliminary performance testing. Read on to see the updates.

Since last time I’ve finished implementing LinkedList‘s API so it is now feature-complete. I have not begun any serious optimization though as correctness must always come first. Along with this feature completeness I have updated the performance testing app to test all of the functionality. In the process I changed the output formatting to save on screen space. More on the results later. For now, let’s look at the updated code:

LinkedListNode

The only change here is the addition of a class comment.

package
{
	/**
	*   A node in a linked list. Its purpose is to hold the data in the
	*   node as well as links to the previous and next nodes.
	*   @author Jackson Dunstan
	*/
	public class LinkedListNode
	{
		public var next:LinkedListNode;
		public var prev:LinkedListNode;
		public var data:*;
		public function LinkedListNode(data:*=undefined)
		{
			this.data = data;
		}
	}
}
LinkedList

As mentioned before, the API is now complete. One notable performance optimization is the caching of the length. I’ve also added a class comment.

package
{
	/**
	*   A linked list, which is a single-dimensional chain of objects called
	*   nodes. This implementation is doubly-linked, so each node has a link
	*   to the next and previous node. It's API is designed to mimic that of
	*   the top-level Array class.
	*   @author Jackson Dunstan
	*/
	public class LinkedList
	{
		public var head:LinkedListNode;
		public var tail:LinkedListNode;
		public var length:int;
 
		public function LinkedList(numElements:uint=0)
		{
			this.length = numElements;
			for (var i:int = 0; i < numElements; ++i)
			{
				push(undefined);
			}
		}
 
 		/**
 		*   Equivalent to the Array(...values) constructor
 		*   @param values Values to add to the list
 		*   @return A newly-created list with the given values
 		*/
		public static function fromValues(...values): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			for each (var val:* in values)
			{
				ret.push(val);
			}
			return ret;
		}
 
		/**
		*   Equivalent to the Array [] operator
		*   @param index Index of the element to get
		*   @return The element at the given index
		*/
		public function elementAt(index:int): *
		{
			if (index < 0)
			{
				throw new TypeError("Error #2007");
			}
			else if (index >= this.length)
			{
				return undefined;
			}
			else
			{
				var halfLength:int = this.length >> 1;
				var cur:LinkedListNode;
				var i:int;
				// Element is in the first half, start at beginning
				if (index < halfLength)
				{
					i = 0;
					for (cur = this.head; cur; cur = cur.next)
					{
						if (i == index)
						{
							return cur.data;
						}
						i++;
					}
				}
				// Element is in the second half, start at the end
				else
				{
					i = this.length-1;
					for (cur = this.tail; cur; cur = cur.prev)
					{
						if (i == index)
						{
							return cur.data;
						}
						i--;
					}
				}
			}
		}
 
		public function concat(...args): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				ret.push(cur.data);
			}
			var list:LinkedList;
			for each (var arg:* in args)
			{
				if (arg is LinkedList)
				{
					list = arg;
					for (cur = list.head; cur; cur = cur.next)
					{
						ret.push(cur.data);
					}
				}
				else
				{
					ret.push(arg);
				}
			}
			return ret;
		}
 
		public function every(callback:Function, thisObject:*=null): Boolean
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (!callback.call(thisObject, cur.data, index, this))
				{
					return false;
				}
				index++;
			}
			return true;
		}
 
		public function filter(callback:Function, thisObject:*=null): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (callback.call(thisObject, cur.data, index, this))
				{
					ret.push(cur.data);
				}
				index++;
			}
			return ret;
		}
 
		public function forEach(callback:Function, thisObject:*=null): void
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				callback.call(thisObject, cur.data, index, this);
				index++;
			}
		}
 
		public function indexOf(searchElement:*, fromIndex:int=0): int
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur && index < fromIndex; cur = cur.next)
			{
				index++;
			}
			for (; cur; cur = cur.next)
			{
				if (cur.data == searchElement)
				{
					return index;
				}
			}
			return -1;
		}
 
		public function join(sep:*=","): String
		{
			var ret:String = "";
			for (var curNode:LinkedListNode = this.head; curNode; curNode = curNode.next)
			{
				ret += curNode.data + sep;
			}
			return ret.substr(0, ret.length-sep.length);
		}
 
		public function lastIndexOf(searchElement:*, fromIndex:int=0x7fffffff): int
		{
			var index:int = this.length-1;
			for (var cur:LinkedListNode = this.tail; cur && index > fromIndex; cur = cur.prev)
			{
				index--;
			}
			for (; cur; cur = cur.prev)
			{
				if (cur.data == searchElement)
				{
					return index;
				}
				index--;
			}
			return -1;
		}
 
		public function map(callback:Function, thisObject:*=null): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				ret.push(callback.call(thisObject, cur.data, index, this));
				index++;
			}
			return ret;
		}
 
		public function pop(): *
		{
			if (this.tail)
			{
				var ret:* = this.tail.data;
				this.tail = this.tail.prev;
				this.length--;
				return ret;
			}
			else
			{
				return undefined;
			}
		}
 
		public function push(...args): void
		{
			var numArgs:int = args.length;
			var arg:*;
			for (var i:int = 0; i < numArgs; ++i)
			{
				arg = args[i];
				var newNode:LinkedListNode = new LinkedListNode(arg);
				if (this.tail)
				{
					this.tail.next = newNode;
					this.tail.next.prev = this.tail;
					this.tail = this.tail.next;
				}
				else
				{
					this.head = this.tail = newNode;
				}
			}
			this.length += numArgs;
		}
 
		public function reverse(): LinkedList
		{
			var front:LinkedListNode = this.head;
			var back:LinkedListNode = this.tail;
			var temp:*;
			while (front != back && back.prev != front)
			{
				temp = front.data;
				front.data = back.data;
				back.data = temp;
 
				front = front.next;
				back = back.prev;
			}
 
			return this;
		}
 
		public function shift(): *
		{
			if (this.head)
			{
				var ret:* = this.head.data;
				this.head = this.head.next;
				this.length--;
				return ret;
			}
			else
			{
				return undefined;
			}
		}
 
		public function slice(startIndex:int=0, endIndex:int=16777215): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var cur:LinkedListNode = this.head;
			var i:int;
			for (i = 0; i < startIndex && cur; ++i)
			{
				cur = cur.next;
			}
			for (; i < endIndex && cur; ++i)
			{
				ret.push(cur.data);
				cur = cur.next;
			}
			return ret;
		}
 
		public function some(callback:Function, thisObject:*=null): Boolean
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (callback.call(thisObject, cur.data, index, this))
				{
					return true;
				}
				index++;
			}
			return false;
		}
 
		public function sort(...args): LinkedList
		{
			var arr:Array = toArray();
			return fromArray(arr.sort.apply(arr, args));
		}
 
		public function sortOn(fieldName:Object, options:Object=null): LinkedList
		{
			var arr:Array = toArray();
			return fromArray(arr.sortOn.call(arr, fieldName, options));
		}
 
		public function splice(startIndex:int, deleteCount:int, ...values): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var cur:LinkedListNode = this.head;
			var endIndex:int = startIndex + deleteCount;
			var i:int;
			for (i = 0; i < startIndex && cur; ++i)
			{
				cur = cur.next;
			}
			for (; i < endIndex && cur; ++i)
			{
				ret.push(cur.data);
				cur.next = cur.next.next;
				cur.next.prev = cur;
				cur = cur.next;
			}
			this.length -= deleteCount;
			return ret;
		}
 
		public function toString(): String
		{
			return join();
		}
 
		public function toLocaleString(): String
		{
			return join();
		}
 
		public function unshift(...args): void
		{
			var numArgs:int = args.length;
			var arg:*;
			for (var i:int = 0; i < numArgs; ++i)
			{
				arg = args[i];
				var newNode:LinkedListNode = new LinkedListNode(arg);
				if (this.head)
				{
					this.head.prev = newNode;
					this.head.prev.next = this.head;
					this.head = this.head.prev;
				}
				else
				{
					this.head = this.tail = newNode;
				}
			}
			this.length += numArgs;
		}
 
		private function toArray(): Array
		{
			var ret:Array = [];
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				ret.push(cur.data);
			}
			return ret;
		}
 
		private function fromArray(arr:Array): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			for each (var val:* in arr)
			{
				ret.push(val);
			}
			return ret;
		}
	}
}
LinkedListPerformance

The performance app is updated for the new API features and for screen space frugality

package
{
	import flash.display.*;
	import flash.events.*;
	import flash.text.*;
	import flash.utils.*;
 
	/**
	*   An app to test linked list performance
	*   @author Jackson Dunstan
	*/
	public class LinkedListPerformance extends Sprite
	{
		public function LinkedListPerformance()
		{
			// Setup logger
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
			function log(msg:*): void { logger.appendText(msg); }
 
			// Properties
			const VALUE:Object = {val:33};
			const ALTERNATE_VALUE:Object = {val:44};
			const SIZE:int = 10000;
			const SORT_ON_PROP_NAME:String = "val";
			const ELEMENTATINDEX:int = SIZE>>1;
			const SPLICE_START:int = 0;
			const SLICE_START:int = 00;
			const SLICE_END:int = SIZE;
 
			// Iterations
			const TRAVERSES:int = 100;
			const ELEMENTATS:int = 100000;
			const CONCATS:int = 10;
			const EVERYS:int = 10;
			const FILTERS:int = 10;
			const FOREACHS:int = 10;
			const INDEXOFS:int = 100;
			const JOINS:int = 1;
			const MAPS:int = 1;
			const PUSHPOPS:int = 100000;
			const REVERSES:int = 100;
			const SLICES:int = 100;
			const SOMES:int = 1;
			const SORTS:int = 1;
			const SORTONS:int = 1;
			const SPLICES:int = 10000;
			const UNSHIFTSHIFTS:int = 10000;
 
			// Test variables
			var array:Array;
			var list:LinkedList;
			var beforeTime:int;
			var curNode:LinkedListNode;
			var i:int;
			var j:int;
 
			// Populate the array
			array = [];
			for (i = 0; i < SIZE; ++i)
			{
				array[i] = VALUE;
			}
 
			// Populate the list
			list = new LinkedList();
			for (i = 0; i < SIZE; ++i)
			{
				list.push(VALUE);
			}
 
			log("traverse (" + TRAVERSES + " operations): ");
 
			beforeTime = getTimer();
			for (j = 0; j < TRAVERSES; ++j)
			{
				for (i = 0; i < SIZE; ++i)
				{
					array[i];
				}
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (j = 0; j < TRAVERSES; ++j)
			{
				for (curNode = list.head; curNode; curNode = curNode.next)
				{
					curNode.data;
				}
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("elementAt/[] (" + ELEMENTATS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < ELEMENTATS; ++i)
			{
				array[ELEMENTATINDEX];
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < ELEMENTATS; ++i)
			{
				list.elementAt(ELEMENTATINDEX);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("concat (" + CONCATS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < CONCATS; ++i)
			{
				array.concat(array);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < CONCATS; ++i)
			{
				list.concat(list);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("every (" + EVERYS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < EVERYS; ++i)
			{
				array.every(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < EVERYS; ++i)
			{
				list.every(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("filter (" + FILTERS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < FILTERS; ++i)
			{
				array.filter(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < FILTERS; ++i)
			{
				list.filter(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("forEach (" + FOREACHS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < FOREACHS; ++i)
			{
				array.forEach(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < FOREACHS; ++i)
			{
				list.forEach(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("indexOf (" + INDEXOFS + " operations): ");
 
			array[SIZE-1] = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				array.indexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
			array[SIZE-1] = VALUE;
 
			list.tail.data = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				list.indexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
			list.tail.data = VALUE;
 
			log("join (" + JOINS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < JOINS; ++i)
			{
				array.join();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < JOINS; ++i)
			{
				list.join();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("lastIndexOf (" + INDEXOFS + " operations): ");
 
			array[0] = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				array.lastIndexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
			array[0] = VALUE;
 
			list.head.data = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				list.lastIndexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
			list.head.data = VALUE;
 
			log("map (" + MAPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < MAPS; ++i)
			{
				array.map(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < MAPS; ++i)
			{
				list.map(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("pop (" + PUSHPOPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				array.pop();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				list.pop();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("push (" + PUSHPOPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				array.push(VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				list.push(VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("reverse (" + REVERSES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < REVERSES; ++i)
			{
				array.reverse();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < REVERSES; ++i)
			{
				list.reverse();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("shift (" + UNSHIFTSHIFTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				array.shift();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				list.shift();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("slice (" + SLICES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SLICES; ++i)
			{
				array.slice(SLICE_START, SLICE_END);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SLICES; ++i)
			{
				list.slice(SLICE_START, SLICE_END);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("some (" + SOMES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SOMES; ++i)
			{
				array.some(arrayCallbackFalse);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SOMES; ++i)
			{
				list.some(listCallbackFalse);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("sort (" + SORTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTS; ++i)
			{
				array.sort();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTS; ++i)
			{
				list.sort();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("sortOn (" + SORTONS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTONS; ++i)
			{
				array.sortOn(SORT_ON_PROP_NAME);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTONS; ++i)
			{
				list.sortOn(SORT_ON_PROP_NAME);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("splice (" + SPLICES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SPLICES; ++i)
			{
				array.splice(SPLICE_START, 5, VALUE, VALUE, VALUE, VALUE, VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SPLICES; ++i)
			{
				list.splice(SPLICE_START, 5, VALUE, VALUE, VALUE, VALUE, VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("unshift (" + UNSHIFTSHIFTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				array.unshift(VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				list.unshift(VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
		}
 
		private function arrayCallbackTrue(cur:*, index:int, list:Array): Boolean
		{
			return true;
		}
 
		private function listCallbackTrue(cur:*, index:int, list:LinkedList): Boolean
		{
			return true;
		}
 
		private function arrayCallbackFalse(cur:*, index:int, list:Array): Boolean
		{
			return false;
		}
 
		private function listCallbackFalse(cur:*, index:int, list:LinkedList): Boolean
		{
			return false;
		}
	}
}
Results
Function Operations 2.2 Ghz Intel Core 2 Duo, 2 GB RAM, Mac OS X 10.6
traverse 100 12 array/13 list
elementAt/[] 100000 1 array/2614 list
concat 10 4 array/176 list
every 10 11 array/15 list
filter 10 17 array/104 list
forEach 10 12 array/14 list
indexOf 100 15 array/21 list
join 1 24 array/27 list
lastIndexOf 100 15 array/21 list
map 1 2 array/12 list
pop 100000 1 array/5 list
push 100000 8 array/85 list
reverse 100 22 array/140 list
shift 10000 332 array/1 list
slice 100 47 array/908 list
some 1 10 array/14 list
sort 1 727 array/848 list
sortOn 1 172 array/254 list
splice 10000 20 array/63 list
unshift 10000 769 array/15 list

LinkList‘s losing streak continues! It comes close in a couple of cases (eg. traverse, every, forEach, indexOf), but totally falls apart in others (eg. elementAt/[], concat, reverse, slice). In fact, it’s only shift and unshift that are faster, just as we saw last week. Next time we’ll see how this changes as some optimizations are applied to it. Stay tuned!