Benchmark: Array vs Linked List (push, shift)

Script Preparation code:

/**
 * Linked List base code courtesy Nicholas C Zakas. Additional methods are my own.
 */
function LinkedList() {
  /**
   * Pointer to first item in the list.
   * @property _head
   * @type Object
   * @private
   */
  this._head = null;
}

function createNode(data, next) {
  return {
    data: data,
    next
  };
}

LinkedList.prototype = {
  //restore constructor
  constructor: LinkedList,

  /**
   * Appends some data to the end of the list. This method traverses
   * the existing list and places the value at the end in a new item.
   * @param {variant} data The data to add to the list.
   * @return {Void}
   * @method add
   */
  push: function(data) {
    //create a new item object, place data in
    var node = createNode(data);

    //used to traverse the structure
    var current;

    //special case: no items in the list yet
    if (this._head === null) {
      this._head = node;
    } else {
      current = this._head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
  },

  /**
   * Like its array counterpart, unshift appends an item to the beginning of the list
   */
  unshift: function(data) {
    var node = createNode(data);

    //special case: no items in the list yet
    if (this._head === null) {
      this._head = node;
    } else {
      node.next = this._head;
      this._head = node;
    }
  },

  /**
   * Like its array counterpart, shift removes and returns the first item of the list
   */
  shift: function() {
    const node = this._head;
    this._head = this._head.next;
    return node;
  },

  /**
   * Retrieves the data in the given position in the list.
   * @param {int} index The zero-based index of the item whose value
   *      should be returned.
   * @return {variant} The value in the "data" portion of the given item
   *      or null if the item doesn't exist.
   * @method item
   */
  item: function(index) {
    //check for out-of-bounds values
    if (index > -1) {
      var current = this._head,
        i = 0;

      while (i++ < index && current) {
        current = current.next;
      }

      return current ? current.data : null;
    } else {
      return null;
    }
  },

  /**
   * Removes the item from the given location in the list.
   * @param {int} index The zero-based index of the item to remove.
   * @return {variant} The data in the given position in the list or null if
   *      the item doesn't exist.
   * @method remove
   */
  remove: function(index) {
    //check for out-of-bounds values
    if (index > -1) {
      var current = this._head,
        previous,
        i = 0;

      //special case: removing first item
      if (index === 0) {
        this._head = current.next;
      } else {
        //find the right location
        while (i++ < index) {
          previous = current;
          current = current.next;
        }

        //skip over the item to remove
        previous.next = current.next;
      }

      //return the value
      return current ? current.data : null;
    } else {
      return null;
    }
  }
};

Tests:

Linked List: unshift
var list = new LinkedList(); var x = 10000; while(x--) { list.unshift(x); }
Array: unshift
var array = []; var x = 10000; while(x--) { array.unshift(x); }
Linked List: push
var list = new LinkedList(); var x = 10000; while(x--) { list.push(x); }
Array: push
var array = []; var x = 10000; while(x--) { array.push(x); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Linked List: unshift
Array: unshift
Linked List: push
Array: push

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's break down the benchmark and explain what's being tested, compared, and considered.

**Benchmark Definition**

The benchmark is designed to compare the performance of two data structures: Arrays and Linked Lists. Specifically, it tests the following operations:

* `unshift`: adding an element to the beginning of a collection
* `push`: adding an element to the end of a collection

In both cases, 10,000 elements are added to each collection using the respective operation.

**Test Cases**

There are four test cases:

1. **Linked List: unshift**: creates a new Linked List instance and adds 10,000 elements using `unshift`.
2. **Array: unshift**: creates a new Array instance and adds 10,000 elements using `unshift`.
3. **Linked List: push**: creates a new Linked List instance and adds 10,000 elements using `push`.
4. **Array: push**: creates a new Array instance and adds 10,000 elements using `push`.

**Comparison**

The benchmark is designed to compare the performance of Arrays versus Linked Lists for both `unshift` and `push` operations. The results will likely show that Arrays are faster than Linked Lists due to their contiguous memory allocation.

**Considerations**

When choosing between an Array and a Linked List, several factors come into play:

* **Memory allocation**: Arrays allocate memory contiguously, whereas Linked Lists allocate memory separately for each node. This can lead to more efficient memory usage in some cases.
* **Insertion and deletion**: In Linked Lists, inserting or deleting elements requires traversing the list, which can be slower than allocating new memory and updating indices in Arrays.
* **Cache performance**: Contiguous memory allocation in Arrays can improve cache performance, as the CPU can access data that's nearby in memory more efficiently.

**Latest Benchmark Results**

The latest results show varying performance across different browsers and devices. The Chrome 84 browser on a Macintosh with Intel Mac OS X 10.15.7 consistently outperforms the Linked List implementations, while the other browsers and platforms have mixed results.

In summary, this benchmark compares the performance of Arrays versus Linked Lists for `unshift` and `push` operations, considering factors like memory allocation, insertion and deletion, and cache performance. The results highlight the benefits of using Arrays in certain scenarios, especially when it comes to cache-friendly operations.

Related benchmarks:

Array vs Linked List (push, shift) (version: 0)

Manage Todos in a list - compare performance of Array vs Linked List.

Comparing performance of: Linked List: unshift vs Array: unshift vs Linked List: push vs Array: push

Created: 5 years ago by: Guest

Jump to the latest result

Linked List: unshift

Array: unshift

Linked List: push

Array: push

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):