Should I create a LinkedList in Java Script

Question

I'm currently working on a project that requires me to iterate over a list of values ​​and add a new value between each value already on the list. This will happen at each iteration, so the list will grow exponentially. I decided that implementing a list as a linked list would be a great idea. Now JS does not have a default Linked List data structure, and I have no problem creating it.

But my question is, is it worth creating a simple Linked List from scratch, or would it be best to create an array and use splice () to insert each element? Will it really be less efficient due to overhead?

Answer 1

Use a linked list; in fact, most custom implementations performed well in the user's javascript will beat the built-in implementations due to the complexity of the specification and decent JITting. For example, see https://github.com/petkaantonov/deque

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

---

As for the implementation, do not create an external linked list that contains values, but makes the values ​​naturally connected in the list nodes. Otherwise, you will use too much memory.

Answer 2

Inserting each element with splice() will be slower (inserting n elements takes O (n²)). But just building a new array (adding new values ​​and adding values ​​from the old to lockstep) and discarding the old one takes linear time and most likely has better persistent factors than manipulating a linked list. This can even take up less memory (linked list nodes can have surprisingly large overheads, especially if they are not intrusive).

Answer 3

Javascript is an interpreted language. If you want to implement a linked list, you will go in cycles! The translator will act slowly. The built-in functions provided by intrepreter are optimized and compiled using the interpreter, so they will work faster. I would decide to cut the array and then merge everything again, it should be faster than implementing my own data structure.

Also, javascript does not pass the value by pointer / link, so how are you going to implement a linked list?