Benchmark: Array vs Linked List 2

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: 4 years ago)

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/85.0.4183.121 Safari/537.36

Browser/OS: Chrome 85 on Linux

View result in a separate tab

Test name	Executions per second
Linked List	9.3 Ops/sec
Array	29104.9 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll break down the benchmark definition and test cases to explain what's being tested, compared, and their pros and cons.

**Benchmark Definition**

The benchmark measures the performance of two data structures: Array and Linked List, in managing Todos (a list of items).

**Script Preparation Code**

The provided JavaScript code defines a `LinkedList` class with methods for adding, removing, and retrieving items from the list. The `createNode` function creates new node objects to be added or removed from the list.

**Individual Test Cases**

There are two test cases:

1. **Linked List**: The benchmark prepares a `LinkedList` instance and pushes 10,000 items onto it using a while loop.
2. **Array**: The benchmark prepares an empty array (`[]`) and pushes 10,000 items onto it using a while loop.

**Comparison**

The benchmark compares the performance of these two data structures under the same load (10,000 push operations).

**Pros and Cons of Each Approach**

1. **Linked List**:
	* Pros: Each node is self-contained, allowing for efficient insertion and deletion at any position.
	* Cons: Memory allocation can lead to memory fragmentation, and traversing the list can be slower than an array.
2. **Array**:
	* Pros: Fast access times due to contiguous memory storage and indexing capabilities.
	* Cons: Insertion and deletion can be slow, especially at the beginning or end of the array.

**Other Considerations**

* The benchmark uses a simple while loop for pushing items onto both data structures, which may not reflect real-world usage patterns.
* There is no test case for removing items from the list.
* No comparison of other data structure implementations (e.g., stack, queue) or algorithms (e.g., binary search).

**Library and Special Features**

The `LinkedList` class uses a library provided by Nicholas C. Zakas, which includes basic methods for adding, removing, and retrieving nodes in the list.

No special JavaScript features or syntax are used beyond basic JavaScript programming constructs.

**Alternatives**

To explore alternative data structures and performance comparisons:

* Test other data structure implementations (e.g., `Stack`, `Queue`) with similar benchmarking scenarios.
* Compare performance of different algorithms for search, insertion, and deletion operations (e.g., binary search vs. linear search).
* Include test cases for removing items from the list or modifying existing elements.
* Use more realistic usage patterns, such as using `forEach` instead of a while loop.

By exploring these alternatives, you can gain a deeper understanding of data structure performance trade-offs and optimize your application's code accordingly.

Related benchmarks:

Array vs Linked List 2 (version: 0)

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

Comparing performance of: Linked List vs Array

Created: 4 years ago by: Guest

Jump to the latest result

Linked List

Array

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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