Learn_DATA_STRUCTURE_with_JavaScript

📝 Algorithms and data structures implemented in JavaScript with explanations

1) Stack :-

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

Stack representation :-

The following diagram depicts a stack and its operations

Functions:-

• Push :- Push for placing data onto a stack
• POP :- Pop for removing the top element of a stack
• Peak :- peak for displaying the top element of a stack
• Length/Size :- Determining how many elements are on a stack

Sets-

3) Queue :-

The queue data structure is a way to hold data, it’s similar to a stack while a stack is first in last out and a queue is first in first out. An example of an real life when you were waiting in line to buy something in store the first person get in the line is the first person to get to the cash register.

Queue Representation -

As we now understand that in queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure –

4) Binary Search Tree :-

A tree data structure is a way to hold data that when visualized looks like a tree you would see in nature. All data points in tree are called nodes, the top of the tree is called root node and from it branches out into additional nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

• The left sub-tree of a node has a key less than or equal to its parent node's key.
• The right sub-tree of a node has a key greater than to its parent node's key.

Following are the basic operations of a tree −

• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Pre-order Traversal − Traverses a tree in a pre-order manner.
• In-order Traversal − Traverses a tree in an in-order manner.
• Post-order Traversal − Traverses a tree in a post-order manner.

fig.1

fig.2

fig.3

fig.4

fig.5

fig.6

5) Binary Search Tree: Traversal & Height

Traversal –

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds.

• depth-first traversal
• breadth-first traversal

There are three different types of depth-first traversals :

• PreOrder traversal - visit the parent first and then left and right children;
• InOrder traversal - visit the left child, then the parent and the right child;
• PostOrder traversal - visit left child, then the right child and then the parent;

There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

As an example consider the following tree and its four traversals:

• PreOrder – 9,4,3,6,5,7,17,10,22,20
• InOrder – 3,4,5,6,7,9,10,17,20,22
• PostOrder – 3,5,7,6,4,10,20,22,17,9
• LevelOrder – 9,4,17,3,6,10,22,5,7,20

6) Hash Table :-

In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hash table.

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:

• In universities, each student is assigned a unique roll number that can be used to retrieve information about them.
• In libraries, each book is assigned a unique number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to etc.

A hash table used to implement associative array of mapping of key value pairs. Hash table are common mapping implement the map data structure or object.

In JavaScript , hash table are usually used to implement objects. However it can be helpful to see how they are implemented just to gain better understanding

7) 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 figure.

Array Vs Linked List :-

8) Trie :-

A trie sometimes called prefix tree is a special type of tree used to store associative data structure. See the below diagram is example of an trie.

Where:

Star (*) indicates end of the word.

Words

• ball
• bat
• do
• doll
• dork
• dorm
• send
• sence

9) Heap :-

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then − key(α) ≥ key(β)

The heap properties indicates a specific relationship between the parents node and child nodes you may a max-heap in which all parent nodes are equal than or greater to than the child nodes so you can see the biggest numbers on top and the smallest numbers are bottom or you may have a min heap in which all child nodes are greater than or equal to parent node so the child nodes are biggest one and the parent nodes are smallest one. See the bellow figure max heap and min heap.

Min heap visualizations :- click the below link

https://www.cs.usfca.edu/~galles/visualization/Heap.html

10) Graph :-

The graph data structure is not the same as a graph you may have learned about a math class. Graphs are collection of things and the relationship between them. The data in a graph are called nodes or vertices the connection between the nodesare called edges, one example of graph is a social network where the nodes are you and other people and the edges are whether two people are friends with each other.

There are two major types of graph.

• Directed Graph- Directed graphs are graphs with a direction and its adges
• Undirected Graph- Undirected graphs are graphs without any direction on the edges between nodes

Following two are the most commonly used representations of a graph.

• Adjacency Matrix
• Adjacency List

There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph representation is situation specific. It totally depends on the type of operations to be performed and ease of use.

Adjacency Matrix:

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w. The adjacency matrix for the above example graph is:

Adjacency List:

An array of lists is used. Size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is adjacency list representation of the above graph.

11) Graphs: breadth-first search :-

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules.

• Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
• Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
• Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.