2

I am reading a book about JS data structure and it's mention that:

Arrays in javascript are implemented as objects, causing them to be less efficient than arrays built in other languages such as C++ and Java.

Why?

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
vlt5
  • 43
  • 4
  • That's an old book, this is no more true. However, JS `Array`s are more like C++ `Vector`s or Java `ArrayList`s (and as such they are less efficient than a "pure" array). – Bergi Aug 03 '15 at 15:34
  • 1
    The implementation of JS arrays is implementation-dependent. In fact, they are usually implemented in some way or another depending on whether they are sparse or not. – Oriol Aug 03 '15 at 15:34
  • 2
    Please ask only one question per post. Comparing arrays to linked lists is a completely different topic. – Bergi Aug 03 '15 at 15:36
  • In general linked list are very efficient at adding and deleting elements since they don't need to cascade on the whole list but only on contiguous nodes (depending if it is a doubly linked list or not). Arrays, on the other hand are (or used to be) better at sorting or adressing directly an element at a specified index. Although nowadays, I don't think we really need to pick one or another based on this criteria, computers are really faster now, but there is a reason to choose arrays over linked list and vice-versa. – axelduch Aug 03 '15 at 15:40

1 Answers1

7

JavaScript's Array type is defined, in the specification, as an object (not a true contiguous-memory array) with special handling of certain types of property names which the spec calls "indexes", a specific prototype (Array.prototype), and a length property with behavior that goes beyond just storing the value you put in it. According to the spec, then, there's little difference between using an array:

var a = [];
a[0] = "foo";
a.notAnIndex = "bar";
console.log(a[0]);         // "foo"
console.log(a.notAnIndex); // "bar"

...and using an object:

var o = {};
o[0] = "foo";
o.notAnIndex = "bar";
console.log(o[0]);         // "foo"
console.log(o.notAnIndex); // "bar"

...except, of course, that the object will have a different prototype and won't have the special length property. According to the spec, even in the a[0] above, that 0 is converted to a string ("0") and then the property with that name is looked up to get the value.

That's per spec, and what JavaScript engines did years ago.

Modern JavaScript engines try, when possible, to use true contiguous-memory arrays if it looks like that's how the array is being used by the code, falling back to dictionaries (objects) if and when necessary. Clever, these JS engine writers. :-)

JavaScript also, now, has other types of arrays called typed arrays, such as Int32Array, which are true arrays rather than dictionaries.

More (on my anemic little blog): A myth of arrays

I haven't got into the array vs. linked list question because, as Bergi says, it's really a separate question, and it's one that's been addressed in multiple questions here on SO, such as this one, this one, this one, and many others.

Community
  • 1
  • 1
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875