usage of linked list vs array (v13)

Revision 13 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 = array.length; i > 0; i--) {
    doSomething(array[i]);
   }
  }
  
  function iterateLinkedList(list) {
    var currentNode;
    for (var node = list.first; node;) {
      currentNode = node;
      node = node._next
      doSomething(currentNode);
    }
  }
  
  array250 = populateArray(250);
  array1000 = populateArray(1000);
  ll250 = populateLinkedList(250);
  ll1000 = populateLinkedList(1000);
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
array insertion x 10k
populateArray(10000);
ready
linked list insertion x 10K
populateLinkedList(10000);
ready
array insertion x 100
populateArray(100);
ready
linked list insertion x 100
populateLinkedList(100);
ready
iterate array 250
iterateArray(array250);
ready
iterate linked list 250
iterateLinkedList(ll250);
ready
iterate array 1000
iterateArray(array1000);
ready
iterate linked list 1000
iterateLinkedList(ll1000);
ready

Revisions

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