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: 4 months ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/148.0.0.0 Safari/537.36 Edg/148.0.0.0

Browser/OS: Chrome 148 on Windows

View result in a separate tab

Array

410K/s

Linked List

47K/s

View exact numbers

Test name	Executions per second
✓ Array	409,573 Ops/sec
Linked List	47,368 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.

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

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

Go 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):

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

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

Go 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):

Related benchmarks

Comparing performance of: `Linked List vs Array`