/** * 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.push(x);}var array = [];var x = 10000;while(x--) { array.push(x); }--enable-precise-memory-info flag.
| Test case name | Result |
|---|---|
| Linked List | |
| Array |
| Test name | Executions per second |
|---|---|
| Linked List | 9.3 Ops/sec |
| Array | 29104.9 Ops/sec |
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:
LinkedList instance and pushes 10,000 items onto it using a while loop.[]) 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
Other Considerations
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:
Stack, Queue) with similar benchmarking scenarios.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.
