CODEWITHSUNDEEP
javascriptarraysperformancememory-managementlinked-list
Dimi
Dimi

Reputation: 187

Is it worth creating a LinkedList in Java Script

I am currently working on a project that requires me to iterate through a list of values and add a new value in between each value already in the list. This is going to be happening for every iteration so the list will grow exponentially. I decided that implementing the list as a Linked List would be a great idea. Now, JS has no default Linked List data structure, and I have no problem creating one.

But my question is, would it be worth it to create a simple Linked List from scratch, or would it be a better idea to just create an array and use splice() to insert each element? Would it, in fact, be less efficient due to the overhead?

Upvotes: 9

Views: 4522

Answers (3)

user395760
user395760

Reputation:

Inserting each element with splice() would be slower indeed (inserting n elements takes O(n²) time). But simply building a new array (appending new values and appending the values from the old one in lockstep) and throwing away the old one takes linear time, and most likely has better constant factors than manipulating a linked list. It might even take less memory (linked list nodes can have surprisingly large space overhead, especially if they aren't intrusive).

Upvotes: 4

Esailija
Esailija

Reputation: 140238

Use a linked list, in fact most custom implementations done well in user javascript will beat built-in implementations due to spec complexity and decent JITting. For example see https://github.com/petkaantonov/deque

What george said is literally 100% false on every point, unless you take a time machine to 10 years ago.

As for implementation, do not create external linked list that contains values but make the values naturally linked list nodes. You will otherwise use way too much memory.

Upvotes: 8

george
george

Reputation: 605

Javascript is an interpreted language. If you want to implement a linked list then you will be looping a lot! The interpreter will perform vely slowly. The built-in functions provided by the intrepreter are optimized and compiled with the interpreter so they will run faster. I would choose to slice the array and then concatenate everything again, it should be faster then implementing your own data structure.

As well javascript passes by value not by pointer/reference so how are you going to implement a linked list?

Upvotes: -2

Related Questions