Would you ever implement a linked list in Javascript? -

i'm learning data structures formally first time. me, of benefits traditionally described of linked lists (easier memory allocation , faster input , deletion body of list) seem moot in js given way arrays work (like objects numbered keys).

can give example of why i'd want use linked list in javascript?

as comments note, you'd if need constant time insertion/deletion list.

there 2 ways array reasonably implemented allow populating non-contiguous indices:

1. as actual c-like contiguous block of memory large enough contain indices used; unpopulated indices contain reference dummy value wouldn't treated populated entries (and excess capacity beyond max index left garbage, since length says it's not important)
2. as hash table keyed integers (based on c-like array)

in either case, cost insert @ end going amortized o(1), spikes of o(n) work done whenever capacity of underlying c-like array exhausted (or hash load threshold exceeded) , reallocation necessary.

if insert @ beginning or in middle (and index in question in use), have same possible work spikes before, , new problems. no, data existing indices doesn't change. keys above entry you're forcing in have incremented (actually or logically). if it's plain c-like array implementation, that's memmove (modulo needs of garbage collections , like). if it's hash table implementation, need read every element (from highest index lowest, means either sorting keys or looking every index below current length, if it's sparse array), pop out, , reinsert key value 1 higher. big array, cost enormous. it's possible implementation in browsers might clever nonsense using "offset" internally use negative "keys" relative offset avoid rehash while still inserting before index 0, make operations more expensive in exchange making shift/unshift cheaper.

point is, linked list written in javascript incur overhead being js (which runs more built-ins similar magnitude work). (ignoring possibility of memory manager introducing work spikes), it's predictable:

• if want insert or delete beginning or end, it's fixed work (one allocation or deallocation, , reference fixups)
• if iterating , inserting/deleting go, aside cost of iteration, it's same fixed work
• if turns out offsets aren't used implement shift/unshift in browser's implementation (with them, shift cheap, , unshift cheap until you've unshift-ed more you've shift-ed), you'd want use linked list when working fifo queue of potentially unbounded size

it's wholly possible browsers use offsets optimize (avoiding memmove or re-keying under conditions, though can't avoid occasional realloc , memmove or rehashing without wasting memory). don't know 1 way or other major browsers do, if you're trying write portable code consistent performance, don't want assume sacrificed general performance make shift/unshift case faster huge arrays, might have preferred make other operations faster , assumed shift/unshift used small arrays cost trivial.