Department of computer Science & Engineering

KCC INSTITUTE OF TECHNOLOGY & MANAGEMENT

2B-2C, Knowledge Park-III, Greater Noida, Uttar Pradesh

BCS351-DATA STRUCTURE LAB

LAB FILE
(2025-26)
THIRD SEMESTER

SUBMITTED TO:​ SUBMITTED BY:

Satyam Mishra​ Priyanshu Tiwari
(Data Structure Trainer)​ [Link]-CSE(AI) (3rd Sem)
Department of CSE​ Roll No.: 2404921520158
Section: B7
 Index
Page
Sr. No. Name of the experiment Date
No.
1.
Implementing Sorting Techniques

2.
Implementing Searching and Hashing Techniques

3.
Implementing Stacks

4.
Implementing Queue

5.
Implementing Linked List

6.
Implementing Trees

7.
Implementing Graphs
 Experiment No. -1
< Implementing Sorting Techniques >

(i)To implement Bubble Sort to sort a given list of numbers in

ascending order.

Theory:

Bubble sort is a simple comparison–based sorting algorithm. It repeatedly

compares adjacent elements of the array and swaps them if they are in the wrong
order. In each pass, the largest element “bubbles up” to its correct position at the
end of the array. Time complexity in worst and average case is O(n²).

Algorithm:

●​ Start
●​ Read n, the number of elements.
●​ Read n elements into array a[ ].
●​ Repeat steps 5–7 for i = 0 to n-2
●​ Repeat for j = 0 to n-2-i
●​ If `a[j] > a[j+1]` then swap `a[j]` and `a[j+1]`.
●​​
●​ End inner loop
●​ End outer loop
●​ Display the sorted array.
●​ Stop

PROGRAM CODE(C) :

#include <stdio.h>

