5

We be learning about arrays in computer science and how they occupy a continuous range of memory space.

In a pure array you cannot add and remove elements without shifting other elements.

So when I do:

const arr = ['a', 'b', 'd'];

arr.splice(2, 0, 'c'); // arr is now ['a', 'b', 'c', 'd']

I am not performing an array operation and arrays must be implemented in some other way in JavaScript?

Perhaps a linked list?

I'm not asking for a specification, just in a typical implementation of the language in the browser or Node, what are they likely using?

This 10 year old+ Q/A touches on the subject but does not answer it, so please do not mark as a duplicate.

The actual underlying representation may differ between browsers (or it may not).

What is the most likely underlying data structure used?

Boann
  • 48,794
  • 16
  • 117
  • 146
i s
  • 53
  • 4
  • To clarify -- You are wondering about the *way* that JavaScript stores arrays from a browser standpoint? If I am wrong or off point, please clarify :) – Zak Jul 24 '19 at 23:49
  • Updated Q to `the browser or Node` ... – i s Jul 24 '19 at 23:51
  • As far as I understand it ... JavaScript can't really "know" about the "real time" structure of array. It makes assumptions based on the runtime environment, but it can never *really* "know" the exact structure of an array object. This is just my understanding, and that's why I am leaving a comment and not an answer ;) – Zak Jul 24 '19 at 23:56

1 Answers1

4

The array is not just implemented in one way. It depends upon what you put in to it, numbers, other arrays or objects, etc.

The JavaScript engine then decides at run-time how to implement it.

The two most common are C++ arrays and Linked Lists.

See here for more information.

t a
  • 56
  • 2
  • 1
    Actually, most js engines never use linked lists. They use a hash table instead (because they already have the code for it for handling Objects and makes array access O(1)). V8 is an example that uses either arrays or hash table and does not use linked lists – slebetman Jul 25 '19 at 01:27
  • My reference is the link reference you provide above. It says that it uses array or array or array or array or array or array or dictionary (hash table). See the list of cases after the "C++ here" link. So in no case does V8 use a link list – slebetman Jul 25 '19 at 04:25
  • This part: `PACKED_SMI_ELEMENTS – a packed integer array`, `PACKED_DOUBLE_ELEMENTS – a packed double array`, `PACKED_ELEMENTS – a packed object array`, `HOLEY_SMI_ELEMENTS – a sparse integer array`, `HOLEY_DOUBLE_ELEMENTS – a sparse double array`, `HOLEY_ELEMENTS – a sparse object array`, `DICTIONARY_ELEMENTS – a very sparse array that is backed by a dictionary (which is a hash table)` – slebetman Jul 25 '19 at 04:27