Introduction

For a long time, JavaScript was considered a scripting language for front end developers. This narrative changed when Node JS arrived. With Node, you can write your application server in JavaScript. Because of this, JavaScript popularity has grown and is being used by many software engineers. And with the introduction of TypeScript, JavaScript gets stronger.

As a software engineer, you understand that data structures are an important part in delivering efficient algorithms.

I recently published an article, Overview of static vs dynamic typing in programming languages, in which we discovered that JavaScript is both dynamically and weakly type programming language. When you understand programming language typing, it is also easier to understand and use data structures. Although JavaScript is dynamically typed, it has data types, which you need to understand.

However, being dynamically and weakly typed has some disadvantages. As you may have guessed, that is why Typescript, which is a typed superset of JavaScript, was developed - it introduces type safety. This video can help you understand programming language typing better.

Typing: Static vs Dynamic, Weak vs. Strong / Intro to JavaScript ES6 programming

In order to set-up Node in your windows computer, I have done a comprehensive tutorial How to setup a Node/Express JS project with Sequelize-cli, where we start from setting up node, to building a sample application.

The motivation of writing this walk-through is to benefit JavaScript developers having completed one for Java developers, Overview of Data Structures in Java Programming Language. Β 

The benefits of using data structures include;-

  • Enables software engineers to build efficient (in terms of speed and memory usage) algorithms.
  • Enables easier representation (in computer memory) and manipulation of large datasets.

Objectives of this walk-through

Prerequisite

  • A basic understanding of JavaScript language, preferably ES6 specifications and above - from time to time we shall be writing JavaScript classes.
  • Ensure you can run JavaScript - you could install Node in your machine or use freely available online IDEs. Β 
  • A basic understanding of algorithm running time and space complexity.
  • A basic knowledge of abstract data structures.

So let's dive and start looking at the data structures. Do remember that for variable declaration, we will mostly be using let and const instead of var. You may want to know why by checking out Declaring a Winner πŸ₯‡ Between JavaScript's var, let and const.

Before you start, look at a teaser in Overview of Data Structures in Java Programming Language. Β 

1. JavaScript Array

An array holds a collection of items of any data type.

Unlike in Java, a JavaScript array is expandable - you can just add items as they come without worrying about its size.

An array is a JavaScript inbuilt object. You create an array as shown below:-

//Using array literal
let myArray = []; //assign values later
let myArray = [3,2,5,0,1,7];
//Using Array class constructor.
let myArray = new Array(3,2,5,0,1,7);
JavaScript Array declaration. 

Problem:

See Sample problem 1 in Overview of Data Structures in Java Programming Language. Β 

In JavaScript/Node, the problem can be solved as shown below;-

//define a class Solution and function called twoSum;
class Solution {
    twoSum (nums, target){
        let n = nums.length;
        //rightPointer starts from right moving left
        let rightPointer = n-1;
        //leftPointer starts from the left moving right 
        let leftPointer = 0;
        let output = [];
        while (leftPointer < rightPointer) {
            let sum = nums[leftPointer] + nums[rightPointer];
            if (sum == target){
                //push these numbers in an array and return it
                output.push(nums[leftPointer]);
                output.push(nums[rightPointer]);
                return output;
            }else if (sum < target) {
			    //we need to move leftPointer rightwise
			    leftPointer ++;
            }else{
                //move rightPointer leftwise 
			    rightPointer--;
            }

        }
        return output;
    }    
}
module.exports = Solution;

Test your code:

//Import your class
const Solution = require('./solution');
//Sample array 
let a = [2,7,11,15];
//create object
let sol = new Solution;
//Print what is returned by twoSum function
console.log(sol.twoSum(a,9));
//ouput should be [2,7]

It is worth noting that JavaScript does not support Associative arrays. You should use objects when you want the element keys to be strings (text). You should use arrays when you want the element names to be numbers.

2. JavaScript Objects

If you wish to create something like an array but instead of using index as a number, you want to use text, then use JavaScript objects.

The named index is like a key to a value. Β 

A JavaScript object can be created as follows;-

let sampleObject = {}
//Or
let sampleObject = new Object();
//Or if you have values e.g for a car
let sampleObject = {
    type:"Fiat", 
    model:"500", 
    color:"white"
}

Although you can use an object as an associative array, the object does not give you a length property like that of an array. If you need a name key and value with a length property, you could consider a map, which we will look at shortly.

Problem:

A good example where you could combine an array and an object is reading records of a table in a database. You create an object whose properties are table column names. Then proceed to add those object into an array. That would be a proper JSON data - However, JSON is more of a data format than a data structure.

