Benchmark: Array vs Linked List push

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;
  this._tail = 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;
      this._tail = node;
    } else {
      this._tail.next = node;
      this._tail = 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.push(x); }
Array
var array = []; var x = 10000; while(x--) { array.push(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 what's being tested in this benchmark and the options being compared.

**Benchmark Definition:**

The benchmark is designed to compare the performance of two data structures: Arrays and Linked Lists. The specific test case involves pushing 10,000 elements onto each data structure using a simple loop.

**Options being compared:**

There are two main options being compared:

1. **Array**: An array is a contiguous block of memory where elements are stored in sequential order. Pushing an element onto an array involves accessing the end of the array and updating its length property.
2. **Linked List**: A linked list is a data structure where each element (node) points to the next node in the sequence. Pushing an element onto a linked list involves creating a new node, setting its `next` property to point to the existing head node, and updating the head node's reference.

**Pros and Cons of each approach:**

**Array:**

Pros:

* Fast access times due to contiguous memory layout
* Efficient insertion and deletion at any position

Cons:

* Memory usage increases linearly with the number of elements added
* Pushing an element onto an array requires accessing the end of the array, which can be slow for large datasets

**Linked List:**

Pros:

* Memory usage is more efficient since only the new node is created and stored in memory
* Insertion and deletion at any position are relatively fast (O(n) time complexity)

Cons:

* Access times can be slower due to the need to traverse the linked list from the head
* More complex implementation compared to arrays

**Other considerations:**

In addition to these two options, there may be other data structures that could be used for this benchmark, such as:

* **Vector**: A dynamic array-based data structure that provides efficient insertion and deletion at any position.
* **Doubly Linked List**: A variant of the linked list where each node points to both the previous and next nodes in the sequence.

**Library usage:**

The `LinkedList` implementation provided appears to be a custom implementation, which suggests that it's being used for this benchmark specifically. If you were to use an existing library or framework, such as JavaScript's built-in `Array` or `LinkedList` implementations, the performance results would likely be different.

Overall, this benchmark is designed to compare the performance of two fundamental data structures in terms of insertion and deletion efficiency, with a focus on large datasets.

Related benchmarks:

Array vs Linked List push (version: 1)

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

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