Benchmark: Array vs Linked List12345

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:

awefwaef
var arr = [] for (var i = 0; i < 10000; i++) { arr.push(i) }
ll12345
var list = new LinkedList() for (var i = 0; i < 10000; i++) { list.push(new createNode(i)) }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
awefwaef
ll12345

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 provided benchmark and explain what's being tested.

**Benchmark Definition:**

The benchmark compares the performance of two data structures: Array and Linked List. The test case is designed to manage a list of 10,000 todo items using both data structures.

**Options Compared:**

There are two options being compared:

1. **Array**: A traditional JavaScript array is used to store and manipulate the todo items.
2. **Linked List**: A custom implementation of a linked list is used to store and manipulate the todo items. The linked list has methods for adding, removing, and retrieving items.

**Pros and Cons:**

* **Array**:
	+ Pros:
		- Fast indexing (O(1) on average)
		- Efficient memory usage
	+ Cons:
		- Slow insertion and deletion at arbitrary positions (O(n))
		- Not suitable for applications where data is frequently added or removed from both ends
* **Linked List**:
	+ Pros:
		- Fast insertion and deletion at arbitrary positions (O(1))
		- Suitable for applications where data is frequently added or removed from both ends
	+ Cons:
		- Slow indexing (O(n)) on average
		- More memory usage compared to arrays

**Library/Functionality:**

The linked list implementation uses a custom `LinkedList` class, which provides methods for adding (`push` and `unshift`), removing (`remove`), and retrieving items by index (`item`). The library is written in JavaScript.

**Special JS Features/Syntax:**

There are no special JavaScript features or syntax mentioned in the benchmark definition. However, the linked list implementation uses a custom `createNode` function to create new node objects.

**Other Considerations:**

The benchmark assumes that the data structure will be used in a desktop environment on Windows 10. The test case only runs on Chrome 89 and has an execution rate of approximately 9,702 executions per second for the array option and 7,570 executions per second for the linked list option.

Overall, this benchmark is designed to compare the performance of arrays and linked lists in a JavaScript environment, with a focus on insertion, deletion, and retrieval operations.

Related benchmarks:

Array vs Linked List12345 (version: 0)

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

Comparing performance of: awefwaef vs ll12345

Created: 5 years ago by: Guest

Jump to the latest result

awefwaef

ll12345

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