Benchmark: Array vs Linked List123451

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) } var find = arr[9000]
ll12345
var list = new LinkedList() for (var i = 0; i < 10000; i++) { list.push(i) } var find = list.item(9000)

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.

I'll provide an explanation of the benchmark, its options, pros and cons, and other considerations.

**Benchmark Definition**

The benchmark compares the performance of two data structures: arrays and linked lists. The benchmark is designed to manage a list of 10,000 "todos" (items) and retrieve a specific todo item at index 9,900.

**Options Compared**

The options being compared are:

1. **Arrays**: Using JavaScript's built-in array data structure.
2. **Linked Lists**: Implementing a custom linked list data structure using the provided `LinkedList` class.

**Pros and Cons of Each Approach**

**Arrays:**

Pros:

* Fast access and retrieval times, especially for large datasets.
* Simple implementation and minimal overhead.

Cons:

* May lead to memory fragmentation issues when dealing with large amounts of data.
* Not suitable for situations where data needs to be frequently inserted or removed at arbitrary positions.

**Linked Lists:**

Pros:

* Efficient insertion and deletion operations, especially at the beginning or end of the list.
* Can help avoid memory fragmentation issues compared to arrays.

Cons:

* Slower access times compared to arrays, especially for large datasets.
* More complex implementation and higher overhead due to pointer management.

**Other Considerations**

The benchmark's performance is influenced by various factors, including:

* The size of the dataset (10,000 todos in this case).
* The frequency and efficiency of insertion, deletion, and retrieval operations.
* The specific hardware and software configuration used for testing.

**Library Used**

In the provided `LinkedList` implementation, the following libraries or concepts are used:

* JavaScript's built-in object prototypes to create the linked list structure.
* Custom methods (`push`, `unshift`, `shift`, `item`, and `remove`) to implement common linked list operations.

**Special JS Feature/Syntax**

This benchmark does not explicitly use any special JavaScript features or syntax, such as async/await, Promises, or modern functional programming constructs. However, it relies on the JavaScript engine's built-in optimizations and caching mechanisms to execute the benchmarks efficiently.

I hope this explanation helps!

Related benchmarks:

Array vs Linked List123451 (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):