# ES6 JavaScript Data Structures you should Know

## 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.

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 **J****ava 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

- To identify JavaScript data structures and how they are used.
- To solve at least one software engineering problem using the identified data structure. In fact, we will try to solve the same problems we solved in
**Overview of Data Structures in Java Programming Language. Β**

## 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:-

**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.

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. Β

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 **l****inked 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 s**ample 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), `Object`

s have been used as `Map`

s 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.