CODEWITHSUNDEEP
javascriptarrayslinked-list
bonbon
bonbon

Reputation: 253

How does an array actually work in javascript

i hope my question isn't that dumb. But i've wondered how arrays actually work in javascript. Espacially getting an element by index.

Let's assume i have an array called myFirstArray with the elements [1,2,3,4]. When i type myFirstArray[3], how does it work to get the fourth element from that array? Does it loop through? So everytime i want the last element of an array it is looping through the whole array?

Same goes with adding an element to an Array. Do it loop always through the array do find the last element in the Array?

I'm asking because i implemented a linkedList into Javascript and im wondering if it is more efficient than an normal array.

Upvotes: 0

Views: 186

Answers (3)

Guffa
Guffa

Reputation: 700630

The implementation of arrays in Javascript is a little different from how it's done in most other languages.

An array isn't just a list of items, instead it is a associative array. Items aren't stored after each other, instead they are stored as discrete key-value pairs. If you for example put values at index 3 and 5, the array doesn't contain undefined items to fill up the gaps, it just has the values that are set.

With code like this:

var a = [];
a[3] = 1;
a[5] = 2;

The data that is stored in the array doesn't look like this:

[ undefined, undefined, undefined, 1, undefined, 2 ]

Rather it looks like this:

{
  "3": 1,
  "5": 2,
  "length": 6
}

The items in the array is stored as properties in the array object, it's just that the array handles properties with a numeric key in a special way, i.e. adjusting the length property if needed.

The implementation of the key-value collection is done using a hash table (or perhaps something even more efficient, depending on the Javascript engine), so accessing an item is close to an O(1) operation, i.e. it doesn't loop through all properties until it finds the right one.

Upvotes: 3

Margus
Margus

Reputation: 20058

In Javascript there are standard built-in objects and one of those objects is Array. Array is high-level global object and is used as a constructor for arrays.

Array elements are object properties that can be accessed through bracket notation. In other languages you would call Javascript arrays as sparse arrays (ex: Wolfram).

Upvotes: 1

Motine
Motine

Reputation: 1862

How array access is realized is up to the JavaScript engine itself and may hence differ from engine to engine.

I would guess though that arrays are still blocks of memory in most engines. If you access an element, the array is not circled through. Rather the memory address for that specific element is calculated (memory_offset_of_the_first_element + size_of_element * desired_index) and then the element can be gathered from there. Insertions and deletions are a more complex and expensive. In worst case the whole array needs to be copied and adjusted.

Lamar provided a good overview in When to use a linked list over an array/array list?.

Upvotes: 1

Related Questions