As we all know that linked list item insertion takes O(1) time irrespective of position while that of array is O(n) depending on position for which worst case is O(n), first position and best case is O(1), last position.
I have checked this in VS Code and surprised to find that insertion in linked list turned out to be 3 times slower that that for array even when placing the item in starting positions. Why is this so?
class Linkedlist{
constructor(){
this.head = null;
this.size = 0;
}
add(d){
this.head = new Node(d, this.head);
++this.size;
}
displace(){
let d = this.head;
this.head = d.next;
--this.size;
return d.data;
}
place(d){
if(this.head){
if((this.head).data >= 14)
this.add(d);
else{
let pre = this.head;
let cur = pre.next;
while(cur && (cur.data<14)){
pre = cur;
cur = cur.next;
}
pre.next = new Node(d,cur);
++this.size;
}
}else
this.add(d);
}
}
class Node{
constructor(data, next=null){
this.data = data;
this.next = next;
}
}
let A = new Linkedlist();
A.add(29);
A.add(28);
A.add(27);
A.add(26);
A.add(25);
A.add(24);
A.add(23);
A.add(22);
A.add(21);
A.add(20);
A.add(19);
A.add(18);
A.add(17);
A.add(16);
A.add(15);
A.add(14);
A.add(13);
A.add(12);
A.add(11);
A.add(10);
const start = performance.now();
A.place(13.5);
const end = performance.now();
console.log(end-start);
So, here I have implemented a linked list using classes concept and added all elements at beginning before starting timer. And the place function is used to interate the list till either it reaches the last node or find the data value to be equal to or greater than 14, there it places 13.5.
let A = [10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29];
let j;
const start = performance.now();
for(j=0; j<A.length; j++){
if(A[j]>=14)
break;
}
A.splice(j,0,13.5);
const end = performance.now();
console.log(end-start);
Similarly, I have done this for array.
As time complexity tells us something about asymptotic behaviour, and the JavaScript array splice method benefits from a native implementation, you'll need to test this with larger data sets.
Secondly, your tests are testing two actions at the same time: finding a location in the data structure, and inserting a value at that location. The finding part has the same O(n) time complexity for both data structures, so it would be wise to remove that aspect from the tests, so you can focus on time used for the insertion only. So that means you should test the insertion at the front of the data structure only.
Finally, the tests should be repeated more than a few times to get reliable results.
Here is a test that inserts a thousand values in both structures, and then times how long it takes to repeat the following action a million times:
To ease the tests, I have also renamed the methods in the linked list class so they have the same name as for the Array prototype (shift and unshift).
class LinkedList{
constructor(...values) {
this.head = null;
this.size = 0;
for (const value of values.reverse()) {
this.unshift(value);
}
}
// Use the same method names as Array.prototype has
unshift(d) {
this.head = new Node(d, this.head);
++this.size;
}
shift() {
let d = this.head;
this.head = d.next;
--this.size;
return d.data;
}
}
class Node{
constructor(data, next=null) {
this.data = data;
this.next = next;
}
}
function test(obj, numTests) {
const start = performance.now();
for (let i = 0; i < numTests; i++) {
obj.unshift(123);
obj.shift();
}
return Math.round(performance.now() - start);
}
// Set up
const numValues = 1000;
const numTests = 1_000_000;
const arr = [...Array(numValues).keys()];
const lst = new LinkedList(...arr);
// Repeatedly add and remove a value at the front of the data structure
const arrTime = test(arr, numTests);
const lstTime = test(lst, numTests);
// Report
console.log({ arrTime, lstTime });On my PC, the array operations turn out to be slower with this setup.