Benchmark: Array vs Linked List 5t3rvgt

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.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 dive into the world of JavaScript microbenchmarks and explore what's being tested in this benchmark.

**Benchmark Definition**

The benchmark defines two data structures: an Array and a Linked List. The goal is to compare the performance of these two data structures when managing a list of 10,000 elements.

**Options Compared**

There are two options being compared:

1. **Array**: An array is a contiguous block of memory that stores a sequence of values.
2. **Linked List**: A linked list is a dynamic collection of nodes, where each node points to the next node in the sequence.

**Pros and Cons of Each Approach**

**Array:**

Pros:

* Fast access times, since elements are stored contiguously in memory.
* Efficient use of memory, as no extra nodes are required for pointer manipulation.

Cons:

* Elements must be accessed sequentially, which can lead to slower performance when inserting or deleting elements near the beginning of the array.
* Insertion and deletion operations have a higher overhead due to the need to shift all subsequent elements.

**Linked List:**

Pros:

* Efficient insertion and deletion operations, as only the affected nodes need to be updated.
* Good memory usage, since each node can be allocated separately when needed.

Cons:

* Slower access times, since elements are not stored contiguously in memory.
* Higher overhead due to pointer manipulation between nodes.

**Library:**

The benchmark uses a custom implementation of a Linked List, which is provided as part of the `LinkedList` class. The library provides methods for common operations such as `push`, `unshift`, `shift`, `item`, and `remove`.

**Special JS Feature/Syntax:**

There doesn't appear to be any special JavaScript features or syntax being used in this benchmark.

**Other Alternatives**

In addition to the Array and Linked List approaches, other alternatives could include:

* **Stack**: A last-in, first-out (LIFO) data structure that could offer efficient insertion and deletion operations.
* **Queue**: A first-in, first-out (FIFO) data structure that could offer efficient insertion and deletion operations.
* **Trees**: A hierarchical data structure that could offer efficient search and insertion operations.

However, these alternatives are not being tested in this benchmark, so we can't draw conclusions about their performance relative to the Array and Linked List approaches.

Related benchmarks:

Array vs Linked List 5t3rvgt (version: 0)

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

Comparing performance of: Linked List vs Array

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