Suppose you have a table called user with columns full_name, age and address, if you want to represent the table data, then you can use an array of objects. See illustration below.

let table = [];
let record1 = {
    full_name: 'Derdus',
    age:30,
    address:'Nairobi'
};
table.push(record1);

let record2 = {
    full_name: 'Joe',
    age:34,
    address:'Mombasa'
};
table.push(record2);

The JSON representation would be like this.

[
    {
        full_name: 'Derdus',
        age:30,
        address:'Nairobi'
    },
    {
        full_name: 'Joe',
        age:34,
        address:'Mombasa'
    }
]

Additionally, if you are presented with an array of objects, you could loop through the array and extract data from the objects using the object properties.

Suppose I want to compute the average age of the users and all I have is the JSON data (i.e array of objects), it can be done by using two ways as follows;-

Using a for loop:

//using a for loop
class Solution {
	aveAge(table){
		let n = table.length;
		let sum = 0;
		for (let i = 0; i < n; i++) {
    			sum = sum + table[i].age;    
		}
		let average = sum/n;
		return average;
    }
}

Using a foreach loop:

//using a foreach loop
class Solution {
	aveAge(table){
    	let n = table.length;
		let sum = 0;
		table.forEach(obj => { //Arrow function 
        	//callback function execution. 
    		sum = sum + obj.age;  
		});
		let average = sum/n;
        return average;
    }
}

3. JavaScript 2D Array

A 2-D array is an array where each array item is also an array.

JavaScript does not provide the multidimensional array natively. However, you can create a multidimensional array by defining an array as an element of another array.

The video below explains how to simply create a 2D array in JavaScript.

4 easy ways to declare JavaScript array

The Sample problem 2 in Overview of Data Structures in Java Programming Language is a Sudoku board, which you have to test if it is validly filled. Β 

The Sudoku board is defined as shown below. It is advisable to look at the Set data structure before you can solve this Sudoku problem. We are using a JavaScript Set to ensure numbers in columns, rows and 3x3 squares are unique. Β 

let board = [	
                [ 3, 1, 6,  5, 7, 8, 4, 9, 2 ], 
                [ 5, 2, 9,  1, 3, 4, 7, 6, 8 ], 
                [ 4, 8, 7,  6, 2, 9, 5, 3, 1 ],        				
                [ 2, 6, 3,  4, 1, 5, 9, 8, 7 ], 
                [ 9, 7, 4,  8, 6, 3, 1, 2, 5 ], 
                [ 8, 5, 1,  7, 9, 2, 6, 4, 3 ],        				
                [ 1, 3, 8,  9, 4, 7, 2, 5, 6 ], 
                [ 6, 9, 2,  3, 5, 1, 8, 7, 4 ], 
                [ 7, 4, 5,  2, 8, 6, 3, 1, 9 ]
            ];
A solved Sudoku board

The solution is as shown below:

//A Solution class with 4 methods. Create an object and call validSudoku method. You must pass the board to this method.  
class Solution {
     async validSudoku (board){
        const validRow =   await this.validRows(board,0,9);
        const validColumn =  await this.validCols(board,0,9);
        let miniSquares = true;
        //handling the 3x3 mini-squares.
        for(let i = 0; i<9, i+3;){
            for(let j=0; j<9; j+3){
                miniSquares  = miniSquares &&  await this.validRows (board, i, i+3) &&  await this.validCols(board, j, j+3);
            }
        }
        const result = miniSquares && validRow && validColumn;
        return result;
    }

    async validRows(board, start, end){
        for(let i = start; i<end; i++){
            let set = new Set();
            for(let j = start; j<end; j++){
                if (await this.validRange(board[i][j]) == false) {
					return false;
				}
                if (set.has(board[i][j])){
                    //a duplicate was found, so invalid Sudoku
                    return false;
                }else{
                    set.add(board[i][j]);
                }
            }
        }
        return true;
    }

    async validCols (board, start, end){
        for(let i = start; i<end; i++){
            let set = new Set();
            for(let j = start; j<end; j++){
                if (await this.validRange(board[j][i]) == false) {
					return false;
				}
                if (set.has(board[j][i])){
                    //a duplicate was found, so invalid Sudoku
                    return false;
                }else{
                    set.add(board[j][i]);
                }
            }
        }
        return true;
    }


     validRange(num) {
        if (num>0 && num<=9) {
            return true;
        }
        return false;
     }
}

module.exports = Solution;

4. JavaScript Linked List

