usage of linked list vs array

Benchmark created by Chris Shorrock 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 = null;
   this.tail = null;
  };
  
  LinkedList.prototype.add = function(data) {
   node = new Node(data);
   if (this.head == null) {
    this.head = node;
   }
   if (this.tail != null) {
    this.tail.next = node;
   }
   this.tail = node;
  }
  
  LinkedList.prototype.each = function(fn) {
   iterate = function(node) {
    fn(node.data);
    if (node.next) {
     return iterate(node.next);
    }
   };
   if (this.head) {
    return iterate(this.head);
   }
  }
  
  function populateArray(amount) {
   ar = new Array();
   for (i = 0; i < amount; i++) {
    ar[i] = "hello " + i;
   }
   return ar;
  }
  
  function populateLinkedList(amount) {
   ll = new LinkedList();
   for (i = 0; i < amount; i++) {
    ll.add("hello " + i);
   }
   return ll;
  }
  
  function doSomething(value) {
   return value + "string concatination";
  }
  
  function iterateArray(array) {
   for (value in array) {
    doSomething(value);
   }
  }
  
  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 25
populateArray(25);
ready
linked list insertion x 25
populateLinkedList(25);
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.