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

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

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.

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:

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.

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

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(β)

Min heap visualizations :- click the below link

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

10) Graph :-

There are two major types of graph.

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

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.