Data Structures and algorithims in Javascript

Data Structures basically describes how we can ogarnise and stored in memory when a program processes it.For example, we can store a list of items having the same data-type using the array data structure.

An Algorithm on the other hand, is step by step set of instruction to process the data for a specific purpose. So, an algorithm uterlises various data structures in a logical way to solve a specific computing problem.This is a very important concept in computer science .It gives us more insight on the data we are working with.It enables data scientists to make better machine learning predictions.This is however a challenging topic to most people in the tech industry , according to most people.We are going to look at various python data structures in python and their code examples.

Lists

The list is a most versatile datatype available in Javascript which can be written as a list of comma-separated values (items) between square brackets.Lists are mutable and ordered. It can contain a mix of different data types.

list1 = ['chicken', 'pizza', 2022, 2000]
list2 = [1, 2, 3, 4, 5 ]
list3 = ["a", "b", "c", "d"]

We can access values in a list using their index.
NOTE: we start counting from 0

console.log (list1[0]) //prints the element in the 0 index

We also use the .push() method to add new items into the list eg

list2.push(6) //add 6 to the existing list2

Incase you want to add to a specific place in the list ,we do it as follows

list3[2] = "e" // returns ["a", "b", "e", "d"]

Dictionaries

Dictionary is a mutable and unordered data structure. It permits storing a pair of items (i.e. keys and values).Each key is separated from its value by a colon (:), the items are separated by commas, and the whole thing is enclosed in curly braces. An empty dictionary without any items is written with just two curly braces, like this − {}.
Keys are unique within a dictionary while values may not be. The values of a dictionary can be of any type, but the keys must be of an immutable data type such as strings, numbers, or tuples.

Accessing Values in Dictionary
To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value.
Example:

dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Javascript'}
console.log( "dict['Name']: ", dict['Name'])
console.log( "dict['Age']: ", dict['Age'])

When the above code is executed, it produces the following result :

dict['Name']:  Marrie
dict['Age']:  27

Updating Dictionary
You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example:

dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
dict['Age'] = 28; // update existing entry
dict['School'] = "LuxAcademy"; # Add new entry

console.log ("dict['Age']: ", dict['Age'])
console.log ("dict['School']: ", dict['School'])

When the above code is executed, it produces the following result :

dict['Age']:  28
dict['School']:LuxAcademy

Delete Dictionary Elements
You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation.
To explicitly remove an entire dictionary, just use the del statement.

dict = {'Name': 'Marrie', 'Age': 27, 'Language': 'Python'}
del dict['Name']; // remove entry with key 'Name'
dict.clear();     // remove all entries in dict
del dict ;        // delete entire dictionary

console.log( "dict['Age']: ", dict['Age'])
console.log ("dict['School']: ", dict['School'])

Note −that an exception is raised because after del dict dictionary does not exist any more.

Properties of Dictionary Keys
Dictionary values have no restrictions. They can be any arbitrary javavscript object, either standard objects or user-defined objects. However, same is not true for the keys.
There are two important points to remember about dictionary keys:
*More than one entry per key not allowed. Which means no duplicate key is allowed. When duplicate keys encountered during assignment, the last assignment wins.

dict = {'Name': 'Marrie', 'Age': 27, 'Name': 'Javascript'}
console.log( "dict['Name']: ", dict['Name'])

When the above code is executed, it produces the following result:

dict['Name']:  Javascript

*Keys must be immutable. Which means you can use strings, numbers or tuples as dictionary keys but something like ['key'] is not allowed.

Tuples

A tuple is another container. It is a data type for immutable ordered sequences of elements. Immutable because you can’t add and remove elements from tuples, or sort them in place.
Creating a tuple is as simple as putting different comma-separated values. Optionally you can put these comma-separated values between parentheses also.
For example:

