Introduction

Arrays are one of the most important data structures that you need to know in order to succeed as a software developer.

In this article, we'll take a look at what is a data structure? The array data structure and why is it important?

What is a Data Structure?

A data structure is a particular way of organizing data in a computer so that it can be used effectively. Just like in real life, we determine the best containers to store certain items based on what they are and how we plan to access them. The same is true for data structures.

Depending on the type of data you have and how you plan to access it, you need to find the right data structure that will help you organize and perform any sort of operation on that data. But there is no perfect data structure. Every data structure has its strengths and its weaknesses and you have to consider the trade-offs before deciding which one to use.

The way we understand the strengths and weaknesses of a data structure is through a mathematical concept known as Big O Notation. I have a write up on it here.

Definition of an Array

So, let’s get started with one of the most common data structures that beginners need to be familiar with, Arrays.

An array is a linear data structure used to store elements at a contiguous location. They are sometimes called lists and organizes items sequentially i.e., one after another in memory. If all you need to do is store some data and iterate over it, arrays are the best choice especially if you know the indexes of the element you are storing.

Types of Arrays

There are two types of arrays which are:

1. Static Arrays
2. Dynamic Arrays

Static Arrays

These are fixed in size i.e., you need to specify the number of elements your array will hold ahead of time.

Dynamic Arrays

This type of array allows us to copy and rebuild an array at a new location which may have more memory if we want that. Dynamic arrays expand as more elements are added, so size doesn’t need to be determined ahead of time.

Array operation and Big O notation

• Lookup

• Push

• Insertion

• Deletion

Lookup

In an array, lookup or access operations happen in constant time O(1), since you have the index of the element you want to access.

const strings = ['a', 'b', 'c', 'd', 'e', 'f', ''];
strings[1];

//output = 'b'

Push

Push operation allows us to add an element to the end of the array. The push operation is an O(1) operation since the element is just added at the end of the array without looping over or changing the indexes of the other elements.

const strings = ['a', 'b', 'c', 'd', 'e', 'f'];
string.push('g');
console.log(strings);

//output = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

Insertion

We can insert an element into an array either at the beginning, at the end, or at a given index. The time complexity of adding elements at the end of an array is O(1) as was shown in the push operation. To add an element at the beginning of the array, we have to move other items by one index. This is a linear O(n) operation. Insertion array examples are push and unshift operations.

const strings = ['a', 'b', 'c', 'd', 'e', 'f'];
string.unshift('g');
console.log(strings);

//output = ['g', 'a', 'b', 'c', 'd', 'e', 'f']

Deletion

We can delete an element in an array from the beginning, at the end or from a given index in the Array. Removing from the end is a pop array operation and it has a constant, O(1) time complexity since you are simply removing the last element using its index.

Deletion from the beginning of an array has a linear time O(n) complexity as you would be removing the first index and shifting the other indexes to the start of the array where an element has been removed from. Deletion array operations are pop and shift operation.

Pop operation with a constant time complexity, O(1)

const strings = ['a', 'b', 'c', 'd', 'e', 'f'];
strings.pop('f');
console.log(strings);

//output = ['a', 'b', 'c', 'd', 'e']

Shift operation with a linear time complexity, O(n)

const strings = ['a', 'b', 'c', 'd', 'e', 'f'];
strings.shift();
console.log(strings);

//output = ['b', 'c', 'd', 'e', 'f']

When considering efficiency, an array should be used when you want to carry out:

• Fast lookups

• Fast push/pop

• When you have ordered elements

An array should not be used for:

• Insertion, it has slow inserts, especially if its not at the end if the array

• Deletion, if its not at the end of the array, we have to shift arrays

• Fixed size (a problem with static arrays)

Wrapping Up

You should always keep in mind that there are tradeoffs when choosing the right data structure to use and depending on the kind of operation you want to carry out, you may need to use an array or opt for another data structure to have a more efficient code.