int main() {

int a[50];

int n, i, j, temp;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter %d elements:\n", n);

for (i = 0; i < n; i++) {

scanf("%d", &a[i]);

}
 for (i = 0; i < n - 1; i++) {

for (j = 0; j < n - 1 - i; j++) {

if (a[j] > a[j + 1]) {

temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

printf("Sorted array (ascending):\n");

for (i = 0; i < n; i++) {

printf("%d ", a[i]);

Return 0;

************************Output*******************************

Result / Conclusion:

Thus the Bubble Sort algorithm was implemented in C language and the given list of numbers was
successfully sorted in ascending order.

Viva-Voce Questions:

1.​ Q: What is the time complexity of bubble sort?

Ans: O(n²) in worst and average case, O(n) in best case (already sorted array).

2.​ Q: Why is it called “Bubble” sort?

Ans: Because in each pass, the largest element moves to the end like a bubble rising to the surface.

3.​ Q: Is bubble sort stable?

Ans: Yes, it is a stable sorting algorithm.
(ii) Insertion Sort:-

Insertion Sort is a simple sorting algorithm that works the way we sort playing cards
in our hands. It builds the final sorted array one item at a time.

●​ It’s efficient for small datasets or when the array is almost sorted.
●​ Time Complexity:
○​ Best case (already sorted): O(n)
○​ Worst case (reverse order): O(n²)
○​ Average case: O(n²)
●​ Space Complexity: O(1) (in-place sorting)

⚙️ Algorithm:-​
1.​ Start from the second element (index 1), because the first element is trivially sorted.
2.​ Compare the current element with the elements before it.
3.​ Shift all larger elements one position ahead to make space.
4.​ Insert the current element into its correct position.
5.​ Repeat until the array is fully sorted.

💻 C Implementation :-
#include <stdio.h>

// Function to perform insertion sort

void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i]; // Current element to be inserted
j = i - 1;

// Shift elements of arr[0..i-1] that are greater than key

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // Insert key at correct position
}
}

// Function to print the array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

insertionSort(arr, n);
 printf("Sorted array: ");
printArray(arr, n);

return 0;
}

Example:-

For array: {12, 11, 13, 5, 6}

●​ Step 1: Compare 11 with 12 → Insert before → {11, 12, 13, 5, 6}

●​ Step 2: 13 is already in correct place → {11, 12, 13, 5, 6}
●​ Step 3: Insert 5 → {5, 11, 12, 13, 6}
●​ Step 4: Insert 6 → {5, 6, 11, 12, 13}
●​ Sorted!

(iii) Selection Sort :-

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly finds

the minimum element from the unsorted part of the array and places it at the beginning.

●​ Works by dividing the array into two parts:

○​ Sorted part (built up from left to right)
○​ Unsorted part (shrinks as sorting progresses)
●​ Time Complexity:
○​ Best case: O(n²)
○​ Worst case: O(n²)
○​ Average case: O(n²)
●​ Space Complexity: O(1) (in-place sorting)

⚙️ Algorithm (Step-by-Step)​
1.​ Start with the first element as the minimum.
2.​ Compare it with the rest of the array to find the smallest element.
3.​ Swap the smallest element with the first element.
4.​ Move to the next position and repeat until the array is sorted.

💻 C Implementation:-
#include <stdio.h>

// Function to perform selection sort

void selectionSort(int arr[], int n) {

int i, j, min_idx, temp;

// Move boundary of unsorted subarray

for (i = 0; i < n-1; i++) {

min_idx = i; // Assume the current index is the minimum

 // Find the minimum element in the unsorted array

for (j = i+1; j < n; j++) {

if (arr[j] < arr[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

// Function to print the array

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

selectionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;

Example:-

For array: {64, 25, 12, 22, 11}

●​ Step 1: Find min (11), swap with 64 → {11, 25, 12, 22, 64}
 ●​ Step 2: Find min (12), swap with 25 → {11, 12, 25, 22, 64}
●​ Step 3: Find min (22), swap with 25 → {11, 12, 22, 25, 64}
●​ Step 4: Find min (25), already in place → {11, 12, 22, 25, 64}

Sorted!

(iv) Shell Sort:-

●​ Shell Sort is an optimization of Insertion Sort. Instead of comparing adjacent

elements one by one, it compares elements that are far apart (using a gap).
●​ The gap is gradually reduced until it becomes 1, at which point the algorithm
behaves like insertion sort.
●​ This reduces the number of shifts required and makes sorting faster for larger
arrays.

Key Idea:​
Start with a large gap, sort elements that are that far apart, then reduce the gap and
repeat until the gap is 1.

⚙️ Algorithm:-
1.​ Choose an initial gap (commonly n/2).
2.​ Perform a gapped insertion sort:
○​ Compare elements that are gap apart.
○​ Swap them if they are out of order.
3.​ Reduce the gap (usually gap = gap/2).
4.​ Repeat until the gap becomes 0.

💻 C Implementation
#include <stdio.h>

// Function to perform Shell Sort

void shellSort(int arr[], int n) {

// Start with a big gap, then reduce the gap

for (int gap = n/2; gap > 0; gap /= 2) {

// Do a gapped insertion sort for this gap size

for (int i = gap; i < n; i++) {

int temp = arr[i];

int j;

// Shift earlier gap-sorted elements up until correct location found

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {

arr[j] = arr[j - gap];

arr[j] = temp;
 }

// Function to print the array

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {12, 34, 54, 2, 3};

int n = sizeof(arr)/sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

shellSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;

Example:-

For array: {12, 34, 54, 2, 3}

●​ Gap = 2 → Compare elements 2 apart → partially sorted.

●​ Gap = 1 → Normal insertion sort → fully sorted.​
Final result: {2, 3, 12, 34, 54}

(v) Radix Sort:-

Radix Sort is a non-comparative sorting algorithm. It sorts numbers digit by digit, starting
from the least significant digit (LSD) to the most significant digit (MSD) (or vice versa).

●​ It uses a stable subroutine like Counting Sort to sort digits at each position.
●​ Works best when the range of digits is small compared to the number of elements.

Key Idea:​
Sort numbers by their digits, one place at a time, until all digits are processed.​
​
​
⚙️ Algorithm:-​
1.​ Find the maximum number to know the number of digits.
2.​ Starting from the least significant digit:
○​ Use Counting Sort to sort numbers based on that digit.
3.​ Move to the next digit and repeat.
4.​ Continue until all digits are sorted.

💻 C Implementation:-
#include <stdio.h>

// Function to get maximum value in arr[]

int getMax(int arr[], int n) {

int max = arr[0];

for (int i = 1; i < n; i++)

if (arr[i] > max)

max = arr[i];

return max;

// A function to do counting sort of arr[] according to the digit represented by exp

void countSort(int arr[], int n, int exp) {

int output[n]; // output array

int count[10] = {0};

// Count occurrences of digits

for (int i = 0; i < n; i++)

count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] contains actual position of this digit in output[]

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

// Build the output array

for (int i = n - 1; i >= 0; i--) {

output[count[(arr[i] / exp) % 10] - 1] = arr[i];

count[(arr[i] / exp) % 10]--;

 }

// Copy the output array to arr[]

for (int i = 0; i < n; i++)

arr[i] = output[i];

// Radix Sort function

void radixSort(int arr[], int n) {

int m = getMax(arr, n);

// Do counting sort for every digit

for (int exp = 1; m / exp > 0; exp *= 10)

countSort(arr, n, exp);

// Function to print array

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

radixSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;

Example:-

Original array: 170 45 75 90 802 24 2 66

Sorted array: 2 24 45 66 75 90 170 802

(vi) Quick Sort:-

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element,
then partitioning the array into:

○​ Elements smaller than pivot

○​ Elements greater than pivot
●​ Recursively apply the same process to subarrays until sorted.
●​ Time Complexity:
○​ Best case: O(n log n)
○​ Average case: O(n log n)
○​ Worst case: O(n²) (when pivot is always the smallest/largest element)
●​ Space Complexity: O(log n) (due to recursion stack)

Algorithm:-
1.​ Choose a pivot (commonly the last element).
2.​ Partition the array so that:
○​ All elements smaller than pivot are on the left.
○​ All elements greater than pivot are on the right.
3.​ Recursively apply Quick Sort to left and right subarrays.
4.​ Continue until subarrays have one element (base case).

💻 C Implementation:-
#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

int partition(int arr[], int low, int high) {

int pivot = arr[high]; // pivot element

int i = (low - 1); // index of smaller element

for (int j = low; j < high; j++) {

// If current element is smaller than or equal to pivot

if (arr[j] <= pivot) {

i++;

swap(&arr[i], &arr[j]);
 }

swap(&arr[i + 1], &arr[high]);

return (i + 1);

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;

Example:-

Original array: 10 7 8 9 1 5

Sorted array: 1 5 7 8 9 10
 EXPERIMENT NO. :- 2
(Implementing Searching and Hashing Technique)

Linear Search:-
●​ Linear Search is the simplest searching algorithm. It checks each element of the
array one by one until the desired element is found or the list ends.
●​ Works on both sorted and unsorted arrays.
●​ Time Complexity:
○​ Best case: O(1) (element found at first position)
○​ Worst case: O(n) (element not found or at last position)
○​ Average case: O(n)
●​ Space Complexity: O(1)

⚙️ Algorithm:-​
1.​ Start from the first element of the array.
2.​ Compare the target element with the current element.
3.​ If they match, return the index (position).
4.​ If not, move to the next element.
5.​ Continue until the element is found or the array ends.
6.​ If not found, return -1 (or indicate "not found").

💻 C Implementation:-
#include <stdio.h>

// Function to perform linear search

int linearSearch(int arr[], int n, int key) {

for (int i = 0; i < n; i++) {

if (arr[i] == key)

return i; // return index if found

return -1; // return -1 if not found

int main() {

int arr[] = {10, 20, 30, 40, 50};

int n = sizeof(arr) / sizeof(arr[0]);

int key = 30;

printf("Array elements: ");

 for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int result = linearSearch(arr, n, key);

if (result != -1)

printf("Element %d found at index %d\n", key, result);

else

printf("Element %d not found in the array\n", key);

return 0;

Example:-

Array elements: 10 20 30 40 50

Element 30 found at index 2

Binary Search:-
Binary Search is a fast searching algorithm used on sorted arrays. It works by repeatedly
dividing the search interval in half:

○​ Compare the target element with the middle element.

○​ If equal → found.
○​ If smaller → search left half.
○​ If larger → search right half.
●​ Time Complexity:
○​ Best case: O(1) (element found at middle)
○​ Worst case: O(log n)
○​ Average case: O(log n)
●​ Space Complexity: O(1) (iterative) or O(log n) (recursive stack)

⚙️ Algorithm:-​
1.​ Start with two pointers: low = 0, high = n-1.
2.​ Find the middle index: mid = (low + high) / 2.
3.​ If arr[mid] == key, return mid.
4.​ If arr[mid] > key, search left half (high = mid - 1).
5.​ If arr[mid] < key, search right half (low = mid + 1).
6.​ Repeat until low > high.
7.​ If not found, return -1.

💻
​
C Implementation (Iterative):-​
#include <stdio.h>

// Function to perform binary search

int binarySearch(int arr[], int n, int key) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == key)

return mid; // element found

else if (arr[mid] < key)

low = mid + 1; // search right half

else

high = mid - 1; // search left half

return -1; // element not found

int main() {

int arr[] = {10, 20, 30, 40, 50};

int n = sizeof(arr) / sizeof(arr[0]);

int key = 40;

printf("Array elements: ");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

int result = binarySearch(arr, n, key);

if (result != -1)

printf("Element %d found at index %d\n", key, result);

else

printf("Element %d not found in the array\n", key);

return 0;}
 Methods for hashing
Modulo division:-

●​ In hashing, we need a hash function to map a key to an index in the hash table. The
modulo division method is one of the simplest and most widely used hash functions.
●​ Formula:
●​ where:
○​ k = key (the value you want to store)
○​ m = size of the hash table
○​ h(k) = index in the hash table
●​ The remainder ensures that the index always lies between 0 and m-1.

⚙️ Algorithm:-​
1.​ Choose a hash table size m (preferably a prime number to reduce collisions). For
each key k:
○​ Compute index = k % m.
○​ Place the key at index in the hash table.
2.​ If multiple keys map to the same index (collision), handle it using techniques like
chaining or linear probing.

💻 C Implementation (Simple Hash Table using Modulo Division):-

​
​

#include <stdio.h>

#define SIZE 10 // size of hash table

// Function to insert a key into hash table

void insert(int hashTable[], int key) {

int index = key % SIZE; // modulo division method

hashTable[index] = key; // store key at computed index

// Function to display hash table

void display(int hashTable[]) {

printf("Hash Table:\n");

for (int i = 0; i < SIZE; i++) {

if (hashTable[i] != -1)

printf("Index %d --> %d\n", i, hashTable[i]);

else

printf("Index %d --> Empty\n", i);

}
}

int main() {

int hashTable[SIZE];

// Initialize hash table with -1 (empty)

for (int i = 0; i < SIZE; i++)

hashTable[i] = -1;

// Keys to insert

int keys[] = {23, 43, 13, 27};

int n = sizeof(keys) / sizeof(keys[0]);

printf("Inserting keys using modulo division method...\n");

for (int i = 0; i < n; i++) {

insert(hashTable, keys[i]);

// Display hash table

display(hashTable);

return 0;

Fold Shift and Fold Boundary:-

The folding method divides a large key into smaller segments (usually equal-sized). These
segments are then combined (added or manipulated) to produce the hash value.

●​ Formula (general):

where a,b,c are segments of the key, and m is the table size.

Fold shift:- (also called folding–shifting) is a hashing method where:

1.​ The key (usually a long number) is split into equal-sized parts.​

2.​ All parts are added together.​

3.​ The resulting sum is then reduced using the hash table size:​
h(key)=(part1+part2+⋯+partn)mod tableSizeh(key) = (part_1 + part_2 + \dots +
part_n) \mod tableSizeh(key)=(part1​+part2​+⋯+partn​)modtableSize

Example:-
Key = 1234567, table size = 100

Split into 3-digit groups:

 ●​ 1 | 234 | 567​

Add:​
1 + 234 + 567 = 802

Hash:​
802 mod 100 = 2

Fold Boundary:-
Fold boundary (also called folding–boundary reversal) is similar, but:

●​ Every alternate part is reversed before adding.​

Example
Key = 1234567, split length = 3:

Parts: 1 | 234 | 567​

Reverse every second part:

●​ 1​

●​ 432 (reverse of 234)​

●​ 567​

Sum:​
1 + 432 + 567 = 1000

Hash:​
1000 mod 100 = 0

Algorithm:-

Fold Shift:-

Input: key, tableSize

1. Convert key to string
2. Split into equal parts of length L
3. Convert each part to integer
4. sum = sum of all parts
5. Return sum % tableSize

Fold Boundary:-

Input: key, tableSize

1. Convert key to string
2. Split into equal parts of length L
3. For every second part (i.e., part 2, 4, 6...), reverse digits
4. Convert each part to integer
5. sum = sum of all parts
6. Return sum % tableSize

C implementation for both methods:-

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int foldShiftHash(char key[], int partSize, int tableSize) {

int len = strlen(key);
int sum = 0;

for (int i = 0; i < len; i += partSize) {

char part[20] = {0};
strncpy(part, key + i, partSize);
sum += atoi(part);
}
return sum % tableSize;
}

int foldBoundaryHash(char key[], int partSize, int tableSize) {

int len = strlen(key);
int sum = 0;
int partIndex = 0;

for (int i = 0; i < len; i += partSize) {

char part[20] = {0};
strncpy(part, key + i, partSize);

// Reverse every second part

if (partIndex % 2 == 1) {
int l = 0, r = strlen(part) - 1;
while (l < r) {
char temp = part[l];
part[l] = part[r];
part[r] = temp;
l++;
r--;
}
}
sum += atoi(part);
partIndex++;
}
return sum % tableSize;
}

int main() {
char key[50];
int partSize, tableSize;
 printf("Enter numeric key: ");
scanf("%s", key);

printf("Enter part size (e.g., 2 or 3): ");

scanf("%d", &partSize);

printf("Enter hash table size: ");

scanf("%d", &tableSize);

int hashShift = foldShiftHash(key, partSize, tableSize);

int hashBoundary = foldBoundaryHash(key, partSize, tableSize);

printf("\nFold Shift Hash Value: %d\n", hashShift);

printf("Fold Boundary Hash Value: %d\n", hashBoundary);

return 0;
}

OUTPUT:-

Input:

Enter numeric key: 1234567

Enter part size: 3
Enter hash table size: 100

Output:-

Fold Shift Hash Value: 2

Fold Boundary Hash Value: 0

Direct and Subtraction Hashing:-

Direct Hashing:-

Definition
Direct hashing uses the key exactly as it is (or a simple function of it) as the hash address.

h(key)=keyh(key) = keyh(key)=key

or

h(key)=a×key+bh(key) = a \times key + bh(key)=a×key+b

When Used

●​ When the key range is small (e.g., 0–999)​

●​ When memory is not a limitation​

●​ Guarantees no collisions​

Example
Key = 45​
Table size = 100

h(45)=45h(45) = 45h(45)=45

Subtraction Hashing:

Definition

Subtraction hashing subtracts the key from a fixed number, then takes modulus of the
table size:

h(key)=(N−key)mod tableSizeh(key) = (N - key) \mod

tableSizeh(key)=(N−key)modtableSize

Where N is a fixed constant (usually power of 2 or the max key value).

✔ Example

Key = 45, table size = 100, N = 1000

h(45)=(1000−45)%100=955%100=55h(45) = (1000 - 45) \% 100 = 955 \% 100 =

55h(45)=(1000−45)%100=955%100=55

Algorithm:-

Direct Hashing:-

Input: key, tableSize

1. If key < tableSize
2. return key
3. Else return key % tableSize

Subtraction Hashing:-

Input: key, tableSize, N

1. Compute value = N - key
2. Hash = value % tableSize
3. Return hash
C Program Implementing Both Methods:-

#include <stdio.h>

int directHash(int key, int tableSize) {

// If key is out of range, use key % table size
if (key < tableSize)
return key;
else
return key % tableSize;
}

int subtractionHash(int key, int tableSize, int N) {

int value = N - key;
return value % tableSize;
}

int main() {
int key, tableSize, N;

printf("Enter the key: ");

scanf("%d", &key);

printf("Enter hash table size: ");

scanf("%d", &tableSize);

printf("Enter constant N (larger than key): ");

scanf("%d", &N);

int h1 = directHash(key, tableSize);

int h2 = subtractionHash(key, tableSize, N);

printf("\nDirect Hash Value: %d\n", h1);

printf("Subtraction Hash Value: %d\n", h2);

return 0;
}

OUTPUT:-

Input:-

Enter the key: 45

Enter hash table size: 100
Enter constant N: 1000

Output:-

Direct Hash Value: 45

Subtraction Hash Value: 55
Linear Probe for Collision Resolution:-

When using hashing, collisions occur if two keys hash to the same index.​
Linear Probing is a simple collision resolution technique where:

●​ If the desired slot is occupied, you check the next slot sequentially (index + 1, index
+ 2, …).
●​ Wrapping around happens when the end of the table is reached (modulo operation).
●​ This continues until an empty slot is found.

👉 Example:​
Hash function: h(key) = key % table_size​
If h(23) = 3 but slot 3 is full, try slot 4, then 5, etc.

📑 Algorithm (Linear Probing):-

Algorithm InsertLinearProbe(hashTable, key):

1. Compute index = key % table_size

2. If hashTable[index] is empty:

Place key at hashTable[index]

Else:

i=1

While hashTable[(index + i) % table_size] is not empty:

i=i+1

Place key at hashTable[(index + i) % table_size]

Algorithm SearchLinearProbe(hashTable, key):

1. Compute index = key % table_size

2. If hashTable[index] == key:

Return index

Else:

i=1

While hashTable[(index + i) % table_size] != key:

If slot is empty → Key not found

 Else i = i + 1

Return (index + i) % table_size

💻 C Implementation:-
#include <stdio.h>

#define TABLE_SIZE 10

int hashTable[TABLE_SIZE];

// Initialize table with -1 (empty)

void initTable() {

for (int i = 0; i < TABLE_SIZE; i++)

hashTable[i] = -1;

// Hash function

int hashFunc(int key) {

return key % TABLE_SIZE;

// Insert using Linear Probing

void insert(int key) {

int index = hashFunc(key);

if (hashTable[index] == -1) {

hashTable[index] = key;

} else {

int i = 1;

while (hashTable[(index + i) % TABLE_SIZE] != -1) {

i++;

hashTable[(index + i) % TABLE_SIZE] = key;

}
}

// Search using Linear Probing

int search(int key) {

int index = hashFunc(key);

if (hashTable[index] == key) return index;

int i = 1;

while (hashTable[(index + i) % TABLE_SIZE] != -1) {

if (hashTable[(index + i) % TABLE_SIZE] == key)

return (index + i) % TABLE_SIZE;

i++;

return -1; // Not found

// Display table

void display() {

printf("\nHash Table:\n");

for (int i = 0; i < TABLE_SIZE; i++) {

printf("%d --> %d\n", i, hashTable[i]);

int main() {

initTable();

insert(23);

insert(43);

insert(13);

insert(27);

display();

int key = 43;

int pos = search(key);

 if (pos != -1)

printf("\nKey %d found at index %d\n", key, pos);

else

printf("\nKey %d not found\n", key);

return 0;

🖥️ Sample Output (Dry Run):-

Hash Table:

0 --> -1

1 --> -1

2 --> -1

3 --> 23

4 --> 43

5 --> 13

6 --> -1

7 --> 27

8 --> -1

9 --> -1

Key 43 found at index 4

🔍 Explanation of Dry Run

●​ 23 % 10 = 3 → goes to index 3
●​ 43 % 10 = 3 → collision at 3 → next free slot is 4
●​ 13 % 10 = 3 → collision at 3 → next free slot is 5
●​ 27 % 10 = 7 → goes to index 7
 EXPERIMENT NO. :-3

Implementing Stacks

Array Implementation:-

An array is a data structure that stores elements of the same type in contiguous
memory locations.

●​ Each element can be accessed directly using its index.

●​ Arrays are widely used to implement other data structures (like stacks, queues, hash
tables).
●​ Operations include insertion, deletion, traversal, searching.

👉 Example:​
If we declare int arr[5] = {10, 20, 30, 40, 50};

●​ arr[0] = 10, arr[1] = 20, etc.

●​ Memory is allocated sequentially.

📑 Algorithm (Basic Array Operations):-

Traversal:-

Algorithm TraverseArray(arr, n):

1. For i = 0 to n-1:
Print arr[i]

Insertion:-

Algorithm InsertArray(arr, n, pos, value):

1. For i = n down to pos+1:
arr[i] = arr[i-1] // shift right
2. arr[pos] = value
3. n = n + 1

Deletion:-

Algorithm DeleteArray(arr, n, pos):

1. For i = pos to n-2:
arr[i] = arr[i+1] // shift left
2. n = n - 1

💻 C Implementation:-
#include <stdio.h>
#define SIZE 10

// Traversal

void traverse(int arr[], int n) {

printf("Array elements: ");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

// Insertion

int insert(int arr[], int n, int pos, int value) {

if (n >= SIZE) {

printf("Array is full!\n");

return n;

for (int i = n; i > pos; i--) {

arr[i] = arr[i-1];

arr[pos] = value;

return n + 1;

// Deletion

int delete(int arr[], int n, int pos) {

if (n <= 0) {

printf("Array is empty!\n");

return n;

for (int i = pos; i < n-1; i++) {

arr[i] = arr[i+1];

return n - 1;
}

int main() {

int arr[SIZE] = {10, 20, 30, 40, 50};

int n = 5;

printf("Initial ");

traverse(arr, n);

// Insert 25 at position 2

n = insert(arr, n, 2, 25);

printf("After Insertion (25 at pos 2): ");

traverse(arr, n);

// Delete element at position 4

n = delete(arr, n, 4);

printf("After Deletion (pos 4): ");

traverse(arr, n);

return 0;

🖥️ Sample Output (Dry Run):-

Initial Array elements: 10 20 30 40 50

After Insertion (25 at pos 2): 10 20 25 30 40 50

After Deletion (pos 4): 10 20 25 30 50

🔍 Explanation of Dry Run

●​ Start: [10, 20, 30, 40, 50]
●​ Insert 25 at position 2: shift right → [10, 20, 25, 30, 40, 50]
●​ Delete element at position 4 (value 40): shift left → [10, 20, 25, 30, 50]
Linked List implementation:-

A linked list is a dynamic data structure where elements (called nodes) are connected using
pointers.​
Each node contains:

●​ Data (the value you want to store)

●​ Pointer (address of the next node)

Unlike arrays:

●​ Memory is not contiguous.

●​ Size can grow/shrink dynamically.
●​ Insertion/deletion is easier (no shifting needed).

👉We’llTypes: Singly Linked List, Doubly Linked List, Circular Linked List.​
start with Singly Linked List.

📑 Algorithm (Singly Linked List Basic Operations):-

Create Node:

Algorithm CreateNode(value):

1. Allocate memory for new node

2. Set node->data = value

3. Set node->next = NULL

4. Return node

Insert at End:

Algorithm InsertEnd(head, value):

1. Create new node with value

2. If head == NULL:

head = new node

Else:

Traverse till last node

last->next = new node

Delete Node:

Algorithm DeleteNode(head, value):

1. If head == NULL → return

2. If head->data == value:

head = head->next

free old head

3. Else:

Traverse until node->next->data == value

temp = node->next

node->next = temp->next

free temp

Traverse(Display):

Algorithm Traverse(head):

1. Set temp = head

2. While temp != NULL:

Print temp->data

temp = temp->next

💻 C Implementation:-
#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {
 int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->next = NULL;

return newNode;

// Insert at end

void insertEnd(struct Node** head, int value) {

struct Node* newNode = createNode(value);

if (*head == NULL) {

*head = newNode;

return;

struct Node* temp = *head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

// Delete a node by value

void deleteNode(struct Node** head, int value) {

if (*head == NULL) return;

 struct Node* temp = *head;

// If head node itself holds the value

if (temp->data == value) {

*head = temp->next;

free(temp);

return;

// Search for the node to delete

struct Node* prev = NULL;

while (temp != NULL && temp->data != value) {

prev = temp;

temp = temp->next;

if (temp == NULL) return; // Value not found

prev->next = temp->next;

free(temp);

// Display linked list

void display(struct Node* head) {

struct Node* temp = head;

printf("Linked List: ");

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next;

}
 printf("NULL\n");

int main() {

struct Node* head = NULL;

insertEnd(&head, 10);

insertEnd(&head, 20);

insertEnd(&head, 30);

insertEnd(&head, 40);

display(head);

deleteNode(&head, 20);

printf("After deleting 20:\n");

display(head);

return 0;

🖥️ Sample Output (Dry Run):-

Linked List: 10 -> 20 -> 30 -> 40 -> NULL

After deleting 20:

Linked List: 10 -> 30 -> 40 -> NULL

🔍 Explanation of Dry Run:

 ●​ Inserted nodes: 10 → 20 → 30 → 40 → NULL
●​ Deleted node with value 20: list becomes 10 → 30 → 40 → NULL

Evaluation of postfix expression and balancing of

parenthesis:-

Evaluation of Postfix Expression:-

●​ Postfix (Reverse Polish Notation): Operators come after operands.​

Example: 23*54*+9- means (2*3) + (5*4) - 9.
●​ Why stack?
●​ Operands are pushed onto the stack.
●​ When an operator is encountered, pop required operands, apply
operation, push result back.
●​ Continue until expression ends.

📑 Algorithm (Postfix Evaluation):-

Algorithm EvaluatePostfix(expr):

1. Initialize empty stack

2. For each symbol in expr:

a. If symbol is operand → push onto stack

b. If symbol is operator:

i. Pop two operands (op2, op1)

ii. result = op1 operator op2

iii. Push result back

3. Final result = pop from stack

C Implementation (Postfix Evaluation):-

#include <stdio.h>

#include <ctype.h> // for isdigit

#include <stdlib.h> // for atoi

#define MAX 100

int stack[MAX];

int top = -1;

void push(int x) {

stack[++top] = x;

int pop() {

return stack[top--];

int evaluatePostfix(char* expr) {

for (int i = 0; expr[i] != '\0'; i++) {

char ch = expr[i];

if (isdigit(ch)) {

push(ch - '0'); // convert char to int

} else {

int val2 = pop();

int val1 = pop();

switch (ch) {

case '+': push(val1 + val2); break;

case '-': push(val1 - val2); break;

case '*': push(val1 * val2); break;

case '/': push(val1 / val2); break;

 }

return pop();

int main() {

char expr[] = "23*54*+9-"; // (2*3)+(5*4)-9

printf("Postfix Expression: %s\n", expr);

printf("Evaluated Result: %d\n", evaluatePostfix(expr));

return 0;

🖥️ Sample Output (Postfix Evaluation):

Postfix Expression: 23*54*+9-

Evaluated Result: 17

Balancing of Parentheses:-
●​ Problem: Check if every opening bracket has a matching closing bracket
in correct order.
●​ Why stack?
●​ Push opening brackets (, {, [ onto stack.
●​ On encountering closing bracket, check top of stack.
●​ If mismatch → unbalanced.
●​ If stack empty at end → balanced.

📑 Algorithm (Balancing Parentheses):-

Algorithm CheckBalanced(expr):

1. Initialize empty stack

2. For each char in expr:

a. If opening bracket → push

b. If closing bracket:

i. If stack empty → Not balanced

ii. Pop top and check if matches

3. If stack empty at end → Balanced

Else → Not balanced

💻 C Implementation (Balancing Parentheses):-

#include <stdio.h>

#include <stdbool.h>

#define MAX 100

char stack2[MAX];

int top2 = -1;

void push2(char c) {

stack2[++top2] = c;

char pop2() {

return stack2[top2--];

bool isMatchingPair(char open, char close) {

return (open == '(' && close == ')') ||

 (open == '{' && close == '}') ||

(open == '[' && close == ']');

bool checkBalanced(char* expr) {

for (int i = 0; expr[i] != '\0'; i++) {

char ch = expr[i];

if (ch == '(' || ch == '{' || ch == '[') {

push2(ch);

} else if (ch == ')' || ch == '}' || ch == ']') {

if (top2 == -1) return false;

char open = pop2();

if (!isMatchingPair(open, ch)) return false;

return (top2 == -1);

int main() {

char expr1[] = "{[()]}";

char expr2[] = "{[(])}";

printf("Expression: %s --> %s\n", expr1, checkBalanced(expr1) ?

"Balanced" : "Not Balanced");

printf("Expression: %s --> %s\n", expr2, checkBalanced(expr2) ?

"Balanced" : "Not Balanced");

return 0;

}
🖥️ Sample Output (Balancing Parentheses):
Expression: {[()]} -->

Balanced Expression: {[(])} --> Not Balanced

Wrap-Up:

●​ Postfix Evaluation: Uses stack to compute expressions without

parentheses.
●​ Balancing Parentheses: Uses stack to validate correct nesting of
brackets.

Both are classic stack applications and essential for compiler design,
parsing, and expression evaluation.

Conversion of infix to postfix notation:-

●​ Infix: Operators are written between operands. Example: A + B * C Postfix

(Reverse Polish Notation): Operators are written after operands. Example: A B C *
+
●​ Why stack?
●​ Operands are directly added to the output.
●​ Operators are pushed onto a stack, respecting precedence and associativity.
●​ Parentheses control grouping.

📑 Algorithm (Shunting Yard Method):-

Algorithm CheckBalanced(expr):

1. Initialize empty stack

2. For each char in expr:

a. If opening bracket → push

b. If closing bracket:

i. If stack empty → Not balanced

ii. Pop top and check if matches

3. If stack empty at end → Balanced

Else → Not balanced

💻 C Implementation:-
#include <stdio.h>

#include <stdbool.h>

#define MAX 100

char stack2[MAX];

int top2 = -1;

void push2(char c) {

stack2[++top2] = c;

char pop2() {

return stack2[top2--];

bool isMatchingPair(char open, char close) {

return (open == '(' && close == ')') ||

(open == '{' && close == '}') ||

(open == '[' && close == ']');

bool checkBalanced(char* expr) {

for (int i = 0; expr[i] != '\0'; i++) {

char ch = expr[i];

if (ch == '(' || ch == '{' || ch == '[') {

push2(ch);

} else if (ch == ')' || ch == '}' || ch == ']') {

if (top2 == -1) return false;

char open = pop2();

if (!isMatchingPair(open, ch)) return false;

return (top2 == -1);

}

int main() {

char expr1[] = "{[()]}";

char expr2[] = "{[(])}";

printf("Expression: %s --> %s\n", expr1, checkBalanced(expr1) ? "Balanced" : "Not

Balanced");

printf("Expression: %s --> %s\n", expr2, checkBalanced(expr2) ? "Balanced" : "Not

Balanced");

return 0;

🖥️ Sample Output (Dry Run):

Infix Expression: A+B*C

Postfix Expression: ABC*+

🔍 Explanation of Dry Run:

●​ Input: A + B * C
●​ Precedence: * > +
●​ Steps:
○​ Read A → output A
○​ Read + → push +
○​ Read B → output B
○​ Read * → higher precedence than + → push *
○​ Read C → output C
○​ End → pop * then +
●​ Result: A B C * +
​
​

​
​

​
​
​
​
​