Data Structure

MADE BY:
MD. ASHIKUZZ ZAMAN (ASHIK)

ID: 220119
 INDEX
1. Data Structure Definition and Operations 3
2. Recursion: 4
3. Sorting: 5
4. Array: 2D 8
4. Stack: 9
5. Queue: 10
6. Circular Queue: 11
7. Linkedlist: 13
8. Polish Notation: 16
9. Tree: 17
11. Spanning Tree: 2
12. Heap: 24
13. Hash Table: 26
1. Data Structure Definition and Operations

A data structure is a way of organizing and managing data so that it can be used

efficiently.

Basic Operations

The data in the data structures are processed by certain operations.

Traversing: Visiting each element in a data structure to access or display its contents.
Searching: Finding a specific element within a data structure.
Insertion: Adding a new element into a data structure.
Deletion: Removing an existing element from a data structure.
Sorting: Arranging elements in a specific order (e.g., ascending or descending).
Merging: Combining elements from two or more data structures into one.

Linear Vs Non-linear Data Structures:

2. Recursion:

Recursion is the process in which a function calls itself again and again.

Key Concepts of Recursion:

● Base Case: The condition under which the recursion stops, preventing infinite recursion
and eventual stack overflow.
● Recursive Case: The part of the function where it calls itself with modified arguments to
work towards the base case.

Factorial:
int factorial(int n) {
if (n <= 1) {
return 1; // Base case
} else {
return n * factorial(n - 1); // Recursive case
}
}

Fibonacci:
int fibonacci(int n) {
if (n <= 1) {
return n; // Base case
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
}

Iterative Implementation:
int fibonacci(int n) {
if (n <= 1) {
return n;
}

int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}
3. Sorting:
A Sorting Algorithm is used to rearrange a given array or list of elements according to a
comparison operator on the elements.

Types of Sorting Techniques in Data Structure :

Several sorting techniques in data structure can be used to sort data elements in an array or
list. The most common types of sorting in data structure are:-

Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.

Selection Sort: Selects the smallest (or largest) element from the unsorted portion and places it
in the correct position.

Insertion Sort: Builds the sorted array one element at a time by inserting each new element
into its proper position.

Merge Sort: Divides the array into halves, recursively sorts each half, and then merges the
sorted halves.

Quick Sort: Chooses a pivot element, partitions the array around the pivot, and recursively
sorts the partitions.

1. Bubble Sort:

Initial Array: [5, 1, 4, 2, 8]

Steps:

1. Pass 1:
○ [1, 5, 4, 2, 8] (5 and 1 swapped)
○ [1, 4, 5, 2, 8] (5 and 4 swapped)
○ [1, 4, 2, 5, 8] (5 and 2 swapped)
○ [1, 4, 2, 5, 8] (8 is in the correct position)
2. Pass 2:
○ [1, 4, 2, 5, 8] (no swap needed between 1 and 4)
○ [1, 2, 4, 5, 8] (4 and 2 swapped)
3. Pass 3:
○ [1, 2, 4, 5, 8] (no swap needed)
4. Pass 4:
○ [1, 2, 4, 5, 8] (no swap needed)

Sorted Array: [1, 2, 4, 5, 8]

pseudocode:
procedure bubbleSort(array, size)
for i from 0 to size - 1 do
for j from 0 to size - i - 2 do
if array[j] > array[j + 1]
swap array[j] with array[j + 1]
end bubbleSort

C++ code:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < n-i-1; ++j) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);//make a swap function
}
}
}
}
2. Selection Sort:

Initial Array: [5, 1, 4, 2, 8]

Steps:

1. Pass 1:
○ Find minimum in [5, 1, 4, 2, 8]: Minimum is 1
○ Swap 5 with 1: [1, 5, 4, 2, 8]
2. Pass 2:
○ Find minimum in [5, 4, 2, 8]: Minimum is 2
○ Swap 5 with 2: [1, 2, 4, 5, 8]
3. Pass 3:
○ Find minimum in [4, 5, 8]: Minimum is 4
○ No swap needed: [1, 2, 4, 5, 8]
4. Pass 4:
○ Find minimum in [5, 8]: Minimum is 5
○ No swap needed: [1, 2, 4, 5, 8]