JavaScript does not implement a linked list out of the box but you could implement one yourself or use available libraries from npm. We understand that in programming languages such as Java, an array has a limitation because its size has to be known beforehand.

However, we noted that a JavaScript array expands as it receives more elements. Thus, an array behaves like a list.

So the question is, Is it worth implementing a linked list in JavaScript?

Well it depends on what you want to do, we say yes.

If you have a list of items and a deletion operation is frequent, then using a doubly linked list achieves constant running time O(1) whereas a similar operation in an array has a linear run time, O(n), because when you delete an element from an array, you have to reorganize the remaining elements, shifting forward, if the deletion did not happen on the last element.

Sample problem:

Suppose you receive streaming data and you want to store it in memory. You are certain that there will be frequent deletion operations. Design this data structure and let it support store and delete operations both of which happen in constant running time, O(n).

Intuition:

Data is coming in and we do not know how many elements further, because the two operations must happen in constant running time, a doubly linked list is suitable.

We will use a linked list library, Linked List

Proceed and install this package:

npm install double-linked-list

We can call our data structure FastStore

const LinkedList = require('double-linked-list');  
class FastStore{
    constructor(){
        this.list = new LinkedList();
    }
    store(value){
        this.list.push(value);
    }


    delete (index){
        this.list.remove(index);
    }
}
module.exports = FastStore;

5. JavaScript Stack

Java does not implement a stack because its array can do the job.

You well know that a stack represents a last-in-first-out (LIFO) stack of objects.

Simply, if you want a data structure where you insert elements and when you want to remove them, you start with last inserted element, then a stack is the best.

Problem: Valid parenthesis

We will solve the problem described in Overview of Data Structures in Java Programming Language, sample problem 3.

We will use a JavaScript array, but we know that we are adding elements at the end and removing elements from the end. Both operations happen in constant time, O(1).

//a function isValid, which receives the parenthesis string and returns true if it is valid or false otherwise.  
isValid(parenthesis){
    
    //let parenthesis = new String("parenthesi");
    if (parenthesis.length == 0){
        return true;
    }
    let stack = [];

    for (let i = 0; i < parenthesis.length; i++) {
        //if it is an opening, push it into a stack
        if (parenthesis.charAt(i) == '{' || parenthesis.charAt(i) == '(' || parenthesis.charAt(i) == '['){
            //if it is an opening bracket, push it into a stack
            stack.push(parenthesis.charAt(i));
        }else if (parenthesis.charAt(i) == '}'){
            //if it is curl and closing
            //we need to check if whatever at the top of the stack
            //is curl opening
            if(stack.length != 0 && stack[stack.length-1] == '{'){
                stack.pop();
            }else{
                stack.push();
            }
        }else if (parenthesis.charAt(i) == ')'){
            if(stack.length != 0 && stack[stack.length-1] == '('){
                stack.pop();
            }else{
                stack.push();
            }
        }else if(parenthesis.charAt(i) == ']'){
            if(stack.length != 0 && stack[stack.length-1] == '['){
                stack.pop();
            }else{
                stack.push();
            }
        }     
    }

    if(stack.length == 0){
        return true;
    }
    return false;
}

5. JavaScript Queue

A Queue works on the FIFO(First in First Out) principle. Hence, it performs two basic operations that is addition of elements at the end of the queue and removal of elements from the front of the queue.

Queue is not implemented in JavaScript but you can use a JavaScript array to achieve a queue operation.

We shall enqueue elements at the end of the queue using push method and dequeue using shift method.

Problem: - Binary Tree BFS or Level Order Tree Traversal

We will solve sample problem 6 in Overview of Data Structures in Java Programming Language.

