DEV Community

Discussion on: thank u, next: an introduction to linked lists

Collapse
 
apastuhov profile image
Aleksey Pastuhov

It is a good article, but it seems to me that it is not relevant to JS Arrays. In JS array is a simple object, but specific a little bit. So no performance profit from the creation of linked list as a data structure in JavaScript.

data can be stored at non-contiguous locations in the array (c) MDN

Please fix me if I am wrong.

Links:

Collapse
 
bozeman42 profile image
Aaron Kvarnlov-Leverty • Edited

There are definite advantages in certain situations to create a linked list over an array in JavaScript (whether they are common I can't say).

If your array is very large, deleting or adding elements near the beginning of the array can be expensive as all elements after the deleted or added element must be re-indexed. In a linked list, removing a node only affects one other node.

The trade off is the expense of traversing the linked list.

An example of the expense of adding or removing elements at the beginning of an array is comparing the performance of push vs unshift in javascript. I wrote a small function that pushes the value true to the end of an array some number of times and reports the time it took to perform that action, then it takes a new array and unshifts the value true to the beginning of the array the same number of times and reports the time taken for that action. Push with 100,000 elements took 1.8ms, unshift took 4.4 seconds, and I've written this entire paragraph while waiting for the 1,000,000 element unshift to finish. The 1,000,000 element push took 22ms. Now that it finished, the unshift took 12 MINUTES.

If you don't have to traverse very far on the list, the performance gain for adding and removing items near the beginning of the structure can be very significant, finishing in milliseconds instead of minutes.

Collapse
 
apastuhov profile image
Aleksey Pastuhov

That is awesome example! And thanks for perf tests you did!! I really forgot about that stuff, shame on me :)