32

I'm new to Javascript, and notice that you don't need to specify an array's size and often see people dynamically creating arrays one element at time. This would be a huge performance problem in other languages as you would constantly need to reallocate memory for the array as it increases in size.

Is this not a problem in JavaScript? If so, then is there a list structure available?

stakx - no longer contributing
  • 83,039
  • 20
  • 168
  • 268
nw.
  • 4,795
  • 8
  • 37
  • 42
  • 2
    In languages with resizable arrays, the actual memory allocated is typically doubled everytime it has to grow. As a result, you are not going to constantly reallocate memory in any language. – Winston Ewert Aug 15 '11 at 19:00
  • Thanks guys, that works fine for me. I just wanted to make sure I wasn't committing a javascript faux pas. – nw. Aug 15 '11 at 19:05

6 Answers6

28

Javascript arrays are typically implemented as hashmaps (just like Javascript objects) with one added feature: there is an attribute length, which is one higher than the highest positive integer that has been used as a key. Nothing stops you from also using strings, floating-point numbers, even negative numbers as keys. Nothing except good sense.

Michael Lorton
  • 43,060
  • 26
  • 103
  • 144
21

It most likely depends on what JavaScript engine you use.

Internet Explorer uses a mix of sparse arrays and dense arrays to make that work. Some of the more gory details are explained here: http://blogs.msdn.com/b/jscript/archive/2008/04/08/performance-optimization-of-arrays-part-ii.aspx.

vcsjones
  • 138,677
  • 31
  • 291
  • 286
12

The thing about dynamic languages is, well, that they're dynamic. Just like ArrayList in Java, or arrays in Perl, PHP, and Python, an Array in JavaScript will allocate a certain amount of memory and when it gets to be too big, the language automatically appends to the object. Is it as efficient as C++ or even Java? No (C++ can run circles around even the best implementations of JS), but people aren't building Quake in JS (just yet).

It is actually better to think of them as HashMaps with some specialized methods too anyway -- after all, this is valid: var a = []; a['cat']='meow';.

cwallenpoole
  • 79,954
  • 26
  • 128
  • 166
  • Might depend on your definition of "valid". It would certainly run on every compliant version of Javascript, it's performant and portable and all those other good CS things. It's a really bad plan, though. – Michael Lorton Aug 15 '11 at 19:13
  • 10
    And, people have built quake in JS and webGL :P – fabspro Jun 16 '12 at 17:31
8

No.

What JavaScript arrays are and aren't is determined by the language specification specifically section 15.4. Array is defined in terms of the operations it provides not implementation details of the memory layout of any particular data structure.

Could Array be implemented on top of a linked list? Yes. This might make certain operations faster such as shift and unshift efficient, but Array also is frequently accessed by index which is not efficient with linked lists.

It's also possible to get the best of both worlds without linked lists. Continguous memory data structures, such as circular queues have both efficient insertion/removal from the front and efficient random access.

In practice, most interpreters optimize dense arrays by using a data structure based around a resizable or reallocable array similar to a C++ vector or Java ArrayList.

Mike Samuel
  • 118,113
  • 30
  • 216
  • 245
4

They are actually more like custom objects that use the properties as indexes. Example:

var a = { "1": 1, "2": 2};
a.length = 2;
for(var i=0;i<a.length;i++)
    console.log(a[i]);

a will behave almost like an array, and you can also call functions from the Array.prototype on it.

Eliu
  • 757
  • 5
  • 6
  • 1
    Don't you miss the zero index? – Zlatko Dec 05 '13 at 20:54
  • 2
    I don't know what @Eliu is trying to show. The code will never work this way (perhaps the intention??). String keys need to be referenced as strings, not as integers. So even ```a[1]``` will not result in a value. The proper code to list the items would be using a ```for .. in``` or using e.g. ```console.log(a[''+(i+1)]);``` – Michiel van der Blonk Mar 07 '18 at 11:33
  • Or maybe defining each key as a number, which is way more simpler? Anyway, even with a syntax mistake, I think @Eliu tried to illustrate the situation - and even using string keys as if they were number ones, IMO the explanation was good enough to understand the main idea. – Stanley Sathler Mar 26 '20 at 14:50
  • 1
    @MichielvanderBlonk This is not true at all. Objects can only have strings and symbols as property identifiers. If you use a number to access a property, it will be converted to a string. @Eliu's code here will work as long as you fix the 0-index which is missing from the object `a`. I think what he's trying to show is that Arrays are just normal objects that happen to have numbers as their property keys. – Leonardo Raele May 22 '21 at 13:20
  • 1
    @LeonardoRaele Yes you are right, and I tried the code, it happens to work, but mostly as a side effect instead of as how it was intended. I think it might confuse the OP even more, even though it's technically correct. Consider this ```var a = { "1": 1, "3": 3}; a.length = 4; for(var i=0;i – Michiel van der Blonk May 24 '21 at 18:55
  • I don't understand your point. What do you mean by side effect? Of course it will print `undefined` for 0 and 2 as these keys doesn't exist in the object in your example. – Leonardo Raele May 25 '21 at 17:16
  • so is it O(n) to retrieve a value from an a certain index of an array? – Embedded_Mugs Jun 08 '22 at 20:35
4

Javascript arrays are not true arrays like in C/C++ or other languages. Therefore, they aren't as efficient, but they are arguably easier to use and do not throw out of bounds exceptions.

FishBasketGordo
  • 22,904
  • 4
  • 58
  • 91