Benchmark: Array vs Linked List with 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
var list = new LinkedList(); var x = 10000; while(x--) { list.unshift(x); } while(list.shift() < 1000) {}
Array
var array = []; var x = 10000; while(x--) { array.unshift(x); } while(array.shift() < 10000) {}

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

User agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:143.0) Gecko/20100101 Firefox/143.0

Browser/OS: Firefox 143 on Ubuntu

View result in a separate tab

Test name	Executions per second
Linked List	16088.4 Ops/sec
Array	1953.6 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks!

**Benchmark Overview**

The provided JSON represents two benchmark test cases: "Linked List" and "Array". Both tests are designed to measure the performance difference between using an array and a linked list data structure in JavaScript.

**Test Cases**

1. **Linked List**: The first test case creates a new instance of a custom LinkedList class, then pushes 10,000 elements onto the list using the `unshift` method. After that, it shifts elements from the list until the result is less than 1000. This test emphasizes the performance of linked list operations like insertion and deletion at the beginning.
2. **Array**: The second test case creates a new empty array, pushes 10,000 elements onto the array using the `unshift` method, and then shifts elements from the array until the result is greater than or equal to 10,000. This test highlights the performance of array operations like insertion and deletion at the beginning.

**Options Compared**

The benchmark compares two options:

1. **Array**: Using a built-in JavaScript array data structure.
2. **Linked List**: Implementing a custom linked list data structure using a LinkedList class.

**Pros and Cons**

* **Array**:
	+ Pros: Built-in, easy to implement, and well-maintained by the JavaScript community.
	+ Cons: May not provide optimal performance for certain use cases, especially when dealing with large amounts of data or frequent insertions/deletions at the beginning.
* **Linked List**:
	+ Pros: Can provide better performance for scenarios with frequent insertion/deletion at the beginning, as it avoids shifting elements to maintain the middle of the list.
	+ Cons: More complex to implement and maintain compared to arrays.

**Library Used**

The custom LinkedList class is implemented using a combination of object-oriented programming (OOP) concepts like inheritance, encapsulation, and polymorphism. The implementation includes methods for insertion, deletion, and searching elements in the list.

**Benchmark Results**

The latest benchmark results show that:

* The "Linked List" test case performed slightly better than the "Array" test case, with an average of 1366 executions per second compared to 303.
* However, it's essential to note that these results may vary depending on specific use cases and system configurations.

**Conclusion**

The benchmark highlights the performance differences between using a built-in JavaScript array and a custom linked list data structure. While arrays are convenient and widely supported, linked lists can provide better performance for scenarios with frequent insertions/deletions at the beginning. However, implementing a linked list requires more effort and expertise compared to using an array.

Related benchmarks:

Array vs Linked List with shift (version: 0)

Compare performance of Array vs Linked List with both shift and unshift

Comparing performance of: Linked List vs Array

Created: 4 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):