Sorted Array: [1, 2, 4, 5, 8]

Pseudocode:
procedure selectionSort(array, size)
for i from 0 to size - 1 do
set minIndex to i
for j from i + 1 to size - 1 do
if array[j] < array[minIndex]
set minIndex to j
if minIndex is not i
swap array[i] with array[minIndex]
end selectionSort
C++ code:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
// Swap without using std::swap
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}

3. Insertion Sort:

Pseudocode:
procedure insertionSort(array, size)
for i from 1 to size - 1 do
set key to array[i]
set j to i - 1
while j >= 0 and array[j] > key do
array[j + 1] to array[j]
set j to j - 1
end while
array[j + 1] to key
end insertionSort
 C++ code:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}

If you are interested. You can read marge and selection sort..!

4. Array: 2D
Sum of Prime Numbers:
bool isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
// Function to calculate the sum of prime numbers in a 2D array
int sumOfPrimes(int arr[][10], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isPrime(arr[i][j])) {
sum += arr[i][j];
}
}
}
return sum;
}

Sum of Diagonal element:

// Function to calculate the sum of the main diagonal elements
int sumOfDiagonal(int arr[][10], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i][i]; // Main diagonal: row index = column index
}
return sum;

}
Sum of Boundary Element:
int boundary(int matrix[100][100], int n) {
int boundary_sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || i == n - 1 || j == 0 || j == n - 1) {
boundary_sum += matrix[i][j];
}
}
return boundary_sum;
}

4. Stack:

A stack is a data structure that follows the Last In First Out (LIFO) principle. Elements can
only be added or removed from the top of the stack.

Operations:

1. Push: Add an element to the top of the stack.

○ Example: Push 10 onto [1, 2, 3], resulting in [1, 2, 3, 10].
2. Pop: Remove and return the top element from the stack.
○ Example: Pop from [1, 2, 3, 10], resulting in the stack [1, 2, 3] and
the popped element 10.
3. Peek: View the top element without removing it.
○ Example: Peek on [1, 2, 3, 10], resulting in 10.

Applications:

1. Function Call Management: Keeps track of function calls and returns.

2. Expression Evaluation: Used in parsing and evaluating expressions.
3. Backtracking Algorithms: Helps in scenarios like maze solving.

template <typename Type>

class Stack{
int MAX_SIZE=1e6;
int last=-1;
Type *arr =new Type[MAX_SIZE];

public:
void push(Type value){
arr[++last]=value;
}
void pop(){
--last;
}
Type top(){
 return arr[last];
}
int size(){
return last+1;
}

bool empty(){
if(last==-1) return true;
return false;
}

Type operator[](int index){

if(index<0 || index>=last){
cout<<"Out of range !";
}
return arr[index];
}
};

5. Queue:

A queue is a data structure that follows the First In First Out (FIFO) principle. Elements
are added at the back (rear) and removed from the front (front) of the queue.

Operations:

1. Enqueue: Adds an element to the back of the queue.

○ Example: Enqueue 10 to [1, 2, 3], resulting in [1, 2, 3, 10].
2. Dequeue: Removes and returns the front element from the queue.
○ Example: Dequeue from [1, 2, 3, 10], resulting in the queue [2, 3, 10] and the
dequeued element 1.

Applications:

● Task Scheduling: Useful in operating systems for managing tasks in the correct
order.
● Breadth-First Search (BFS): Used in graph traversal algorithms.
● Printers and Job Queues: Jobs are processed in the order they are received.

Template-based Queue Example:

Here’s a basic implementation of a queue using templates, similar to your stack

