Benchmark: Array vs Linked List (with improved array corrected)

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 < 10000) { 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:

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 is being tested, compared, and their pros and cons.

**Benchmark Definition**

The benchmark tests two data structures: Arrays and Linked Lists. The purpose of this benchmark is to compare the performance of these two data structures when performing common operations such as appending, unshifting, shifting, and retrieving items from the end or beginning of the list.

**Script Preparation Code**

The script preparation code provides a basic implementation for both Array and Linked List data structures. For Linked Lists, it includes methods like `push`, `unshift`, `shift`, `item`, and `remove`. These methods are used to manipulate the linked list nodes.

**Individual Test Cases**

There are two test cases:

1. **Linked List**: This test case creates a new Linked List instance and appends 10,000 integers to it using the `push` method.
2. **Array**: This test case creates an empty array and assigns 0 to each index from 0 to 9,999 using the `[]` syntax.

**Comparison**

The benchmark compares the performance of Arrays and Linked Lists when performing these operations. The comparison is done by executing each operation a fixed number of times (10,000 in this case) and measuring the time it takes for each data structure to complete.

**Options Compared**

Two options are compared:

1. **Arrays**: Using built-in array methods like `push`, `unshift`, and indexing.
2. **Linked Lists**: Implementing custom linked list methods like `push`, `unshift`, and `remove`.

**Pros and Cons of Each Approach**

**Arrays:**

Pros:

* Built-in and widely supported
* Fast and efficient for large datasets
* Easy to use and understand

Cons:

* May incur overhead due to indexing and bounds checking
* Limited control over memory allocation and deallocation

**Linked Lists:**

Pros:

* Provides direct access to nodes, reducing indexing overhead
* Can be optimized for memory allocation and deallocation

Cons:

* Requires more code and expertise to implement correctly
* May have slower performance compared to arrays due to node creation and manipulation

**Latest Benchmark Result**

The latest benchmark result shows that the Array data structure outperforms the Linked List in terms of execution speed. However, this result may vary depending on the specific use case, dataset size, and system configuration.

It's essential to note that this benchmark is just one example, and there are many other factors that can influence performance, such as memory allocation, caching, and compiler optimizations.

Related benchmarks:

Array vs Linked List (with improved array corrected) (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

No previous run results

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