Linked Lists: Part 2 « JacksonDunstan.com

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!

This entry was posted on Monday, December 21st, 2009 and is filed under AS3. You can follow any responses to this entry through RSS 2.0. Use <pre lang="actionscript3">CODE<pre> for code. You can leave a response, or trackback from your own site.

JacksonDunstan.com

Mastering AS3