usage of linked list vs array (v10)

Revision 10 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>
  Node = function(data) {
   this.data = data;
   this.next = null;
  };
  
  LinkedList = function() {
   this.head = this.tail = new Node;
  };
  
  LinkedList.prototype.add = function(data) {
   var node = new Node(data);
   this.tail.next = node;
   this.tail = node;
  }
  
  LinkedList.prototype.each = function(fn) {
   for (var node = this.head.next; node; node = node.next) {
    fn(node.data);
   }
  }
  
  function populateArray(amount) {
   ar = new Array();
   for (i = 0; i < amount; i++) {
    ar[i] = {x:Math.random()};
   }
   return ar;
  }
  
  function populateLinkedList(amount) {
   ll = new LinkedList();
   for (i = 0; i < amount; i++) {
    ll.add({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) {
   list.each(doSomething);
  }
  
  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.