Program – 1

Aim :- Write a program to implement a linked list with their operation.

Code :-
#include <iostream>
using namespace std;

// Node structure
struct Node {
int data;
Node* next;
};

// Class to manage linked list operations

class LinkedList {
public:
Node* head;

LinkedList() {
head = nullptr;
}

// Insert a new node at the end of the list

void insertAtEnd(int data) {
Node* newNode = new Node();
newNode->data = data;
 newNode->next = nullptr;

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

// Insert a new node at the beginning of the list

void insertAtBeginning(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = head;
head = newNode;
}

// Delete a node by its value

void deleteNode(int key) {
Node* temp = head;
Node* prev = nullptr;
 // If head node itself holds the key
if (temp != nullptr && temp->data == key) {
head = temp->next;
delete temp;
return;
}

// Search for the key and keep track of the previous node
while (temp != nullptr && temp->data != key) {
prev = temp;
temp = temp->next;
}

// If the key was not present in the list

if (temp == nullptr) {
cout << "Element not found in the list" << endl;
return;
}

// Unlink the node and delete it

prev->next = temp->next;
delete temp;
}

// Search for a node by its value

bool search(int key) {
 Node* temp = head;
while (temp != nullptr) {
if (temp->data == key) {
return true;
}
temp = temp->next;
}
return false;
}

// Display the linked list

void display() {
Node* temp = head;
if (temp == nullptr) {
cout << "List is empty" << endl;
return;
}
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
};

int main() {
LinkedList list;
int choice, value;

do {
cout << "\nLinked List Operations:\n";
cout << "1. Insert at the end\n";
cout << "2. Insert at the beginning\n";
cout << "3. Delete a node\n";
cout << "4. Search for a node\n";
cout << "5. Display the list\n";
cout << "6. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter the value to insert: ";
cin >> value;
list.insertAtEnd(value);
break;
case 2:
cout << "Enter the value to insert: ";
cin >> value;
list.insertAtBeginning(value);
break;
case 3:
 cout << "Enter the value to delete: ";
cin >> value;
list.deleteNode(value);
break;
case 4:
cout << "Enter the value to search: ";
cin >> value;
if (list.search(value)) {
cout << "Element found in the list" << endl;
} else {
cout << "Element not found in the list" << endl;
}
break;
case 5:
list.display();
break;
case 6:
cout << "Exiting..." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
}
} while (choice != 6);

return 0;
}
Output :-
 Program – 2

Aim :- Write a program to implement stack with their operation.

Code :-
#include <iostream>
using namespace std;

#define MAX 100 // Maximum size of the stack

class Stack {
int top;

public:
int arr[MAX]; // Stack array

Stack() { top = -1; } // Constructor to initialize top

// Function to check if the stack is empty

bool isEmpty() {
return (top < 0);
}

// Function to check if the stack is full

bool isFull() {
return (top >= MAX - 1);
}
// Function to push an element onto the stack
void push(int value) {
if (isFull()) {
cout << "Stack overflow! Cannot push " << value << endl;
} else {
arr[++top] = value;
cout << value << " pushed onto the stack." << endl;
}
}

// Function to pop an element from the stack

void pop() {
if (isEmpty()) {
cout << "Stack underflow! Cannot pop an element." << endl;
} else {
cout << arr[top--] << " popped from the stack." << endl;
}
}

// Function to peek the top element of the stack

int peek() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
return -1;
} else {
 return arr[top];
}
}

// Function to display the stack elements

void display() {
if (isEmpty()) {
cout << "Stack is empty!" << endl;
} else {
cout << "Stack elements are: ";
for (int i = top; i >= 0; i--) {
cout << arr[i] << " ";
}
cout << endl;
}
}
};

int main() {
Stack stack;
int choice, value;

do {
cout << "\nStack Operations:\n";
cout << "1. Push\n";
cout << "2. Pop\n";
cout << "3. Peek\n";
cout << "4. Display\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter the value to push: ";
cin >> value;
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
value = stack.peek();
if (value != -1) {
cout << "Top element is: " << value << endl;
}
break;
case 4:
stack.display();
break;
case 5:
cout << "Exiting..." << endl;
 break;
default:
cout << "Invalid choice! Please try again." << endl;
}
} while (choice != 5);

return 0;
}
Output :-
 Program – 3

Aim :- Write a program to implement queue with their operation.

Code :-
#include <iostream>
using namespace std;

#define MAX 100 // Maximum size of the queue

class Queue {
int front, rear;
int arr[MAX];

public:
Queue() {
front = -1;
rear = -1;
}

// Function to check if the queue is empty

bool isEmpty() {
return (front == -1 || front > rear);
}

// Function to check if the queue is full

bool isFull() {
 return (rear == MAX - 1);
}

// Function to add an element to the queue (enqueue)

void enqueue(int value) {
if (isFull()) {
cout << "Queue overflow! Cannot enqueue " << value << endl;
} else {
if (front == -1) {
front = 0; // Set front to 0 when the first element is inserted
}
arr[++rear] = value;
cout << value << " enqueued to the queue." << endl;
}
}

// Function to remove an element from the queue (dequeue)

void dequeue() {
if (isEmpty()) {
cout << "Queue underflow! Cannot dequeue an element." << endl;
} else {
cout << arr[front] << " dequeued from the queue." << endl;
front++;
// Reset front and rear if the queue becomes empty
if (front > rear) {
front = -1;
 rear = -1;
}
}
}

// Function to peek the front element of the queue

int peek() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
} else {
return arr[front];
}
}

