9

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?

Dimi
  • 187
  • 1
  • 2
  • 7
  • Depends on the number of elements. For few elements, the array approach is faster, for many elements, the linked list is faster. In any case, the linked list will consume more memory. You'll just have to try. – T-Bull Mar 09 '14 at 09:42

3 Answers3

8

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.

Esailija
  • 138,174
  • 23
  • 272
  • 326
  • Can you expand on the last part? Does this mean I should make a Linked List with nodes that contain data and a reference to the next node? Or are you suggesting I make the data itself a node that has an extra reference to next node? Or are you suggesting something completely different? – Dimi Mar 09 '14 at 20:01
  • 2
    @Dimi I mean do not make an external "linked list data structure" at all. Simply have your values naturally have a `.next` property (and `.prev` if required). If your values are singly linked you will use just as much memory as you would use with array, so great savings are gained. – Esailija Mar 10 '14 at 11:31
  • I don't follow this: why do we allow ourselves to put the .next and .prev properties on objects in a linked list? isn't there a better way without storing properties? – Alexander Mills Sep 01 '16 at 06:39
3

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).

  • This is an interesting solution. I'll check it out. To "throw away" The old array, would I have to pop all the items off? Or can I just set the thing to null? I'm not quite sure how memory management is handled yet in Java Script. – Dimi Mar 09 '14 at 20:06
  • 1
    @Dimi You *could* pop off all items, but it's probably more effective to just overwrite the variable that used to refer to it (i.e. `the_array = new_array;`). "Setting it to null" is just a specific case of "overwriting the variable", it does nothing special, especially if you proceed to store yet another thing (e.g. the new array) in the variable right afterwards. –  Mar 09 '14 at 23:05
-2

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?

george
  • 565
  • 1
  • 5
  • 16
  • 2
    That's not true. JS passes most things by reference. – T-Bull Mar 09 '14 at 09:40
  • @T-Bull http://stackoverflow.com/questions/518000/is-javascript-a-pass-by-reference-or-pass-by-value-language not most things – george Mar 09 '14 at 09:48
  • Yes, most things. While at the core, JS is a pass-by-value language, most things that you use are objects, and objects are always handled by reference. – T-Bull Mar 09 '14 at 10:03
  • Furthermore, JS may have once been very slow at these things, but with modern JIT compilers JS is actually one of the fastest languages around. As Esailija says, this answer is simply wrong. – Michael Dorst Oct 19 '19 at 02:52