implementation:
template <typename Type>
class Queue {
int MAX_SIZE = 1e6;
int front = 0, rear = -1, size = 0;
Type *arr = new Type[MAX_SIZE];

public:
// Enqueue: Adds element to the rear of the queue
void enqueue(Type value) {
arr[++rear] = value;
size++;
}

// Dequeue: Removes element from the front of the queue

void dequeue() {
front++;
size--;
}

// Front: Returns the front element without removing it

Type frontElement() {
return arr[front];
}

// Size: Returns the number of elements in the queue

int getSize() {
return size;
}

// Empty: Checks if the queue is empty

bool empty() {
return size == 0;
}
};
6. Circular Queue:

Definition:

A Circular Queue is a linear data structure that follows the FIFO (First In, First Out) principle

but uses a circular arrangement of elements. It connects the end of the queue back to the

beginning to make a circular structure, thereby utilizing the entire array space efficiently.

Operations:

1. Enqueue: Add an element to the rear of the queue. If the rear reaches the end of

the array, it wraps around to the beginning if there is space available.

2. Dequeue: Remove an element from the front of the queue. The front pointer moves

to the next position in the circular fashion.

3. Peek: View the front element of the queue without removing it.

4. isEmpty: Check if the queue is empty. This is typically done by checking if the front

and rear pointers are equal.

5. isFull: Check if the queue is full. This can be determined by checking if the next

position of the rear pointer (in circular fashion) is the front pointer.

Linear Queue:

Circular Queue:

Advantages Over Traditional Queue

 1. Efficient Space Utilization:

○ In a traditional queue, when the rear reaches the end of the array, the space

at the front may remain unused even though it could potentially be utilized. A

circular queue overcomes this issue by reusing the empty space.

2. Avoids Wasting Space:

○ Circular queues make better use of the available space by wrapping around

to the beginning of the array. This reduces wasted memory and optimizes

resource use.

3. Simplified Implementation:

○ The circular nature simplifies the implementation of operations such as

enqueue and dequeue by eliminating the need to shift elements.

4. Fixed Size:

○ Like traditional queues, circular queues also have a fixed size. However, their

circular nature helps in making the fixed size more efficient.

7. Linkedlist:
A Linked List is an Abstract Data Type (ADT) that holds a collection of nodes. Each node
contains data and a reference (or pointer) to the next node in the sequence. Linked lists are
used to implement dynamic data structures that can grow or shrink in size.

struct Node {
int data;
Node* next;

Node(int val){
data=val;
next=nullptr;
}
};
void insertHead(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}

void insertTail(int value) {

Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}