// Function to display the queue elements

void display() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
} else {
cout << "Queue elements are: ";
for (int i = front; i <= rear; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
 }
};

int main() {
Queue queue;
int choice, value;

do {
cout << "\nQueue Operations:\n";
cout << "1. Enqueue\n";
cout << "2. Dequeue\n";
cout << "3. Peek\n";
cout << "4. Display\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter the value to enqueue: ";
cin >> value;
queue.enqueue(value);
break;
case 2:
queue.dequeue();
break;
 case 3:
value = queue.peek();
if (value != -1) {
cout << "Front element is: " << value << endl;
}
break;
case 4:
queue.display();
break;
case 5:
cout << "Exiting..." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
}
} while (choice != 5);

return 0;
}
Output :-
 Program – 4

Aim :- write a program to implement binary search tree with their operation.
Code :-
#include <iostream>
using namespace std;

// Node structure for Binary Search Tree

struct Node {
int data;
Node* left;
Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

// Class for Binary Search Tree

class BST {
private:
Node* root;

// Helper function for insertion

Node* insert(Node* node, int data) {
if (!node) {
return new Node(data);
}
 if (data < node->data) {
node->left = insert(node->left, data);
} else {
node->right = insert(node->right, data);
}
return node;
}

// Helper function for searching

Node* search(Node* node, int data) {
if (!node || node->data == data) {
return node;
}
if (data < node->data) {
return search(node->left, data);
} else {
return search(node->right, data);
}
}

// Helper function for finding the minimum node

Node* findMin(Node* node) {
while (node && node->left) {
node = node->left;
}
return node;
}

// Helper function for deletion

Node* deleteNode(Node* node, int data) {
if (!node) return node;

if (data < node->data) {

node->left = deleteNode(node->left, data);
} else if (data > node->data) {
node->right = deleteNode(node->right, data);
} else {
// Node with one or no child
if (!node->left) {
Node* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
Node* temp = node->left;
delete node;
return temp;
}

// Node with two children

Node* temp = findMin(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
 }
return node;
}

// Helper function for in-order traversal

void inorder(Node* node) {
if (!node) return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}

// Helper function for pre-order traversal

void preorder(Node* node) {
if (!node) return;
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}

// Helper function for post-order traversal

void postorder(Node* node) {
if (!node) return;
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
 }

public:
BST() : root(nullptr) {}

// Public functions to call private helper functions

void insert(int data) {
root = insert(root, data);
}

void deleteNode(int data) {

root = deleteNode(root, data);
}

bool search(int data) {

return search(root, data) != nullptr;
}

void inorder() {
inorder(root);
cout << endl;
}

void preorder() {
preorder(root);
cout << endl;
 }

void postorder() {
postorder(root);
cout << endl;
}
};

int main() {
BST bst;

// Inserting values into BST

bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);

cout << "In-order traversal: ";

bst.inorder(); // Output: 20 30 40 50 60 70 80

cout << "Pre-order traversal: ";

bst.preorder(); // Output: 50 30 20 40 70 60 80
 cout << "Post-order traversal: ";
bst.postorder(); // Output: 20 40 30 60 80 70 50

// Searching for a value

int searchValue = 60;
if (bst.search(searchValue)) {
cout << "Value " << searchValue << " found in the tree.\n";
} else {
cout << "Value " << searchValue << " not found in the tree.\n";
}

// Deleting a value
cout << "Deleting 70...\n";
bst.deleteNode(70);

cout << "In-order traversal after deletion: ";

bst.inorder(); // Output: 20 30 40 50 60 80

return 0;
}
Output :-
 Program – 5

Aim :- Write a program to implement bubble sort.

Code :-
#include <iostream>
using namespace std;

// Function to perform Bubble Sort

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // To optimize and check if any swapping happened

// Last i elements are already sorted, so we don't need to check them

for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

swapped = true; // Set flag to true if swapping happens

}
}

// If no two elements were swapped in the inner loop, array is sorted

if (!swapped) {
 break;
}
}
}

// Function to print the array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int n;

// Get the size of the array from the user

cout << "Enter the number of elements in the array: ";
cin >> n;

int arr[n];

// Get the elements of the array

cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
 }

// Sort the array using Bubble Sort

bubbleSort(arr, n);

// Print the sorted array

cout << "Sorted array: ";
printArray(arr, n);

return 0;
}
Output :-
 Program – 6

Aim :- Write a program to implement insertion sort.

Code :-
#include <iostream>
using namespace std;

// Function to perform Insertion Sort

