Deep Dive into Data structures using Javascript - Arrays

What is an array?

Array, sometimes called "list" is a fundamental data structure. It is the simplest and most used data structure across different languages, because of it's simplicity and fast way of retrieving data. In addition to that they have the least amount of rules compared to other data structures.

Arrays helps us to organize our data items sequentially.

Anatomy of an array

• Arrays uses indexes to identify item positions. These index numbers are references to the item locations in computer memory.
• Index numbers starts from zero.
• Same index will always give you the same element (unless it is removed or updated).
• Duplicate values are allowed in arrays.

Arrays in Javascript and other languages

There are actually 2 types of arrays, depends on the language we use: Dynamic and Static arrays.

In Javascript and languages like Python and Ruby, we have Dynamic Arrays.

In languages that are good at low level memory management like C, C++, we have Static Arrays.

What is the difference between Static and Dynamic Arrays?

• Static Array: If you are using a Static Array, you need your array length being pre-defined. In other words, you need to specify the number of elements ahead of time. By doing this, static array is declared at compiled time, so the memory allocation of the array is done at compile time. Memory management here is easier because everything is also done at compile time and no re-sizing or variable size is allowed.

// C++ - Initializing a static array

int myNumbers [5] = { 16, 2, 77, 40, 12071 };

• Dynamic Array: If you are using a Dynamic Array, you don't need to define your array length ahead of time. Here you are allowed to copy, rebuild, extend or shrink your array at a new location. Even you declare the Dynamic Array at compile time, number of elements won't be determined until run-time. With this, value that determines the size can be any variable during runtime.
• In simpler terms, you don't have to worry about the resizing and memory allocation on low level when you use Dynamic arrays. They extend and shrink when you add / remove elements, and memory allocation part is handled under the hood.

Data types that an Array can hold between different languages

Data types for arrays can also differ depends on the language you use. In languages like Javascript, an array can contain any type of data - not only primitives, they can include even arrays, objects and functions. In typed languages like C / C++, you need to predefine the data type (array of strings, array of integers, etc..).

When and when not to use an array in Javascript?

As a thumb of rule, it is good to remember each data structure have their advantages and disadvantages - and same thing also applies when it comes to arrays.

Let's take a look at the Big O of common array operations to get a better picture:

Use arrays:

• When you need to work with a sequential data. For example, if you need to do iterations, additions, storing the order, get count of total items, arrays will be a good choice.

Do not use arrays:

• If you want to work with a single big entity, need to have unique named properties, you want quick insert / access / update / delete, using an Object will be a better choice. Because if you don't know the index of the element you want to access, you will need to search for it - which will be a costly operation in a large array compared to an Object. Same thing applies for insertion, update and deletion.
• But there is a good point to keep in mind - you can get good performance with access as long as you know the index. Insert and delete operations will work good as well - as long as you do these at the end of an array. Let's take a closer look:

Why insert & delete operations works better at the end of an array

This happens because when we work at the last index, changes that happens there does not effect the previous items. To understand this better, here is an example of what happens when we do insert / delete at the beginning:

Insert & delete at the beginning

// INSERTION AT THE BEGINNING
const array1 = [ 'a', 'b', 'c' ]

array1.unshift('z')

console.log(array1) // => Output: ['z', 'a', 'b', 'c']

// Now the indexes of 'a', 'b' and 'c' have changed from 0, 1, 2 to 1, 2, 3 respectively

// DELETION AT THE BEGINNING
const array2 = [ 'a', 'b', 'c' ]

const firstElement = array2.shift()

console.log(firstElement) // => Output: 'a'
console.log(array2) // => Output: ['b', 'c']

// Now the indexes of 'b' and 'c' have changed from 1, 2 to 0, 1 respectively

As we see on the examples, inserting or deleting an element at the beginning of an array effects the indexes of all other elements. Which means extra work under the hood to point each element to new indexes. Therefore we have O(n) - Linear time cost here.

Now you maybe thinking, "How about if we have inserted / deleted an element at the middle of an array instead of beginning?"

We will be still having O(n) Linear time. Because at the middle it will be O(n / 2) => and we always drop the constants to calculate the end result of Big O => O(n)

When it comes to insert & delete at the end of an array, we see none of them effects previous elements - which means no need for re-indexing here. Therefore the cost will be O(1) - Constant time.

Insert & delete at the end

// INSERTION AT THE END
const array1 = [ 'a', 'b', 'c' ]

array1.push('z')

console.log(array1) // => Output: ['a', 'b', 'c', 'z']

// No changes on indexes for previous elements

// DELETION AT THE END
const array2 = [ 'a', 'b', 'c' ]

const lastElement = array2.pop()

console.log(lastElement) // => Output: 'c'
console.log(array2) // => Output: ['a', 'b']

// No changes on indexes for previous elements

Mutable and Immutable Array methods in Javascript

In Javascript, Arrays and Objects are reference types and they are mutable, therefore you need to keep this in mind whenever you are working with them to prevent pitfalls that comes with mutation.

In some cases you will actually want to mutate the original array in purpose - and in some other cases you will want to keep the original array immutable.

Here is an example of what can go wrong:

const namesAscending = ['a', 'b', 'c']
const namesDescending = namesAscending.reverse()

console.log(namesDescending) // OUTPUT => ['c', 'b', 'a']
console.log(namesAscending) // OUTPUT => ['c', 'b', 'a']

By the looks of the code here, you probably want to keep the namesAscending as it is - in same order. You wanted to get a descending version by simply using reverse() method on ascending one, which worked fine. But now we ended up having both arrays in descending order.

Why? Because the built-in reverse() method mutates the array, and our second variable is referencing the first variable. In this case they both point to same address in memory - a change in either of them will effect the one other.

To prevent this pitfall, there is a simple solution: use a spread operator whenever you want to keep your original array immutable:

const namesAscending = ['a', 'b', 'c']
const namesDescending = [...namesAscending].reverse()

console.log(namesDescending) // OUTPUT => ['c', 'b', 'a']
console.log(namesAscending) // OUTPUT => ['a', 'b', 'c']

What was different this time? Only difference was we created a brand new array by using a spread operator, THEN used the reverse method afterwards. With this we were able to keep our original array immutable.

In some cases, you won't need the spread operator to keep the original array immutable. Why? This is because some built-in array methods in Javascript mutates the original array, while some others returns a brand new array.

We can simplify the workaround for immutability like this:

• If you are using a built-in method that returns a new array, you don't need to use spread operator.
• If you are using a built-in method that mutates the array, you will need to create a new array using spread operator.

And here is a list of common Mutable & Immutable built-in Array methods in Javascript:

Mutable Array Methods:

• .pop()
• .push()
• .shift()
• .unshift()
• .reverse()
• .sort()
• .splice()
• .copyWithin()
• .fill()

Immutable Array Methods

• .forEach()
• .map() - Returns new array
• .filter() - Returns new array
• .reduce()
• .reduceRight()
• .slice() - Returns new array
• .concat() - Returns new array
• .entries() - Returns new array iterator object
• .values() - Returns new array iterator object
• .every()
• .find()
• .findIndex()
• .flat() - Returns new array
• .includes()
• .indexOf()
• .join()
• .keys() - Returns new array iterator object
• .lastIndexOf()
• .some()
• .toLocaleString()
• .toSource()
• .toString()

Thanks for reading!