Data Structures & Algorithms in Javascript

Introduction

Data Structure and Algorithms, the two most fundamental concepts every person with a computer science background must know about it. There are plenty of articles and blogs about Data Structure and algorithms, but it’s my take. As part of a journey to learn DS and algorithms, I decided to write blogs about it. And the best way to learn faster is to teach someone. And it’s loosely based upon the same name as the blog name.

Its a series about data structures I will post the blogs in the below order after completing all the DS, I will start algorithms.

• Arrays
• Stack
• Queue
• Linked list
• Set
• Dictionary
• Hash map
• Tree

All the code in JavaScript but you can follow along with your language of choice. As the core concept of data structure and algorithms would be the same, only the implementation and syntax will differ in other programming languages.

What is Data structure?

A data structure (DS) is a way of organising data in an adequate matter.

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Wikipedia

So, Let’s get started with the first data structure Arrays, which is freely available in any language

What an Array?

An Array is a collection of similar data types store sequentially in indexed format start with Index 0.

Why Should we use Arrays?
Let us consider if you want to store the average temperature of each month of the year for the city that we live in.

const averageTempJan = 31.9; 
const averageTempFeb = 35.3; 
.
.
.
const averageTempDec = 60.8;

However, this is not the best approach. If we store the temperature for only one year, we can manage 12 variables. However, what if we need to store the average temperature for more than one year? Fortunately, this is why arrays were created, and we can easily represent the same information mentioned earlier as follows:

const averageTemp = []; 
averageTemp[0] = 31.9;
averageTemp[1] = 35.3;
averageTemp[2] = 42.4;
.
.
averageTemp[12] = 60.8;

Creating and Initializing an Array

Declaring, creating, and initializing an array in JavaScript is simple, as the following shows,

let daysOfWeek = new Array();         //1
let daysOfWeek = new Array(7);        //2
let daysOfWeek = new Array('Monday','Tuesday','Sunday'); //3
let daysOfWeek = [];                 //4
let daysOfWeek = ['Monday,'Tuesday','Sunday']; //5

We can simply declare and instantiate a new array using the keyword new (line {1}). Also, using the keyword new, we can create a new array specifying the length of the array (line {2}). A third option would be passing the array elements directly to its constructor (line {3}). However, using the new keyword is not considered best practice. If we want to create an array in JavaScript, we can assign empty brackets as (line {4}) or use can initialize the array with some element.

Accessing elements and iterating an array

daysOfWeek[0]    //1
daysOfWeek[12]   //2

To access an element in the array, we can also use brackets, passing the index of the position we would like to access as (line {1}) would return the element at that position. if we try to access the index of the position which is not present in the array then it would return undefined.
For example, let’s say we want to output all the elements from the days of week array. To do so, we need to loop the array and print the elements, starting from index 0 as follows:

for (let index = 0; index < daysOfWeek.length; index++) {
   console.log(daysOfWeek[index]);
}

Inserting an element in Array

let us consider an array of numbers

const listOfNumbers = [];

Insert an element at the end of the array (append)

Javascript API, provide push method which adds the element at the end of the array. as shown in (line {1}) . you can add as many elements as we want as arguments and the push method will append the element respectively (line {2})

listOfNumbers.push(1); //1
listOfNumbers.push(2,3,4); //2

Insert an element at the beginning of the array(prepend)

Javascript API Also provides unshift method which adds the element at the start of the array. as shown in (line {1}) . you can add as many elements as we want as arguments and the push method will prepend the element respectively (line {2})

listOfNumbers.unshift(0);    //1
listOfNumbers.unshift(1,2);  //2

Removing an element in Array

To remove a value from the end of an array, we can use the pop method as shown in (line {1}). And to remove an element from the beginning of the array, we can use the shift method as shown in (line {2}).

listOfNumbers.pop();   //1
listOfNumbers.shift(); //2

Searching an element in Array

We can search an element in an array using linear search
loop through the array starts from index 0 to n
check if the element is equal to the indexed element
if found return the element or return -1

function(array , element){
    for (let index = 0; index < listOfNumbers.length; index++) { 
        if (listOfNumbers[index] == searchElement){
               return listOfNumbers[index];
           }
      }
return -1;
}

Another approach would be to Javascript built-in method indexOf, return the index of the element if present or else return -1. (indexOf is a new method added in Javascript ES6 to other methods visit here)

const index = listOfNumbers.indexOf(searchElement);
if (index != -1) {
  console.log(listOfNumbers[index]);
}

Conclusion :

In Array, data is store in indexed formatted; mostly starting with 0.
Search, Remove and Inserting any data, using an index. Get all the list of methods available here MDN.

Array Methods Complexity

The complexity of algorithms is defined by big O notation which I will cover in an upcoming blog. So, stay tuned for the next blog, in which cover another DS Stack.