Linked List vs. Array

JavaScript performance comparison

Test case created by Ryan Lynd

Preparation code

<script>
/**
 * Simple (generic) entity class
 */

var Entity = function( ) {
        var _self = this;

        this.pos = { x:0, y:0 };

        this.update = function() {
                // bad heavy arithmetic for the sake of testing
                _self.pos.x = Math.round( Math.sin( Math.random() * 100 % 23 + 14 / 32 | 0 ) );
                _self.pos.y = Math.round( Math.sin( Math.random() * 100 % 42 - 67 / 98 | 0 ) );
        };

        this.draw = function() {
                //console.log(42);
        }
}

/**
 * Turns any class into a simple Linked-List and returns the list.
 * @param  {Object} Clazz Target Class
 * @return {LinkedList}       instance of the list
 */

LinkedList = function( Clazz ) {
        // add linked list assoc. properties to class
        Clazz.prototype.__next__ = null;

        this.head = this.tail = new Clazz();
};

LinkedList.prototype.add = function( Clazz ) {
        var node = new Clazz();
        this.tail.__next__ = node;
        this.tail = node;
}

LinkedList.prototype.each = function( callback ) {
        var node = this.head.__next__;
        while ( node !== null ) {
                callback( node );
                node = node.__next__;
        }
}

// testing functions

// iterate through the list and call update() + draw() on each node
function iterateLinkedList( list ) {

        var updateNode = function( node ){
                node.update();
        }

        var drawNode = function( node ){
                node.draw();
        }

        list.each( updateNode );

        list.each( drawNode );
}


// iterate through the array and call update() + draw() on each object
function iterateArray( arr ) {
        var i, len = arr.length;

        i = len;
        while(i--){
                arr[i].update();
        }

        i = len;
        while(i--){
                arr[i].draw();
        }

}


function populateArray(amount) {
        ar = new Array();
        for (i = 0; i < amount; i++) {
                ar.push( new Entity() );
        }
        return ar;
}

function populateLinkedList(amount) {
        ll = new LinkedList( Entity );
        for (i = 0; i < amount; i++) {
                ll.add( Entity );
        }
        return ll;
}


array100 = populateArray( 100 );
list100 = populateLinkedList( 100 );
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
update/draw objcts in Array
iterateArray( array100 );
pending…
update/draw objects in Linked List
iterateLinkedList( list100 );
pending…
add 100 objects to Array
populateArray( 100 );
pending…
add 100 objects to Linked List
populateLinkedList( 100 );
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment