Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Closure and garbage collection: most efficient way to remove consecutive nodes from a linked list

I wrote a quick and dirty implementation of a doubly-linked list for javascript. I would like to be able to remove multiple (consecutive) nodes at once, and was wondering: is it enough to just sever the ends of these outer most nodes I am removing, or do I have to remove each node individually. If I understand javascript's garbage collection correctly, once nothing points to those consecutive nodes any more even when they are still connected with each other, they should be taken care of by the garbage collector, is that correct? If anyone could tell me how I could test or verify this myself, I would highly appreciate that as well.

like image 227
DudeOnRock Avatar asked Dec 09 '12 01:12

DudeOnRock


1 Answers

According to MDN:

As of 2012, all modern browsers ship a mark-and-sweep garbage-collector. All improvements made in the field of JavaScript garbage collection (generational/incremental/concurrent/parallel garbage collection) over the last few years are implementation improvements of this algorithm, but not improvements over the garbage collection algorithm itself nor its reduction of the definition of when "an object is not needed anymore"

Mark and sweep algorithms begin from the root objects and find all reachable objects then collect all the non-reachable ones, so for these browsers severing the nodes will be fine. Older browsers use reference counting, which means objects are only collected once they have 0 references to them, so in this case the cycles of a doubly linked list will be problematic. You would then need to cut the cycles in the consecutive nodes in some way (setting the references to null, delete keyword, so on).

So if you are developing for moden browsers you're all good, but you'll need a slightly more involved solution if you want back compatibility to browsers like IE6/7 (it's always the way, isn't it...)

like image 88
kieran Avatar answered Sep 28 '22 23:09

kieran