In this article, we will explore Data Structures and Algorithms (DSA) using JavaScript.
Data structures and algorithms (DSA) form the foundation of computer science and play a crucial role in efficiently addressing complex problems. They are linked to multiple programming languages, including C++, Java, and Python, among others. Recently, the JavaScript programming language has also established itself as a powerful tool for understanding concepts related to data structures and algorithms.
What is a Data Structure?
A data structure is a systematic approach for organizing, handling, and storing data. The organization of this data is performed in a manner that facilitates easy access and retrieval without complications.
In straightforward terms, we can define a data structure as a collection of data values along with the relationships that exist among them.
Array in JavaScript
An array serves the purpose of holding a set of related information, and in JavaScript, it allows for the inclusion of various data types within a single array. Each item within the array can be retrieved using its index value, which denotes the specific position of the array element. The indexing begins at 0; therefore, in an array containing 5 elements, the fourth element can be accessed by using the index number 3.
Syntax:
const array_name = [item1, item2, item3, …];
In the syntax presented above, the keyword const is utilized to define the array, while array_name refers to the designated name of the array. The elements item1, item2, and item3 represent the items contained within the array.
In JavaScript, it is possible for arrays to contain other arrays. Such arrays are referred to as multidimensional arrays.
Syntax of the multidimensional array:
const arr = [
[2, 4, 6],
[8, 10, 12],
[14, 16, 18]
];
Arrays serve multiple functions, including the addition of data, removal of data, and more.
Example of the array in JavaScript
In the upcoming demonstration, we will construct an array that consists of elements of a uniform data type, as well as an array that includes elements of varying data types.
Code:
const electronic_devices = ["LCD", "Refrigerator", "Microwave"]; //same data type
const example = ["BMW", 10, "laptop"]; //different data types
console.log(electronic_devices); //printing array of same data type
console.log(example); ////printing array of different data types
Output:
Below is the output where we can observe the arrays.
Example of the multidimensional array in JavaScript
In the upcoming demonstration, we will be constructing a multidimensional array.
Code:
const salary = [
["Remo", 25, 75000],
["Raghav", 26, 42000],
["Shakti", 30, 50000],
["Puneet", 35, 45000],
];
console.log("Salary of Remo : " + salary[0][2]);
console.log("Salary of Raghav : " + salary[1][2]);
Output:
Here is the outcome in which we can observe a multidimensional array.
Linked List in JavaScript
A linked list is a data structure designed for the storage of sequential data. The items within the linked list are interconnected. The initial element of the linked list is referred to as the head, while the final element is called the tail. It is possible to add or delete elements from the linked list.
Creating a Node class
The Node class consists of two properties:
data: It stores the actual data of the node.
next: It stores the reference of the next node.
Syntax:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
Creating a LinkedList class
The LinkedList class represents the linked list structure. It is comprised of two main properties, detailed as follows:
head: It is the first node.
tail: It is the last node.
Syntax:
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Printing a LinkedList class
Here is the syntax that is utilized to display the information of each element within the linked list.
Syntax:
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
Demonstration to add new elements in the linked list
We will insert Node y at index 4 and append Node x at the end of the list.
Code:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
add(data) {
const new_node = new Node(data);
if (!this.head) {
this.head = new_node;
this.tail = new_node;
} else {
this.tail.next = new_node;
this.tail = new_node;
}
this.length++;
return this;
}
addToTail(data) {
let new_node = new Node(data);
if (this.head === null) {
this.head = new_node;
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = new_node;
}
addAtPosition(data, position) {
let new_node = new Node(data);
if (position === 1) {
new_node.next = this.head;
this.head = new_node;
return;
}
let current = this.head;
let i = 1;
while (i < position - 1 && current) {
current = current.next;
i++;
}
if (current) {
new_node.next = current.next;
current.next = new_node;
}
}
it
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
const list = new LinkedList();
list.add("Node 1");
list.add("Node 2");
list.add("Node 3");
list.add("Node 4");
console.log("Initial List:");
list.printAll();
console.log("After adding Node y at position 4");
list.addAtPosition("Node y",4);
list.printAll();
console.log("After adding Node x to tail");
list.addToTail("Node x");
list.printAll();
Output:
The output demonstrates that the elements Node y and Node x have been successfully incorporated into the linked list.
Demonstration to remove elements from the linked list
In the upcoming demonstration, we will first eliminate Node 1, followed by the removal of the node located at index 2 from the linked list.
Code:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
add(data) {
const new_node = new Node(data);
if (!this.head) {
this.head = new_node;
this.tail = new_node;
}
else {
this.tail.next = new_node;
this.tail = new_node;
}
this.length++;
return this;
}
remove(data) {
if (!this.head) {
return null;
}
if (this.head.data === data) {
this.head = this.head.next;
this.length--;
return this;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
this.length--;
return this;
}
current = current.next;
}
return null;
}
removeAt(index) {
if (index < 0 || index >= this.length) return null;
if (index === 0) return this.remove();
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
this.length--;
return this;
}
printAll() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
const list = new LinkedList();
list.add("Node 1");
list.add("Node 2");
list.add("Node 3");
list.add("Node 4");
console.log("Initial List:");
list.printAll();
console.log("List after removing Node 1");
list.remove("Node 1");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();
Output:
The following output demonstrates that the nodes have been successfully eliminated from the linked list.
Hash tables in JavaScript
Hash tables are a type of data structure that allows for the creation of a collection of key-value pairs. We can create a hash table utilizing the Object data type along with the Map object.
Utilizing the Object data type
We will employ the Object data type to construct a hash table.
Code:
var cars = new Object();
cars['car1'] = 'Hyundai Creta';
cars['car2'] = 'Toyota Urban Cruiser Taisor';
cars['car3'] = 'Mahindra Bolero';
for (var key in cars) {
if (cars.hasOwnProperty(key)) {
console.log('key is: ' + key + ', value is: ' + cars[key]);
}
}
Output:
The following output demonstrates the application of hash tables.
Utilizing the Map object
A Map is employed to hold a collection of elements where each element is organized as a key-value pair. We will leverage the Map object to create a hash table.
Code:
var cars = new Map();
cars.set('car1', 'Hyundai Creta');
cars.set('car2', 'Toyota Urban Cruiser Taisor');
cars.set('car3', 'Mahindra Bolero');
console.log(cars.get('car3'));
cars.set('car1', 'Hyundai Creta');
console.log(cars.get('car1'));
console.log(cars.size);
cars.delete('car2');
console.log(cars.size);
for (const [key, value] of cars) {
console.log(key + ' = ' + value);
}
Output:
The output below demonstrates the utilization of the Map object.
Trees
Trees represent a data structure employed to connect nodes. A node can have zero or more child nodes. The highest node within the tree is referred to as the root node, while the nodes at the lowest level are termed leaf nodes. All nodes that branch out from the root node are classified as child nodes.
The height of a tree is defined as the measurement of the distance from the root node to the most distant leaf node.
The level, or depth, of a node is ascertained by measuring the distance that separates the node from the root.
Following is the code of the tree:
class TreeNode {
constructor(value) {
this.value = value;
this.descendants = [];
}
}
const seema = new TreeNode('Seema');
const rakhi = new TreeNode('Rakhi');
const krish = new TreeNode('Krish');
const meeta = new TreeNode('Meeta');
const hina = new TreeNode('Hina');
seema.descendants.push(rakhi);
rakhi.descendants.push(krish, meeta, hina);
Above created tree will look like this:
In the tree constructed above, the node designated as seema functions as the root node. The nodes identified as krish, meeta, and hina are classified as leaf nodes.
Seema's height measures 2, while Hina's height is recorded as 0.
Krish is situated at a depth or level of 2, whereas Rakhi is positioned at a depth or level of 1.
Binary tree
The trees that consist of at most two children are called binary tree. There are various kinds of binary trees:
- Full binary tree
- Complete binary tree
- Perfect binary tree
The type of binary tree employed for the purpose of searching is referred to as a binary search tree (BST).
Implementing the binary search tree (BST):
class Node{
constructor(value){
this.value = value
this.left = null
this.right = null
}
}
class BinarySearchTree {
constructor(){
this.root = null
}
insert(value){
const new_node = new Node(value)
if(this.root === null){
this.root = new_node
return this
}
let current = this.root
while(true){
if(value === current.value) return undefined
if(value < current.value){
if(current.left === null){
current.left = new_node
return this
}
current = current.left
} else {
if(current.right === null){
current.right = new_node
return this
}
current = current.right
}
}
}
find(value){
if(this.root === null) return false
let current = this.root,
found = false
while(current && !found){
if(value < current.value){
current = current.left
} else if(value > current.value){
current = current.right
} else {
found = true
}
}
if(!found) return undefined
return current
}
contains(value){
if(this.root === null) return false
let current = this.root,
found = false
while(current && !found){
if(value < current.value){
current = current.left
} else if(value > current.value){
current = current.right
} else {
return true
}
}
return false
}
}
Stack in JavaScript
A stack is a linear data structure that operates on the Last In First Out (LIFO) or First In Last Out (FILO) principle. Operations such as insertion and deletion occur at a single end of the structure. Following the FILO principle, the initial element that is added to the stack will be the last one to be removed. Conversely, under the LIFO principle, the most recently added element is the first to be extracted.
A variety of operations can be executed on the stack, including push, pop, peek, isFull, and isEmpty.
Code:
class Stack {
constructor()
{
this.items = [];
}
push(element)
{
this.items.push(element);
}
pop()
{
if (this.items.length == 0)
return "Welcome";
return this.items.pop();
}
peek()
{
return this.items[this.items.length - 1];
}
isEmpty()
{
return this.items.length == 0;
}
printStack()
{
var str = "";
for (var i = 0; i < this.items.length; i++)
str += this.items[i] + " ";
return str;
}
}
var stack = new Stack();
console.log(stack.isEmpty());
console.log(stack.pop());
stack.push(50);
stack.push(60);
stack.push(20);
console.log(stack.printStack());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.printStack());
Output:
We can observe how a stack is implemented in JavaScript.
Queue in JavaScript
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This indicates that the element that enters the queue first is the one that will be removed first, similar to how a person waiting in line to purchase a train ticket will receive their ticket before anyone else behind them.
A stack supports a range of operations, including push, pop, peek, isFull, and isEmpty.
Code:
class Queue {
constructor() {
this.items = {}
this.frontIndex = 0
this.backIndex = 0
}
enqueue(item) {
this.items[this.backIndex] = item
this.backIndex++
return item + ' added'
}
dequeue() {
const item = this.items[this.frontIndex]
delete this.items[this.frontIndex]
this.frontIndex++
return item
}
peek() {
return this.items[this.frontIndex]
}
get printQueue() {
return this.items;
}
isEmpty() {
return this.items.length == 0;
}
}
const queue = new Queue()
console.log(queue.enqueue(42))
console.log(queue.enqueue(60))
console.log(queue.enqueue(9))
console.log(queue.dequeue())
console.log(queue.enqueue(72))
console.log(queue.peek())
var sq = queue.printQueue;
console.log(sq);
Output:
We can observe how a stack is implemented in JavaScript.
Set in JavaScript
A Set is employed to hold a collection of distinct items that differ from one another. Each item within a Set is unique, meaning that no duplicates are allowed.
Syntax:
new Set([it]);
In the syntax provided above, the argument "it" refers to an iterable object that holds various elements, and each of these elements is incorporated into the newly established set. Even in scenarios where the parameter lacks any elements, a new set will still be instantiated, resulting in an empty set.
Implementation of Set Object
Code:
var set1 = new Set(["kartik", "aryan", "sahil", "bhavna", "anjali"]);
var set2 = new Set("Brilliant");
var set3 = new Set([2, 4, 6, 8, 10, 12]);
var set4 = new Set();
set4.add(2);
set4.add(4);
set4.add(18).add(21).add(60);
console.log(set1);
console.log(set2);
console.log(set3);
console.log(set4);
Output:
We can observe the application of the set in JavaScript.
Graph in JavaScript
A graph is classified as a non-linear data structure consisting of nodes and edges. The edges, which connect the nodes, may also be referred to as arcs or lines. In this context, the nodes are commonly known as vertices.
Code:
class Graph {
constructor(verticesNumber)
{
this.verticesNumber = verticesNumber;
this.AdjList = new Map();
}
addVertex(v)
{
this.AdjList.set(v, []);
}
addEdge(v, x)
{
this.AdjList.get(v).push(x);
this.AdjList.get(x).push(v);
}
printGraph()
{
var getKeys = this.AdjList.keys();
for (var k of getKeys)
{
var getValues = this.AdjList.get(k);
var conc = "";
for (var l of getValues)
conc += l + " ";
console.log(k + " -> " + conc);
}
}
}
var gr = new Graph(6);
var vertices = [ 'H', 'I', 'J', 'K', 'L', 'M' ];
for (var i = 0; i < vertices.length; i++) {
gr.addVertex(vertices[i]);
}
gr.addEdge('H', 'I');
gr.addEdge('H', 'K');
gr.addEdge('H', 'L');
gr.addEdge('I', 'J');
gr.addEdge('K', 'L');
gr.addEdge('L', 'M');
gr.addEdge('L', 'J');
gr.addEdge('J', 'M');
gr.printGraph();
Output:
We can observe the application of graphs within JavaScript.
Algorithms in JavaScript
In the following sections, we will explore a range of algorithms implemented in JavaScript:
Sorting algorithm:
At times, it becomes necessary to arrange numbers in JavaScript, and for this purpose, we have a range of sorting algorithms available, including merge sort, quicksort, selection sort, bubble sort, insertion sort, and heap sort.
Merge sort: This algorithm arranges an array by employing the divide and conquer strategy, which entails breaking down a larger issue into more manageable, smaller issues that can be addressed individually. Subsequently, the solutions to these smaller issues are combined to resolve the larger issue.
Quick sort is a sorting technique that employs the divide and conquer strategy. Initially, it identifies a pivot element from the array. This pivot is then compared with other elements in the array, facilitating the sorting process of the entire array.
Bubble sort: This algorithm organizes an array by implementing a loop that is used to evaluate each element against another element. When the element being compared is found to be less than the current element, their positions are exchanged. This procedure is repeated continuously until the array is fully sorted.
Selection sort: This algorithm organizes an array by initially identifying the first element as the smallest. Subsequently, this element is compared with the other elements in the array. If a smaller element is found, it replaces the current smallest item. This process continues iteratively until the whole array is sorted in order.
Insertion sort is a sorting algorithm that organizes an array by initially treating the first element as sorted. The algorithm then selects the subsequent element to compare it with the already sorted items. If this element is found to be smaller, it is placed in its appropriate position within the sorted section. This process is repeated continuously until the whole array is completely sorted.
Heap sort: A heap represents a tree-structured data organization. The heap sort algorithm organizes an array by leveraging the properties of the heap data structure.
Searching algorithm:
In JavaScript, search algorithms are employed to retrieve data stored within data structures. There are several methods available for locating information within an array:
Linear Search:
This method is employed to locate an element within an array. It iterates through every item in the array, and upon discovering the desired element, it returns the index corresponding to that element.
Binary Search:
It is employed to locate values within a sorted array. This method adheres to a divide-and-conquer strategy, whereby the array is split into two segments to ascertain the presence of the target value.
Dynamic programming
This is an effective technique employed to address intricate challenges. It deconstructs the complicated issue into more manageable subproblems. After resolving the individual subproblems, it integrates the outcomes to tackle the original complex problem.
Greedy algorithm
This algorithm is employed to address intricate issues. It enables the selection of locally optimal decisions at every stage to find a solution. Initially, the algorithm evaluates all available alternatives, subsequently selecting the most favorable one, and continues this iterative process until the desired outcome is achieved.
Implementation of the greedy algorithm:
Code:
function coin_change(coins, amount) {
coins.sort((c, d) => d - c);
let count = 0;
for (let k = 0; k < coins.length; k++) {
while (amount >= coins[k]) {
amount -= coins[k];
count++;
}
}
return count;
}
console.log(coin_change([2, 6, 12], 10));
Output:
Advantages of DSA in JavaScript
- JavaScript programming language is utilized for both front-end and back-end development.
- JavaScript's dynamic nature and expressive syntax make it easy to prototype and experiment with different algorithms and data structures.
- With JavaScript being one of the most popular programming languages, there are abundant resources, libraries, and communities available for learning and implementing DSA concepts.
Conclusion
In this article, we have explored Data Structures and Algorithms (DSA) within the context of JavaScript. We have gained insights into various data structures including arrays, linked lists, hash tables, trees, binary trees, as well as stack, queue, set, and graph. Additionally, we have examined algorithms such as searching algorithms and greedy algorithms, along with the benefits that implementing DSA in JavaScript provides.