Data Structure: Arrays

Array is one of the most commonly used data structure in the computer science world. If you ever had used a list of items such as todo list or playlist or a contacts list on your phone you most probably used an Array.

An array is a data structure for storing more than one data item that has a similar data type. The items of an array are allocated at adjacent memory locations where each identified by at least one array index or key.

Let’s imagine this grid is our computer memory. Each piece of information is stored in one of those small elements (squares) that make the grid.

Arrays take advantage of this “grid” structure to store lists of related information in adjacent memory locations to guarantee extreme efficiency for finding those values.

An array is a container of elements. Where elements have a specific value and data type, like “ABC” (string), TRUE or FALSE (boolean), etc and each element also has its own index, which is used to access the element.

On the above example, we have an array that stores characters data types and a size of 8.

• Array Length = 8;
• First index = 0;
• Last index = 7;

Their elements are next to each other in memory. If you need to access more than one of them, the process is extremely optimized because your computer already knows where the value is located.

Creating an Array

In most of the programming languages, when creating an array we have to supply the length/size of it. That way our computer knows it needs to create X space in memory and in order.

In Java, when declaring int[] nums = new int[5] we get a space in memory for 5 items. If we will want to increase the size, we will have to copy the elements and create a new array with a bigger size.

In JavaScript we can use let nums = new Array(5) to initialize an array. Interesting is, it is just creating a new array whose property length is set to the argument (5) and that's it, meaning there isn't any real elements inside this newly created array.

However, the most common way to create an array in JavaScript is using
let nums = [] . It creates a new array with property length as 0 .

Insertion Operation

Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.

Insert at the end — Array.push()

As I mentioned before, arrays are stored lists of related information in adjacent memory locations. When adding an element to the end of the array, all we do is giving it an index that’s 1 greater than the index of the last element in the array.
It doesn’t matter whether the array has 10 elements or 1000. The number of operations that needs to be performed won’t change.
Therefore, this operation has a Constant Time Complexity and so is O(1).

const arr = ['A','B','C','D','E','F','G','H']

arr.push('I');

Insert at the beginning — Array.unshift()

Adding an element to the beginning of the array is a little different.
When adding an element at the beginning of an array means the new element will have an index of 0. Which means that the index of every other element must be incremented by 1. Since this operation depends on the amount of the elements in the array, this operation has a Linear Time Complexity and is O(n).

const arr = ['A','B','C','D','E','F','G','H'];

arr.unshift('I');

Insert at the middle — Array.splice()

Same as adding an element to the beginning of the array, adding an element at any given index would be O(n).
We can use the Array.splice() method to remove an element and/or insert elements at any position in an array. When we use this method, the number of indices that need to be changed depend on which index you splice. But in the worst case scenario which is if you splice at the very start is O(n).

Removing Operation

Remove operation is to remove one or more data elements from the array. Based on the requirement, a new element can be removed at the beginning, end, or any given index of array.

Remove from the end — Array.pop()

same as adding an element to the end, removing from the end is O(1) because we basically go to the last address of the last index in the array, decrease it by 1 and “free” the removed address.

Remove from the beginning — Array.shift()

same as adding an element to the beginning, removing from the beginning is O(n) because that once we removed the element at index 0, we need to decrease all the elements index’s by 1.

Accessing Or Editing Operations

const arr = ['A','B','C','D','E','F','G','H'];

Let’s say we want to access ‘C’ which is the 3rd value in the array. Since we already know the index of the value, we can just do arr[2] and we will get what we need. You might think that what will happen is that we will need to go through all the array indexes until we reach 2 . However, this is not the case. We already know the element address, we know it is in index 2 so all we need to do is go to this address in the computer memory and get its value.
So that means accessing values of an array have a Constant Time Complexity which we can write as O(1)

Editing an element is the same case as getting an element. by doing
arr[4] = 'I' we already know the address of the index we want to edit (which is index 4 ) so we just go there and edit it.

Searching For An Element

To search for an element in an array, we have to go through the array. How long would it take? well it depends on were the element is.

const arr = ['A','B','C','D','E','F','G','H'];

In JavaScript, we can search for an element by Array.indexOf(). This method gets the index of the value we are looking for.

arr.indexOf('D'); // returns 3

We can also use the ES6 Array.findIndex() method to do this

In our example we were searching for the value 'D' , and we were lucky enough to have it on index 3 so we didn’t have to go through the whole array. But imagine that we were searching for the value 'H' , then we definitely had to go through the entire array. Since when calculating big O notation we calculate the worst case scenario, searching a value in an array is Linear Time Complexity, O(n) because it depends on how big the array is.

Limitations

While array is a popular data structure, it has its limitations:

1. The dimension of an array is determined the moment the array is created, and cannot be changed later on (unless we will copy the elements and create a new array with a bigger size)
2. The array occupies an amount of memory that is proportional to its size, independently of the number of elements that are actually of interest
3. Can take long time for operations such as -
   * Searching an element (where we don’t know the index),
   * Inserting at the beginning or the middle,
   * Removing from the beginning or the middle

To handle those limitations, there is another popular data structure we can use — LinkedList.

Conclusion

In this post, we learned what is an array, how to initialize it and some of the main operations we can do with the array data. As Array has a lot of other built in functions, each of them has different time complexity. But I think that for now this is a good place to start from.