tuple_one = ('javascript', 'java', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
tuple_3 = "a", "b", "c", "d";

The empty tuple is written as two parentheses containing nothing −

languages = ();

To write a tuple containing a single value you have to include a comma, even though there is only one value −

tup1 = (50,);

Like string indices, tuple indices start at 0, and they can be sliced, concatenated, and so on.
Accessing Values in Tuples
To access values in tuple, use the square brackets for slicing along with the index or indices to obtain value available at that index.
For example

tuple_one = ('python', 'javascript', 'c++', 2000);
tuple_two = (1, 2, 3, 4, 5 );
console.log ("tuple_one[0]: ", tuple_two[0]);
console.log ("tuple_two[1:5]: ",tuple_two[1:5]);

When the above code is executed, it produces the following result :

tuple_one[0]:  python
tuple_two[1:5]:  [2, 3, 4, 5]

Updating Tuples
Tuples are immutable which means you cannot update or change the values of tuple elements. You are able to take portions of existing tuples to create new tuples as the following example demonstrates −

tup1 = (12, 34.56);
tup2 = ('abc', 'xyz');

// Following action is not valid for tuples
// tup1[0] = 100;

// So let's create a new tuple as follows
tup3 = tup1 + tup2;
console.log(tup3);

When the above code is executed, it produces the following result:

(12, 34.56, 'abc', 'xyz')

Delete Tuple Elements
Removing individual tuple elements is not possible. There is, of course, nothing wrong with putting together another tuple with the undesired elements discarded.
To explicitly remove an entire tuple, just use the del statement.
For example:

tuple_one = ('python', 'javascript', 'c++', 2000);
console.log( tuple_one);
del tuple_one;
print "After deleting tup : ";
print tuple_one;

Note − an exception raised, this is because after del tup tuple does not exist anymore.
This produces the following result:

('python', 'javascript', 'c++', 2000)

Sets

Set is a mutable and unordered collection of unique elements. It can permit us to remove duplicate quickly from a list.The sets in javacript are typically used for mathematical operations like union, intersection, difference and complement etc.
A javascript set is similar to this mathematical definition with below additional conditions:
*The elements in the set cannot be duplicates.
*The elements in the set are immutable(cannot be modified) but the set as a whole is mutable.
*There is no index attached to any element in a python set. So they do not support any indexing or slicing operation.

Creating a set
A set is created by using the set() function or placing all the elements within a pair of curly braces.

Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
Months={"Jan","Feb","Mar"}
Dates={21,22,17}
console.log(Days)
console.log(Months)
console.log(Dates)

Note how the order of the elements has changed in the result.

set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])
set(['Jan', 'Mar', 'Feb'])
set([17, 21, 22])

Accessing Values in a Set
We cannot access individual values in a set. We can only access all the elements together as shown above. But we can also get a list of individual elements by looping through the set.

//Considering the data above.
Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])

for d in Days:
   console.log(d)

When the above code is executed, it produces the following :

Wed
Sun
Fri
Tue
Mon
Thu
Sat

Adding Items to a Set

We can add elements to a set by using add() method. Remember,there is no specific index attached to the newly added element.

//Adding to the data above. 
Days.add("Sun")
 console.log(Days)

results

set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Removing Item from a Set
We can remove elements from a set by using discard() method.
Example

//Using the data above.
Days.discard("Sun")
 console.log(Days)

Output

set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Union of Sets
The union operation on two sets produces a new set containing all the distinct elements from both the sets. In the below example the element “Wed” is present in both the sets.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA|DaysB
 console.log(AllDays)

Output will be as shown,note the result has only one “wed”.

set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Intersection of Sets
The intersection operation on two sets produces a new set containing only the common elements from both the sets. In the below example the element “Wed” is present in both the sets.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA & DaysB
console.log(AllDays)

Output

set(['Wed'])

Difference of Sets
The difference operation on two sets produces a new set containing only the elements from the first set and none from the second set. In the below example the element “Wed” is present in both the sets so it will not be found in the result set.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA - DaysB
 console.log(AllDays)

Output
When the above code is executed, it produces the following result. Please note the result has only one “wed”.

set(['Mon', 'Tue'])

Compare Sets
We can check if a given set is a subset or superset of another set. The result is True or False depending on the elements present in the sets.
Example

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
SubsetRes = DaysA <= DaysB
SupersetRes = DaysB >= DaysA
 console.log(SubsetRes)
 console.log(SupersetRes)

Output

True
True

Queue

The queue is a linear data structure where elements are in a sequential manner. It follows the F.I.F.O mechanism that means first in first out.
Below the aspects that characterize a queue.
Two ends:
*front → points to starting element
*rear → points to the last element
There are two operations:
*enqueue → inserting an element into the queue. It will be done at the rear.
*dequeue → deleting an element from the queue. It will be done at the front.
There are two conditions:
*overflow → insertion into a queue that is full
*underflow → deletion from the empty queue
Lets see a code example of this:

// program to implement queue data structure

class Queue {
    constructor() {
        this.items = [];
    }

    // add element to the queue
    enqueue(element) {
        return this.items.push(element);
    }

    // remove element from the queue
    dequeue() {
        if(this.items.length > 0) {
            return this.items.shift();
        }
    }

    // view the last element
    peek() {
        return this.items[this.items.length - 1];
    }

    // check if the queue is empty
    isEmpty(){
       return this.items.length == 0;
    }

    // the size of the queue
    size(){
        return this.items.length;
    }

    // empty the queue
    clear(){
        this.items = [];
    }
}

let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
console.log(queue.items);

queue.dequeue();
console.log(queue.items);

console.log(queue.peek());

console.log(queue.isEmpty());

console.log(queue.size());

queue.clear();
console.log(queue.items);

This will procuce the following results.

[1, 2, 4, 8]
[2, 4, 8]
8
false
3
[]

Stack

In the english dictionary the word stack means arranging objects on over another. Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
In the following program we implement it as add and and remove functions. We declare an empty list and use the append() and pop() methods to add and remove the data elements.
Pushing into a Stack
Example

let city = ["New York", "Madrid", "Kathmandu"];

// add "London" to the array
city.push("London");


console.log(city);