void pop() {
if (Head == nullptr) {
cout << "Queue is Emptly !\n";
return;
}
else if (Head->next == nullptr) {
delete Head;
Head = nullptr;
return;
}
else {
Node *temp = Head;
while (temp->next->next != nullptr) {
 temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
}

Advantage and Disadvantage of Linked List Over Array:

Advantages of Linked Lists

1. Dynamic Size:
○ Flexible Growth: Linked lists can grow or shrink in size as needed, without
requiring an initial size. Memory is allocated only when needed.
2. No Memory Wastage:
○ Efficient Use: Memory is used only for the nodes that are needed. There’s no
pre-allocation of memory or wasted space, as with arrays.
3. Easy Implementation:
○ Simple Structures: Data structures like stacks and queues are easier to
implement using linked lists due to their flexible nature.
4. Efficient Insertion and Deletion:
○ Quick Updates: Adding or removing elements is straightforward and quick.
You only need to update pointers, without shifting other elements as you do
in arrays.
5. Flexible Memory Usage:
○ Non-Contiguous: Linked lists do not require elements to be stored in
contiguous memory locations, which can be advantageous for memory
management.
6. Handles Large Data Well:
○ Dynamic Adjustment: Ideal for working with large datasets as they can
dynamically adjust their size and handle large amounts of data efficiently.
7. Scalable:
 ○ Adaptable Size: Easily allows adding or removing elements at any position in
the list without major adjustments.

8. Polish Notation:

Postfix Expression Evaluation Algorithm

Algorithm:

1. Initialize an empty stack.

2. Read the postfix expression from left to right.
3. For each token:
○ If it's an operand, push it onto the stack.
○ If it's an operator, pop two elements from the stack, apply the operator, and
push the result back onto the stack.
4. After processing all tokens, the result will be on the top of the stack.

Evaluate Expression: 5 2 * 3 6 2 ^ / + 5 5 - * -2 -

int evaluatePostfix(string& expression) {

stack<int> st;
stringstream ss(expression);
string token;

while (ss >> token) {

// If the token is a number, push it onto the stack
if (isdigit(token[0]) || (token[0] == '-' && token.size() >
1)) {
st.push(stoi(token));
} else {
// Pop two elements for the operation
int a = st.top(); st.pop();
int b = st.top(); st.pop();

// Apply the operation based on the token

switch (token[0]) {
case '+': st.push(b + a); break;
case '-': st.push(b - a); break;
case '*': st.push(b * a); break;
case '/': st.push(b / a); break;
case '^': st.push(pow(b, a)); break;
default:
cout << "Invalid operator: " << token << endl;
return -1;
 }
}
}

return st.top(); // Return the final result

}

9. Tree:
A tree is a kind of data structure that is used to represent the data in hierarchical form.

Binary Search tree:

● A Binary Search Tree is a Binary Tree where every node's left child has a lower value,
and every node's right child has a higher value.

#include<iostream>
using namespace std;
struct Node{
int data;
Node *left,*right;
Node(int val) {
data=val;
left=right=nullptr;
}
};

Node* insertBst(Node *root,int val) {

if(root==nullptr) {
return new Node(val);
}
if(val<root->data){
root->left=insertBst(root->left,val);
}
 else{
root->right=insertBst(root->right,val);
}
return root;
}

void inorder(Node* root)

{
if(root==nullptr){
return;
}
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
void preorder(Node* root) {
if(root==nullptr){
return;
}
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
void postorder(Node* root) {
if(root==nullptr) {
return;
}
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
int main() {
Node* root=nullptr;
root=insertBst(root,1);
insertBst(root,1);
insertBst(root,3);
insertBst(root,4);
cout<<"IN order:";
inorder(root);
return 0;
}
Delation:

void deletion(Node*& root, int item)

{
Node* parent = NULL;
Node* cur = root;

search(cur, item, parent);

if (cur == NULL)
return;

if (cur->left == NULL && cur->right == NULL) {

if (cur != root)
{
if (parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;

delete cur; // Use delete instead of free

}
else if (cur->left && cur->right) {
Node* succ = findMinimum(cur->right);
int val = succ->data;
deletion(root, succ->data);
cur->data = val;
}
else {
Node* child = (cur->left) ? cur->left : cur->right;

if (cur != root)
{
if (cur == parent->left)
parent->left = child;
else
parent->right = child;
}
else
root = child;

delete cur; // Use delete instead of free

}
}

Node* findMinimum(Node* cur) {

while (cur->left != NULL) {
cur = cur->left;
}
return cur;
}
10. Graph:
Graph Data Structure is a collection of nodes connected by edges. It's used to represent
relationships between different entities.

Construct graph:

Depth First Search (DFS) Algorithm:

Depth First Search (DFS) algorithm is a recursive algorithm for searching all the vertices of
a graph or tree data structure. This algorithm traverses a graph in a depthward motion and
uses a stack to remember to get the next vertex to start a search, when a dead end occurs
in any iteration.

Step for DFS Recursive Implementation:

● Start DFS from a vertex.

● Visit the current vertex, mark it, and explore its unvisited neighbors.
● The process continues recursively for each neighbor, following a depth-first
path.
● DFS goes deep along a path, while BFS explores level by level using a queue.
DFS:

Breadth-First Search (BFS):

Breadth First Search (BFS) is a fundamental graph traversal algorithm. It begins with a
node, then first traverses all its adjacent.

Step for DFS Recursive Implementation:

● Start BFS from a vertex.

● Visit the current vertex and explore all its immediate neighbors.
● Enqueue all unvisited neighbors and repeat the process level by level, moving
outward from the starting point.

BFS:
11. Spanning Tree:

A spanning tree is a subset of Graph G, such that all the vertices are connected using the
minimum possible number of edges.

Properties:

1. Connected: A spanning tree connects all the vertices together.

2. Acyclic: A spanning tree cannot have any cycles (just like any other tree).
3. Number of Edges: A spanning tree for a graph with V vertices always has V−1 edges.
4. Minimum Weight: If the edges have weights, a Minimum Spanning Tree (MST) is a
spanning tree where the sum of the edge weights is minimized.
5. We can construct a spanning tree for a complete graph by removing E-V+1 edges,
where E is the number of Edges and V is the number of vertices.
6. Cayley’s Formula: It states that the number of spanning trees in a complete graph with N
vertices is N^{N-2}. If N=4,maximum number of spanning tree possible=16.

Normal Graph:

Spanning Tree:
Minimum Spanning Tree (MST):
The minimum spanning tree is a spanning tree whose sum of the edges is minimum. Consider
the below graph that contains the edge weight.

Kruskal’s algorithm:

Below are the steps for finding MST using Kruskal’s algorithm:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Prim's Algorithm:

Minimum Spanning Tree (MST) is to build the MST incrementally by starting with a single
vertex and gradually extending the tree by adding the closest neighboring vertex at each step.

Below are the steps for finding MST using Prim’s algorithm:
1. Start by picking any vertex and add it to the MST.
2. Look for the smallest edge that connects a vertex already in the MST to a vertex not yet
in the MST.
3. Add that edge and vertex to the MST.
4. Repeat this process until all vertices are included in the MST.
12. Heap:
A Heap is a complete binary tree data structure that satisfies the heap property: for every node,
the value of its children is greater than or equal to its own value. Heaps are usually used to
implement priority queues, where the smallest (or largest) element is always at the root of the
tree.

Types of Heaps
There are two main types of heaps:
● Max Heap: The root node contains the maximum value, and the values decrease as you
move down the tree.
● Min Heap: The root node contains the minimum value, and the values increase as you
move down the tree.
Max Heapify:

Min Heapify:
13. Hash Table:

A hash table is a way to store and retrieve key-value pairs efficiently. It works as follows:

● Key: The input (like a string or number) used to find where to store or retrieve data.
● Hash Function: Takes the key and calculates an index in the hash table.
● Hash Table: An array where data is stored at the index given by the hash function.

Collisions: When two keys hash to the same index, a collision occurs. Common methods to
handle collisions include:

● Chaining: Each index holds a list of all entries that hash to that index.
● Open Addressing: If a slot is taken, it finds another slot using:
○ Linear Probing: Check the next slot until you find an empty one.
○ Quadratic Probing: Use a pattern to skip over slots.
○ Double Hashing: Use a second hash function to find the next slot.

Hashing:
● Hashing is a technique used in data structures that efficiently stores and retrieves data
in a way that allows for quick access.
Hash collision:
● A hash collision occurs when two different keys produce the same hash address or
index in the hash table. This can happen when a hash function maps multiple keys to the
same location. To handle collisions, several methods can be used. One common method
is linear probing, which means that when a collision occurs, you check the next available
memory slot (i.e., increase the index by 1 until an empty spot is found).

Given: The table has 11 memory locations. Using linear probing, the records will be placed as
follows:
Records and Their Hashing:

● Record A: Hashes to slot 4

● Record B: Hashes to slot 8
● Record C: Hashes to slot 2
● Record D: Hashes to slot 11
● Record E: Hashes to slot 4, but slot 4 is occupied (by A), so it moves to slot 5
● Record F: Hashes to slot 11, but slot 11 is occupied (by D), so it wraps around and
moves to slot 0
● Record G: Hashes to slot 5, but slot 5 is occupied (by E), so it moves to slot 6
● Record H: Hashes to slot 1

Final Memory Positions After Linear Probing:

● Slot 0: F
● Slot 1: H
● Slot 2: C
● Slot 4: A
● Slot 5: E
● Slot 6: G
● Slot 8: B
The End