/** * 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);}while(list.shift() < 1000) {}var array = [];var x = 10000;while(x--) { array.unshift(x); }while(array.shift() < 10000) {}--enable-precise-memory-info flag.
| Test case name | Result |
|---|---|
| Linked List | |
| Array |
| Test name | Executions per second |
|---|---|
| Linked List | 19478.8 Ops/sec |
| Array | 242.1 Ops/sec |
Let's dive into the world of JavaScript microbenchmarks!
Benchmark Overview
The provided JSON represents two benchmark test cases: "Linked List" and "Array". Both tests are designed to measure the performance difference between using an array and a linked list data structure in JavaScript.
Test Cases
unshift method. After that, it shifts elements from the list until the result is less than 1000. This test emphasizes the performance of linked list operations like insertion and deletion at the beginning.unshift method, and then shifts elements from the array until the result is greater than or equal to 10,000. This test highlights the performance of array operations like insertion and deletion at the beginning.Options Compared
The benchmark compares two options:
Pros and Cons
Library Used
The custom LinkedList class is implemented using a combination of object-oriented programming (OOP) concepts like inheritance, encapsulation, and polymorphism. The implementation includes methods for insertion, deletion, and searching elements in the list.
Benchmark Results
The latest benchmark results show that:
Conclusion
The benchmark highlights the performance differences between using a built-in JavaScript array and a custom linked list data structure. While arrays are convenient and widely supported, linked lists can provide better performance for scenarios with frequent insertions/deletions at the beginning. However, implementing a linked list requires more effort and expertise compared to using an array.
