const a = [ ] is not an array?! 😱

Introduction

As I delved into Primeagen's Algorithms course on Frontend Masters, I was struck by a revelation: the familiar const a = [ ] syntax we use to declare an array in JavaScript is not, in fact, an array in the traditional sense. This discovery came as a surprise to me, and I felt a desire to share this newfound knowledge with others through this blog.

What is an Array?

An array is an ordered collection of values. Each value is called an element, and each element has a numeric position in the array, known as its index. JavaScript arrays are untyped: an array element may be of any type, and different elements of the same array may be of different types. Array elements may even be objects or other arrays, which allows you to create complex data structures, such as arrays of objects and arrays of arrays. JavaScript arrays may be sparse: the elements need not have contiguous indexes, and there may be gaps. Every JavaScript array has a length property. For nonsparse arrays, this property specifies the number of elements in the array. For sparse arrays, length is larger than the highest index of any element. JavaScript arrays are a specialized form of JavaScript object, and array indexes are really little more than property names that happen to be integers. JavaScript arrays are dynamic: they grow or shrink as needed, and there is no need to declare a fixed size for the array when you create it or to reallocate it when the size changes.

The Proof!

Let's write some code for the empirical test and find out under the hood, what type of data structure is const a = [ ]

P.S: I'll be using TypeScript for this proof so I have type safety.

You can find the code in the github repo for reference or you can copy it from below and work it out on your own machine

const a: number[] = [];

function time(fn: () => void): number {
    const now = Date.now();
    fn();
    return Date.now() - now;
}

function unshift(number: number) {
    for (let i = 0; i < number; ++i) {
        a.unshift(Math.random());
    }
}

function shift(number: number) {
    for (let i = 0; i < number; ++i) {
        a.shift();
    }
}

function push(number: number) {
    for (let i = 0; i < number; ++i) {
        a.push(Math.random());
    }
}

function pop(number: number) {
    for (let i = 0; i < number; ++i) {
        a.pop();
    }
}

function get(idx: number) {
    return function() {
        return a[idx];
    };
}

function push_arr(count: number) {
    return function() {
        push(count);
    };
}

function pop_arr(count: number) {
    return function() {
        pop(count);
    };
}

function unshift_arr(count: number) {
    return function() {
        unshift(count);
    };
}

function shift_arr(count: number) {
    return function() {
        shift(count);
    };
}

Let's summarize:

• Create an array

• function time: to measure the time of function

  We just want a gauge of how fast or slow things are.

• function unshift : it will unshift " a " a certain amount of times

  unshift in javascript means adding to a list

• function shift will shift "a" a certain number of times

  shift is used for removing from the beginning of the list

• function push will push "a" a certain number amount of time.

  push method is used to add one or more elements to the end of an array

• function pop will pop "a" a certain number of times.

  pop method is used to remove the last element from an array and returns that element.

• function get based on index. Just in case it is a LinkedList under the hood, if we were to get progressively larger indices, we should see a linear slowdown.

• functions push_arr, pop_arr, shift_arr, unshift_arr are higher-order functions that will call push, pop, shift and unshift functions repeatedly.

• then comes the tests ...

Tests

Now we will test our functions and try to figure out what the results indicate

Pro-tip: Whenever we are doing a performance test, you should use a step ladder-type approach that way you can see how it grows so you can run a linear regression.

const tests = [10, 100, 1000, 10000, 100000, 1_000_000, 10_000_000];
console.log("Testing get");
tests.forEach(t => {
    a.length = 0;
    push(t);
    console.log(t, time(get(t - 1)));
});

console.log("push");
tests.forEach(t => {
    a.length = 0;
    push(t);

    console.log(t, time(push_arr(1000)));
});

console.log("pop");
tests.forEach(t => {
    a.length = 0;
    push(t);

    console.log(t, time(pop_arr(1000)));
});

console.log("unshift");
tests.forEach(t => {
    a.length = 0;
    push(t);

    console.log(t, time(unshift_arr(1000)));
});

console.log("shift");
tests.forEach(t => {
    a.length = 0;
    push(t);

    console.log(t, time(shift_arr(1000)));
});

Let's summarize:

• We are gonna test with 10, 100, 100 .... 10000000 elements.

• In first test, "Testing get", we are going to push in the value and do a get for the last element

  The thesis here is, if indexing is linear, we should see a slowdown as the array gets bigger

• In the second test, "push", we are going to push a thousand items after growing to a certain length t.

  If push is based on the number of items within the array, we should theoretically see a slowdown that happens. So it should be linearly getting slower at every single step.

• The same thesis is for "pop", "shift" and "unshift" tests.

Results

Its time to run our code and check how the results pan out and in what direction are we going when we talk about arrays in javascript

As this is TypeScript, run npx ts-node {file-name}.ts

Testing Get

Doesn't matter the size of the array. It's super duper fast.

Testing push

Same case as get, it's quite fast.

Testing pop

Similar results as get and push, it's quite fast.

Testing unshift and shift

Here we observe that the test cases get horribly slow and is having a linear growth.

So what do we infer from these results:

• Instant access

• Instant pushing and popping at the end

• Linear shifting and un-shfting

Hence it's an ArrayList

An array list is a data structure that is similar to an array, but it has a dynamic size and allows you to add and remove elements more efficiently. Array lists are commonly used in programming languages to store and manipulate a collection of items.

Conclusion

We can safely conclude that Javascript arrays are dynamic and it's actually ArrayLists under the hood.

Credits

ThePrimeAgen

---

Thank you for reading this blog. I hope that you have found this information helpful and if you liked it, consider sharing it with others also.

Bye!

Comments

[JianTeng]

Hey,

To add on, shift/unshift in Javascript array is O(n) because it will need to update the index of the rest of the items in the array after adding/removing the first item.

After shift,
item at index 1 become index 0
item at index 2 become index 1
item at index 3 become index 2
...

[Vishal-Aggarwal0305]

Amazing!