/** * 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; } }};var list = new LinkedList();var x = 10000;while(x--) { list.unshift(x);}var array = [];var x = 10000;while(x--) { array.unshift(x); }var list = new LinkedList();var x = 10000;while(x--) { list.push(x);}var array = [];var x = 10000;while(x--) { array.push(x); }--enable-precise-memory-info flag.
| Test case name | Result |
|---|---|
| Linked List: unshift | |
| Array: unshift | |
| Linked List: push | |
| Array: push |
| Test name | Executions per second |
|---|---|
| Linked List: unshift | 1406.1 Ops/sec |
| Array: unshift | 400.3 Ops/sec |
| Linked List: push | 9.7 Ops/sec |
| Array: push | 26206.3 Ops/sec |
Let's break down the benchmark and explain what's being tested, compared, and considered.
Benchmark Definition
The benchmark is designed to compare the performance of two data structures: Arrays and Linked Lists. Specifically, it tests the following operations:
unshift: adding an element to the beginning of a collectionpush: adding an element to the end of a collectionIn both cases, 10,000 elements are added to each collection using the respective operation.
Test Cases
There are four test cases:
unshift.unshift.push.push.Comparison
The benchmark is designed to compare the performance of Arrays versus Linked Lists for both unshift and push operations. The results will likely show that Arrays are faster than Linked Lists due to their contiguous memory allocation.
Considerations
When choosing between an Array and a Linked List, several factors come into play:
Latest Benchmark Results
The latest results show varying performance across different browsers and devices. The Chrome 84 browser on a Macintosh with Intel Mac OS X 10.15.7 consistently outperforms the Linked List implementations, while the other browsers and platforms have mixed results.
In summary, this benchmark compares the performance of Arrays versus Linked Lists for unshift and push operations, considering factors like memory allocation, insertion and deletion, and cache performance. The results highlight the benefits of using Arrays in certain scenarios, especially when it comes to cache-friendly operations.
