/** * 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); }--enable-precise-memory-info flag.
| Test case name | Result |
|---|---|
| Linked List | |
| Array |
| Test name | Executions per second |
|---|---|
| Linked List | 10817.4 Ops/sec |
| Array | 4729.2 Ops/sec |
Let's break down the benchmark and explain what's being tested, compared, and their pros and cons.
What is being tested?
The benchmark compares the performance of two data structures: Arrays and Linked Lists. The specific test cases are:
unshift().unshift().Comparison
The comparison is between two approaches:
push, unshift, shift, and item methods.unshift method.Pros and Cons:
Linked List:
Pros:
unshift).Cons:
Array:
Pros:
Cons:
Other Considerations:
The benchmark uses Firefox 131 as the testing browser, which may not represent the entire user base. Additionally, the test cases only involve appending elements to the beginning of the data structure, which might not be a realistic use case for most applications.
Alternatives:
If you need to implement a linked list or array in JavaScript, consider the following alternatives:
node-queue) provide built-in linked list implementations that simplify development and manage memory automatically.
