Benchmark: Array vs Linked List (with improved array)

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
var list = new LinkedList(); var x = 10000; while(x--) { list.unshift(x); }
Array
var array = []; var x = 0; while(x < 1000) { array[x] = x; x++ }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Linked List
Array

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Linked List	36056.9 Ops/sec
Array	32020.4 Ops/sec

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

LLMs can make mistakes. Check important info.

**Benchmark Overview**

The provided benchmark compares the performance of two data structures: Arrays and Linked Lists. The benchmark is designed to measure the execution time of inserting and manipulating elements in both data structures.

**Script Preparation Code**

The Script Preparation Code is a JavaScript implementation of a Linked List, which includes methods for inserting, removing, and accessing elements. This code is used as a base for both the Array and Linked List benchmarks.

**Individual Test Cases**

There are two individual test cases:

1. **Linked List**: The benchmark inserts 10,000 elements at the beginning of the Linked List using the `unshift` method.
2. **Array**: The benchmark inserts 1,000 elements in a contiguous block of memory starting from index 0 using the `array[x] = x;` syntax.

**Options Compared**

In this benchmark, two main options are compared:

* **Arrays**: A traditional JavaScript Array implementation with push and shift methods.
* **Linked Lists**: The custom implementation provided in the Script Preparation Code.

**Pros and Cons of Each Approach**

**Arrays:**

Pros:

* Fast access to elements using direct indexing (O(1) time complexity)
* Cache-friendly due to contiguous memory allocation

Cons:

* Insertion and deletion operations can be slow, especially for large datasets, as they require shifting all subsequent elements
* Not designed for efficient insertion or deletion of elements at arbitrary positions

**Linked Lists:**

Pros:

* Efficient insertion and deletion operations at arbitrary positions (O(1) time complexity)
* No need to shift elements when inserting or deleting, reducing the number of operations required

Cons:

* Accessing elements can be slow due to the need to traverse the list from the beginning
* Not cache-friendly due to non-contiguous memory allocation

**Library and Special JS Features**

The Linked List implementation uses a library-style approach with custom methods for insertion, deletion, and access. No special JavaScript features are used in this benchmark.

**Benchmark Results**

The latest benchmark results show that the Array performs better than the Linked List in terms of execution time per second:

* **Array**: 152763.609375 executions/second
* **Linked List**: 822.3585205078125 executions/second

This result suggests that Arrays are generally faster for this particular benchmark, likely due to their cache-friendly nature and efficient access patterns.

Keep in mind that the results may vary depending on the specific use case, hardware, and software configuration.

Related benchmarks:

Array vs Linked List (with improved array) (version: 0)

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

Comparing performance of: Linked List vs Array

Created: 3 years ago by: Guest

Jump to the latest result

Linked List

Array

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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