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;
}

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.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:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Android 14; Mobile; rv:135.0) Gecko/135.0 Firefox/135.0

Browser/OS: Firefox Mobile 135 on Android

View result in a separate tab

Test name	Executions per second
Linked List	3.1 Ops/sec
Array	12964.5 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll break down the benchmark and its components to help understand what's being tested.

**Benchmark Overview**

The benchmark measures the performance of two data structures: arrays and linked lists. The test case is designed to create a large list (10,000 elements) using both an array and a linked list, and then pushes or unshifts elements onto the list repeatedly.

**Options Compared**

Two options are being compared:

1. **Array**: A traditional JavaScript array implementation.
2. **Linked List**: A custom implementation of a singly-linked list, specifically designed to mimic the behavior of arrays.

**Pros and Cons**

**Array:**

Pros:

* Fast access and manipulation (O(1) time complexity for push() and unshift())
* Memory-efficient (no unnecessary node creation)

Cons:

* Not optimized for frequent insertions or deletions
* May suffer from memory fragmentation if elements are frequently added and removed

**Linked List:**

Pros:

* Optimized for frequent insertions and deletions (O(1) time complexity)
* Can handle large amounts of data without excessive memory usage

Cons:

* Slower access and manipulation compared to arrays (O(n) time complexity for push() and unshift())
* More memory-intensive due to the need to create new nodes for each element

**Other Considerations**

The benchmark focuses on the performance of these two data structures when pushing or unshifting elements onto a list. Other factors that might influence performance, such as memory allocation and deallocation, are not considered in this benchmark.

**Library Used (Linked List)**

The linked list implementation is based on Nicholas C. Zakas's work, with additional methods added by the author. This implementation provides basic operations like push(), unshift(), shift(), item(), and remove().

No specific JavaScript features or syntax are being tested in this benchmark, as it focuses solely on the performance of these two data structures.

**Alternatives**

If you're interested in exploring alternative data structures for your use case, some options to consider are:

1. **Stacks**: A Last-In-First-Out (LIFO) data structure that can be implemented using arrays or linked lists.
2. **Queues**: A First-In-First-Out (FIFO) data structure that can be implemented using arrays or linked lists.
3. **Trees**: A hierarchical data structure that can be used for efficient storage and retrieval of large amounts of data.

Keep in mind that the choice of data structure depends on your specific requirements, including performance, memory usage, and complexity.

Related benchmarks:

Array vs Linked List (push) (version: 0)

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

Comparing performance of: Linked List vs Array

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