usage of linked list vs array (v12)

Revision 12 of this benchmark created on

Description

Minimalistic implementation of a linked list, used to compare the performance of population and iteration a linked list implementation and a standard Array.

Preparation HTML

<script>
  function MakeNode(newNode) {
    newNode._previous = undefined;
    newNode._next = undefined;

    return newNode;
  };
  
  function LinkedList() {
    this.first = undefined;
    this.last = undefined;
  };
  
  LinkedList.prototype.add = function(node) {
   if (this.first) //If it's not empty
    {
        this.last._next = node;
        node._previous = this.last;
        this.last = node;
    }
    else { //If it's the first one
        this.first = this.last = node;
    }
  }
    
  function populateArray(amount) {
   ar = [];
   for (var i = 0; i < amount; i++) {
    ar.push({x:Math.random()});
   }
   return ar;
  }
  
  function populateLinkedList(amount) {
   ll = new LinkedList();
   for (var i = 0; i < amount; i++) {
    ll.add(MakeNode({x:Math.random()}));
   }
   return ll;
  }
  
  function doSomething(value) {
   return value + "string concatination";
  }
  
  function iterateArray(array) {
   for (var i = 0, l = array.length; i < l; ++i) {
    doSomething(array[i]);
   }
  }
  
  function iterateLinkedList(list) {
   for (var node = list.first; node; node = node._next) {
    doSomething(node);
   }
  }
  
  array25 = populateArray(25);
  array100 = populateArray(100);
  ll25 = populateLinkedList(25);
  ll100 = populateLinkedList(100);
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
array insertion x 100K
populateArray(100000);
ready
linked list insertion x 100K
populateLinkedList(100000);
ready
array insertion x 100
populateArray(100);
ready
linked list insertion x 100
populateLinkedList(100);
ready
iterate array 25
iterateArray(array25);
ready
iterate linked list 25
iterateLinkedList(ll25);
ready
iterate array 100
iterateArray(array100);
ready
iterate linked list 100
iterateLinkedList(ll100);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.