// Output: [ 'New York', 'Madrid', 'Kathmandu', 'London' ]

POP from a Stack
As we know we can remove only the top most data element from the stack, we implement a python program which does that. The remove function in the following program returns the top most element. We check the top element by calculating the size of the stack first and then use the in-built pop() method to find out the top most element.

let cities = ["Madrid", "New York", "Kathmandu", "Paris"];

// remove the last element
let removedCity = cities.pop();

console.log(cities)         // ["Madrid", "New York", "Kathmandu"]
console.log(removedCity);   // Paris

Linked list

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

Traversing a Linked List
Singly linked lists can be traversed in only forward direction starting form the first data element. We simply print the value of the next data element by assigning the pointer of the next node to the current data element.

struct node *temp = head;
printf("\n\nList elements are - \n");
while(temp != NULL) {
  printf("%d --->",temp->data);
  temp = temp->next;
}

Output

List elements are - 
1 --->2 --->3 --->

Insertion in a Linked List
Inserting element in the linked list involves reassigning the pointers from the existing nodes to the newly inserted node. Depending on whether the new data element is getting inserted at the beginning or at the middle or at the end of the linked list, we have the below scenarios.
Inserting at the Beginning
This involves pointing the next pointer of the new data node to the current head of the linked list. So the current head of the linked list becomes the second data element and the new node becomes the head of the linked list.
Example

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

Inserting at the End
This involves pointing the next pointer of the the current last node of the linked list to the new data node. So the current last node of the linked list becomes the second last data node and the new node becomes the last node of the linked list.
Example

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

struct node *temp = head;
while(temp->next != NULL){
  temp = temp->next;
}

temp->next = newNode;

Inserting in between two Data Nodes
This involves changing the pointer of a specific node to point to the new node. That is possible by passing in both the new node and the existing node after which the new node will be inserted. So we define an additional class which will change the next pointer of the new node to the next pointer of middle node. Then assign the new node to next pointer of the middle node.

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {
  if(temp->next != NULL) {
    temp = temp->next;
  }
}
newNode->next = temp->next;
temp->next = newNode;

Removing an Item

We can remove an existing node using the key for that node. In the below program we locate the previous node of the node which is to be deleted.Then, point the next pointer of this node to the next node of the node to be deleted.
Example

struct node* temp = head;
while(temp->next->next!=NULL){
  temp = temp->next;
}
temp->next = NULL;

Algorithims

Algorithms are instructions that are formulated in a finite and sequential order to solve problems.
The word algorithm derives itself from the 9th-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose name was Latinized as Algorithmi. Al-Khwārizmī was also an astronomer, geographer, and a scholar in the House of Wisdom in Baghdad.

As you already know algorithms are instructions that are formulated in a finite and sequential order to solve problems.
When we write an algorithm, we have to know what is the exact problem, determine where we need to start and stop and formulate the intermediate steps.

There are three main approaches to solve algorithms:
*Divide et Impera (also known as divide and conquer) → it divides the problem into sub-parts and solves each one separately
*Dynamic programming → it divides the problem into sub-parts remembers the results of the sub-parts and applies it to similar ones
*Greedy algorithms → involve taking the easiest step while solving a problem without worrying about the complexity of the future steps

Tree Traversal Algorithm
Trees in python are non-linear data structures. They are characterized by roots and nodes. I take the class I constructed before for the binary tree.
Tree Traversal refers to visiting each node present in the tree exactly once, in order to update or check them.

struct node {
    int data;
    struct node* left;
    struct node* right;
}

There are three types of tree traversals:
*In-order traversal → refers to visiting the left node, followed by the root and then the right nodes.

inorder(root->left)
display(root->data)
inorder(root->right)

*Pre-order traversal → refers to visiting the root node followed by the left nodes and then the right nodes.

display(root->data)
preorder(root->left)
preorder(root->right)

*Post-order traversal → refers to visiting the left nodes followed by the right nodes and then the root node.

postorder(root->left)
postorder(root->right)
display(root->data)

Sorting Algorithm
The sorting algorithm is used to sort data in some given order. It can be classified in Merge Sort and Bubble Sort.

*Merge Sort → it follows the divide et Impera rule. The given list is first divided into smaller lists and compares adjacent lists and then, reorders them in the desired sequence. So, in summary from unordered elements as input, we need to have ordered elements as output.
*Bubble Sort → it first compares and then sorts adjacent elements if they are not in the specified order.

*Insertion Sort → it picks one item of a given list at the time and places it at the exact spot where it is to be placed.
There are other Sorting Algorithms like Selection Sort and Shell Sort.

Searching Algorithms

*Searching algorithms are used to seek for some elements present in a given dataset. There are many types of search algorithms such as Linear Search, Binary Search, Exponential Search, Interpolation Search, and so on. In this section, we will see the Linear Search and Binary Search.

*Linear Search → in a single-dimensional array we have to search a particular key element. The input is the group of elements and the key element that we want to find. So, we have to compare the key element with each element of the group.