2

Arrays in a language like C have certain non-functional characteristics, like O(n) insertion and deletion.

But C operates on the bare metal, allocating contiguous bytes of memory.

In JavaScript, what is an Array?

Is it an implementation-defined data-structure with similar non-functional characteristics to those of C? Could Array actually be a linked-list under the hood?

If so, does that make user-land linked-list libraries redundant?

Ben Aston
  • 53,718
  • 65
  • 205
  • 331
  • If I'm not mistaking Arrays are optimized hashmaps in JS. I know they are build on top of Objects having the index as the key and the value as, the value. – Razvan Jul 06 '15 at 18:16
  • So who is brave enough to go digging into [the specification](http://www.ecma-international.org/ecma-262/6.0/index.html#sec-array-initializer)? – Dan Jul 06 '15 at 18:17
  • 3
    A JavaScript implementation is required to satisfy the behaviors described in the spec, and none of those stipulate implementation details or big-O behavior requirements. – Pointy Jul 06 '15 at 18:18
  • So assumptions about operation complexity cannot be made about `Array` instances? What about another languages that run in VMs? Are arrays in managed languages typically arrays in name alone? – Ben Aston Jul 06 '15 at 18:21
  • 1
    I searched "sublinear" in the spec. Only maps, sets, weakmaps and weaksets must be sublinear (on average). There does not seem to be any requirement for arrays. – Oriol Jul 06 '15 at 18:25
  • Some higher-level languages *do* describe the behavior of aggregate types; I think Clojure for example spells out how `List` and `Vector` are different. JavaScript arrays are (slightly) specialized objects, but the core behavior of array element access is exactly the same as object property access (because it **is** object property access). Of course, runtimes optimize for typical array-like use patterns. – Pointy Jul 06 '15 at 18:25
  • 1
    You can best see in the [implementation](http://izs.me/v8-docs/v8_8h_source.html#l01697). – Razvan Jul 06 '15 at 18:34

0 Answers0