//JS binary definition; file name: treenode.js
class TreeNode { 
    constructor(data){ 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
}
module.exports = TreeNode;

A Solution class with a method BFS

//file name solution.js
const TreeNode = require('./treenode');
class Solution {
    BFS(root){
        let queue = [];
        if(root == null){
            return;
        }
        queue.push(root);
        while(queue.length !=0 ){
            let head = queue.shift();
            console.log(head.data);

			if (head.left != null) {
				queue.push(head.left);
			}
			
			if (head.right != null) {
				queue.push(head.right);
			}
        }
    }
}

Create a sample binary tree and test your code:

let sol = new Solution();
let root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(30);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(8);

root.left.left.left = new TreeNode(1);
root.right.right = new TreeNode(40);

sol.BFS(root);

The biggest challenge when using an array to implement a queue, is that the shift operation has a linear run time, O(n), thus it might be too slow if the queue gets large.

To address this problem, we can use a doubly linked list, which keep a reference to the head and tail. We enqueue at the tail and dequeue at the head. With a linked list both the enqueue and dequeue operations will happen at constant time, O(1). If you have done a bit of Java, you should already know that a Queue in Java is implemented as a LinkedList.

In our implementation above, we are only going to do a modification to the BFS method.

We will use the same package we used to implement a queue, which we earlier used to illustrate the linked list.

BFS(root){
    let queue = new LinkedList();
    if(root == null){
        return;
    }
    queue.push(root);
    while(queue.length !=0 ){
        let head = queue.remove(0);
        console.log(head.data);

        if (head.left != null) {
            queue.push(head.left);
        }
        
        if (head.right != null) {
            queue.push(head.right);
        }
    }
}

Do not forget to import the package.

const LinkedList = require('double-linked-list');

7. JavaScript Priority Queue

A priority queue is an abstract data type similar to a regular queue data structure in which each element additionally has a priority associated with it.

JavaScript does not implement a priority queue out of the box but there are plenty of npm libraries, which you can use or you can implement it yourself.

This video explains the relationship between a queue, a priority queue Β and the implementation of a priority queue as a heap.

Problem:

We are going to use a priority queue to solve a Leetcode problem number 1046 - Last Stone Weight.

Install this npm package, which implements a priority queue as follows

 npm install priorityqueuejs
lastStoneWeight (stones){
    let pq = new PriorityQueue();
    stones.forEach(stone => {
        pq.enq(stone);
    });

    while(pq.size() > 1){
        let largestStone = pq.deq();
        let secondLargestStone = pq.deq();
        if(largestStone != secondLargestStone){
            let difference = largestStone - secondLargestStone;
            pq.enq(difference);
        }
    }
    if(pq.size() == 0){
        return 0;
    }
    return pq.deq();
}

Do not forget to import the library.

const PriorityQueue = require('priorityqueuejs');

8. JavaScript Map

A map data structure can be used as an associative array, but its main purpose is to maintain a key-value structure and enable fast look-up.

A JavaScript Map object holds key-value pairs and remembers the original insertion order of the keys - Java map does not preserve the insertion order.

We discussed about a JavaScript Object earlier and it is similar to Mapβ€”both let you set keys to values, retrieve those values, delete keys, and detect whether something is stored at a key. For this reason (and because there were no built-in alternatives), Objects have been used as Maps historically.

Problem:

We are going to solve Sample problem 8 in Overview of Data Structures in Java Programming Language.

Our solution would look like this:

luckyInteger(nums){
    let happyNumber = -1;	
    if(nums.length == 0){
        return happyNumber;
    }
    //map: key is the number and value is its frequency. 
    let map = new Map();
    for(let i=0; i<nums.length;i++){
        if(map.has(nums[i])){
            map.set(nums[i], map.get( nums[i]) + 1);
        }else{
            map.set(nums[i], 1);
        }
    }
    //iterate and check the number equal to its frequence. 
    for (let [key, value] of map.entries()){
        if(key==value){
            return key;
        }
    }
    return happyNumber;
}

Because JavaScript Map preserves insertion order, there is no need of thinking about things like LinkedHashMap which are in Java.

If you combine a doubly linked list and a map, your can easily build LRU cache.

There is a problem in Leetcode, LRU cache, problem number 146, check it out.

If you do not understand caching, watch this short video.

9. JavaScript Set

The Set object lets you store unique values of any type. JavaScript Set objects are collections of values. You can iterate through the elements of a set in insertion order it preserves insertion order. Β 

A set can be useful in writing efficient algorithms to a wide range of software engineering problems.

For instance, earlier we used a set to check unique entries in a Sudoku board.

In this case, let us solve Sample problem 9 in Overview of Data Structures in Java Programming Language.

hasDuplicates (nums) {
    let set = new Set ();
    let n = nums.length;
    if (n <=1){
        return false;
    }
    for (let i = 0; i < n; i++) {
        if(set.has(nums[i])){
            return true;
        }else{
            set.add(nums[i]);
        }            
    }
    return false;
}

10. Graphs and binary trees

Graphs and binary trees are non-linear data structures and have not been implemented in JavaScript.

They can be implemented by creating nodes using JavaScript classes. For example, see a TreeNode class representation of a binary tree node in section 5 of this article.

Also, checkout section 13 and onward in Overview of Data Structures in Java Programming Language.

Voila! We are done.

I will be glad to hear from you in the comments section.

You've successfully subscribed to Decoded For Devs
Welcome back! You've successfully signed in.
Great! You've successfully signed up.
Your link has expired
Success! Your account is fully activated, you now have access to all content.