Benchmark: Array vs Linked List

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 = 10000; while(x--) { array.unshift(x); }

Historical Performance Data aggregated from 61 community runs

Desktop Results:

Chrome 29 runs

Linked List

3K/s

Array

336/s

Fastest: Linked List (8.7x faster)

View exact numbers

✓ Linked List: 2,913 ops/sec
• Array: 336 ops/sec

Firefox 10 runs

Linked List

11K/s

Array

4K/s

Fastest: Linked List (3.1x faster)

View exact numbers

✓ Linked List: 11,296 ops/sec
• Array: 3,620 ops/sec

Mobile Results:

Chrome 16 runs

Linked List

2K/s

Array

170/s

Fastest: Linked List (9.3x faster)

View exact numbers

✓ Linked List: 1,587 ops/sec
• Array: 170 ops/sec

Firefox 6 runs

Linked List

8K/s

Array

2K/s

Fastest: Linked List (4.7x faster)

View exact numbers

✓ Linked List: 7,552 ops/sec
• Array: 1,618 ops/sec

Results show median performance across all community submissions. Run this benchmark yourself to verify on your device.

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

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/146.0.0.0 Safari/537.36

Browser/OS: Chrome 146 on Linux

View result in a separate tab

Linked List

31K/s

Array

481/s

View exact numbers

Test name	Executions per second
✓ Linked List	30,783 Ops/sec
Array	481 Ops/sec

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 their pros and cons.

**What is being tested?**

The benchmark compares the performance of two data structures: Arrays and Linked Lists. The specific test cases are:

1. "Linked List" (test case): Appending 10,000 elements to the beginning of a linked list using `unshift()`.
2. "Array" (test case): Appending 10,000 elements to the beginning of an array using `unshift()`.

**Comparison**

The comparison is between two approaches:

1. **Linked List**: A custom implementation of a singly-linked list with `push`, `unshift`, `shift`, and `item` methods.
2. **Array**: The built-in JavaScript Array object with the `unshift` method.

**Pros and Cons:**

**Linked List:**

Pros:

* Can be more efficient for large datasets since it only needs to traverse the list until the insertion point, rather than shifting all elements after each insertion.
* Allows for O(1) insertion at the beginning of the list (using `unshift`).

Cons:

* Requires manual memory management (e.g., keeping track of node references).
* Can be slower in practice due to the overhead of traversing the list.

**Array:**

Pros:

* Built-in and optimized by JavaScript engine for performance.
* Easy to use and integrate into existing code.

Cons:

* Can be less efficient for large datasets since it requires shifting all elements after each insertion, resulting in O(n) time complexity.
* Limited control over the underlying implementation.

**Other Considerations:**

The benchmark uses Firefox 131 as the testing browser, which may not represent the entire user base. Additionally, the test cases only involve appending elements to the beginning of the data structure, which might not be a realistic use case for most applications.

**Alternatives:**

If you need to implement a linked list or array in JavaScript, consider the following alternatives:

* **Native Linked List**: You can create a custom implementation using JavaScript objects and arrays. This approach provides control over the underlying implementation but requires manual memory management.
* **JavaScript libraries**: Libraries like jQuery, Lodash, or even vanilla Node.js modules (e.g., `node-queue`) provide built-in linked list implementations that simplify development and manage memory automatically.
* **Native Array**: If you're working with a modern JavaScript engine, using the built-in array implementation is usually the best choice for most use cases.

Array vs Linked List (version: 2) Benchmark.js

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

Comparing performance of: `Linked List vs Array`

Created: 8 years ago by: Registered User

Go to the latest result

Linked List

Array

Historical Performance Data aggregated from 61 community runs

Desktop Results:

Chrome 29 runs

Firefox 10 runs

Mobile Results:

Chrome 16 runs

Firefox 6 runs

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 (version: 2) Benchmark.js

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

Comparing performance of: Linked List vs Array

Created: 8 years ago by: Registered User

Go to the latest result

Linked List

Array

Historical Performance Data aggregated from 61 community runs

Desktop Results:

Chrome 29 runs

Firefox 10 runs

Mobile Results:

Chrome 16 runs

Firefox 6 runs

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`