void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // Store the current element
int j = i - 1;

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

// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}

// Place the key in its correct position

arr[j + 1] = key;
}
}

// Function to print the array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int n;

// Get the size of the array from the user

cout << "Enter the number of elements in the array: ";
cin >> n;

int arr[n];

// Get the elements of the array

cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// Sort the array using Insertion Sort

insertionSort(arr, n);

// Print the sorted array

 cout << "Sorted array: ";
printArray(arr, n);

return 0;
}
Output :-
 Program – 7

Aim :- Write a program to implement linear search.

Code :-
#include <iostream>
using namespace std;

// 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 the index if the key is found
}
}
return -1; // Return -1 if the key is not found
}

int main() {
int n, key;

// Get the size of the array from the user

cout << "Enter the number of elements in the array: ";
cin >> n;

int arr[n];
 // Get the elements of the array
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// Get the key to search for

cout << "Enter the element to search: ";
cin >> key;

// Call the linear search function

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

// Output the result

if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found in the array" << endl;
}

return 0;
}
Output :-
 Program – 8

Aim :- Write a program to implement binary search.

Code :-
#include <iostream>
using namespace std;

// Function to perform binary search

int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;

// Check if the key is present at mid

if (arr[mid] == key) {
return mid;
}

// If key is greater, ignore the left half

if (arr[mid] < key) {
left = mid + 1;
}
// If key is smaller, ignore the right half
else {
right = mid - 1;
}
}
 return -1; // Return -1 if the key is not found
}

int main() {
int n, key;

// Get the size of the array from the user

cout << "Enter the number of elements in the array: ";
cin >> n;

int arr[n];

// Get the elements of the array (array should be sorted)

cout << "Enter the elements of the array in sorted order: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}

// Get the key to search for

cout << "Enter the element to search: ";
cin >> key;

// Call the binary search function

int result = binarySearch(arr, 0, n - 1, key);
 // Output the result
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found in the array" << endl;
}

return 0;
}
Output :-
 Program – 9

Aim :- Write a program to implement an adjacency list representation of a

graph.
Code :-
#include <iostream>
#include <vector>
using namespace std;

// Graph class representing the adjacency list

class Graph {
int vertices; // Number of vertices
vector<vector<int>> adjList; // Adjacency list

public:
// Constructor
Graph(int V) {
vertices = V;
adjList.resize(V);
}

// Add an edge to the graph (undirected graph)

void addEdge(int src, int dest) {
adjList[src].push_back(dest); // Add destination to source's list
adjList[dest].push_back(src); // Add source to destination's list
}
 // Print the adjacency list representation of the graph
void printGraph() {
for (int i = 0; i < vertices; i++) {
cout << "Vertex " << i << ":";
for (int neighbor : adjList[i]) {
cout << " -> " << neighbor;
}
cout << endl;
}
}
};

// Main function
int main() {
int V = 5; // Number of vertices
Graph graph(V);

// Adding edges
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
 // Print the graph
graph.printGraph();

return 0;
}
Output :-
 Program – 10

Aim :- Write a program to implement graph traversing using BFS and DFS.
Code :-
#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

// Graph class
class Graph {
int vertices; // Number of vertices
vector<vector<int>> adjList; // Adjacency list

public:
// Constructor
Graph(int v) {
vertices = v;
adjList.resize(v);
}

// Function to add an edge to the graph

void addEdge(int u, int v) {
adjList[u].push_back(v);
 adjList[v].push_back(u); // For an undirected graph
}

// Function for BFS traversal

void BFS(int start) {
vector<bool> visited(vertices, false);
queue<int> q;
q.push(start);
visited[start] = true;

cout << "BFS Traversal: ";

while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";

// Visit all adjacent nodes

for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
// Function for DFS traversal (recursive)
void DFS(int start) {
vector<bool> visited(vertices, false);
cout << "DFS Traversal (Recursive): ";
DFSUtil(start, visited);
cout << endl;
}

// Utility function for DFS

void DFSUtil(int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";

// Visit all adjacent nodes

for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}

// Function for DFS traversal (iterative)

void DFSIterative(int start) {
vector<bool> visited(vertices, false);
stack<int> s;
 s.push(start);

cout << "DFS Traversal (Iterative): ";

while (!s.empty()) {
int node = s.top();
s.pop();

if (!visited[node]) {
cout << node << " ";
visited[node] = true;
}

// Visit all adjacent nodes

for (auto it = adjList[node].rbegin(); it != adjList[node].rend(); ++it) {
if (!visited[*it]) {
s.push(*it);
}
}
}
cout << endl;
}
};

// Main function
int main() {
Graph g(6); // Create a graph with 6 vertices
 // Adding edges
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);

// Display BFS and DFS traversals

cout << "Starting BFS from vertex 0:\n";
g.BFS(0);

cout << "\nStarting DFS from vertex 0 (Recursive):\n";

g.DFS(0);

cout << "\nStarting DFS from vertex 0 (Iterative):\n";

g.DFSIterative(0);

return 0;
}
Output :-