Faculty of Engineering and

Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-6
a) Write a c program to implement Insertion sort & Quick sort
#include<stdio.h>
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] > temp) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;

CSE-PIET(PU) Page No:22

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (i < j) {
while (arr[i] <= pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < j) {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotPos = partition(arr, low, high);
quickSort(arr, low, pivotPos - 1);
quickSort(arr, pivotPos + 1, high);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)

CSE-PIET(PU) Page No:23

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

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

printf("\n");
}
int main(){
int n,i,j;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter array elements: ");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Sorted array Insertionsort:");
insertionSort(arr,n);
printArray(arr,n);
printf("Sorted array Using Quicksort ");
quickSort(arr, 0, n - 1);
printArray(arr, n);
return 0;
}

OUTPUT:

CSE-PIET(PU) Page No:24

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

CSE-PIET(PU) Page No:25

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

b) Write a c program to sort the given n integers

and perform following operations i) Find the
products of every two odd position elements ii)
Find the sum of every two even position elements
Explanation: Input : 9 1 9 8 3 5 4 7 2 6 Output: 3
15 35 63 6 10 14 The sorted list of given input is 1
2 3 4 5 6 7 8 9, the product of alternative odd
position elements is 1*3 = 3,3*5=15,5*7=35… and
the sum of two even position elements 2+4
=6,4+6=10…
#include<stdio.h>
void bubbleSort(int a[], int n)
{ int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

CSE-PIET(PU) Page No:26

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

int main(){
int n,i,j;
printf("Enter the size of the array: ");
scanf("%d", &n);
int a[n];
printf("Enter array elements: ");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
bubbleSort(a,n);
for (i = 0; i <n; i++) {
printf("%d\t", a[i]);
}
printf("\n");
for (i = 0; i < n-2; i += 2) {
int n = i+2;
int product = a[i]*a[n];
printf("%d\t",product);
}
printf("\n");
for(i=1;i<n-2;i+=2){
int n = i+2;
int sum = a[i]+a[n];

CSE-PIET(PU) Page No:27

 Faculty of Engineering and
Technology
2303031240665Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("%d\t",sum);
}
}

OUTPUT:

CSE-PIET(PU) Page No:28

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-7
Write a c Program to implement Merge Sort
#include <stdio.h>
void merge(int arr[], int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = 0; // Initialize the index for the auxiliary array
int b[high - low + 1]; // Auxiliary array for merging
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
b[k] = arr[i];
i++;
} else {
b[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
b[k] = arr[i];
i++;
k++;
}

CSE-PIET(PU) Page No:29

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (j <= high) {

b[k] = arr[j];
j++;
k++;
}
for (i = low; i <= high; i++) {
arr[i] = b[i - low];
}
}
void mergeSort(int arr[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
int main() {
int n, i;
printf("Enter the size of the array: ");
scanf("%d", &n);
int a[n];
printf("Enter array elements: ");

CSE-PIET(PU) Page No:30

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

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

scanf("%d", &a[i]);
}
mergeSort(a, 0, n - 1);
printf("Sorted array: ");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
OUTPUT:

CSE-PIET(PU) Page No:31

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-8
a) Write a c program to sort in ascending
order and reverse the individual row
elements of an
mxn matrix
input : 3 4
1423
7 8 10 9
6352
output:
4321
10 9 8 7
6532

#include <stdio.h>
void sortRow(int arr[][100], int row, int col)
{ for (int i = 0; i < row; i++) {
for (int j = 0; j < col - 1; j++) {
for (int k = 0; k < col - j - 1; k++) {
if (arr[i][k] > arr[i][k + 1]) {
int temp = arr[i][k];
arr[i][k] = arr[i][k + 1];
arr[i][k + 1] = temp;

CSE-PIET(PU) Page No:32

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
}
}
}
}
void reverseRow(int arr[][100], int row, int col)
{
for (int i = 0; i < row; i++) {
for (int j = 0; j < col / 2; j++) {
int temp = arr[i][j];
arr[i][j] = arr[i][col - j - 1];
arr[i][col - j - 1] = temp;
}
}
}
void printArray(int arr[][100],int m,int n){
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}

CSE-PIET(PU) Page No:33

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

int main() {
int m, n;
printf("Enter the number of rows and columns (m x n): ");
scanf("%d %d", &m, &n);
int matrix[100][100];
printf("Enter the matrix elements:\n");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j]);
}
}
sortRow(matrix, m, n);
printf("sorted array:-\n");
printArray(matrix,m,n);
printf("reversed array:-\n");
reverseRow(matrix, m, n);
printArray(matrix,m,n);
return 0;
}

CSE-PIET(PU) Page No:34

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

OUTPUT:

CSE-PIET(PU) Page No:35

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-9
a) Write a c program to perform linear Search

#include <stdio.h>
int main() {
int i, e, n;
printf("Enter size of array:");
scanf("%d", &n);
int a[n];
printf("Enter array elements:");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
printf("Enter search element:");
scanf("%d", &e);
for (i = 0; i < n; i++) {
if (a[i] == e) {
printf("The element is found at index: %d", i);
break;
}
}
if (i == n) {
printf("Element not found in the array.");

CSE-PIET(PU) Page No:36

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
return 0;
}

OUTPUT:

CSE-PIET(PU) Page No:37

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

b) Write a c program to perform binary search

#include <stdio.h>
int main() {
int i, e, n;
printf("Enter size of array: ");
scanf("%d", &n);
int a[n];
printf("Enter array elements: ");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
printf("Enter search element: ");
scanf("%d", &e);
int low = 0;
int high = n - 1;
int mid, flag = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == e) {
flag = 1;
break;
} else {
if (e < a[mid])

CSE-PIET(PU) Page No:38

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

high = mid - 1;
else
low = mid + 1;
}
}
if (flag == 1)
printf("\nData found at location: %d\n", mid + 1);
else
printf("\nData not found\n");
return 0;
}
OUTPUT:

CSE-PIET(PU) Page No:39

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-10
Write a c program to Create a single Linked list and
perform Following Operations
A. Insertion At Beginning
B. Insertion At End
C. Insertion After a particular node
D. Insertion Before a particular node
E. Insertion at specific position
F. Search a particular node
G. Return a particular node
H. Deletion at the beginning
I. Deletion at the end
J. Deletion after a particular node
K. Deletion before a particular node
L. Delete a particular node
M. Deletion at a specific position

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};

CSE-PIET(PU) Page No:40

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

struct Node* createNode(int data) {

struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;

CSE-PIET(PU) Page No:41

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (temp->next != NULL) {

temp = temp->next;
}
temp->next = newNode;
}
void insertAfterNode(struct Node* prevNode, int data)
{
if (prevNode == NULL) {
printf("Previous node cannot be NULL.\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void insertBeforeNode(struct Node** head, struct
Node* nextNode, int data) {
if (nextNode == NULL) {
printf("Next node cannot be NULL.\n");
return;
}
struct Node* newNode = createNode(data);
if (*head == nextNode) {

CSE-PIET(PU) Page No:42

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != nextNode) {
temp = temp->next;
}
newNode->next = nextNode;
temp->next = newNode;
}
void insertAtPosition(struct Node** head, int position,
int data) {
if (position < 0) {
printf("Invalid position.\n");
return;
}
if (position == 0) {
insertAtBeginning(head, data);
return;
}
struct Node* newNode = createNode(data);
struct Node* temp = *head;

CSE-PIET(PU) Page No:43

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

for (int i = 0; i < position - 1 && temp != NULL; i++) {

temp = temp->next;
}
if (temp == NULL) {
printf("Position out of range.\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
struct Node* searchNode(struct Node* head, int key) {
while (head != NULL) {
if (head->data == key)
return head;
head = head->next;
}
return NULL;
}
// Function to delete the first node
void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty, deletion not possible.\n");
return;

CSE-PIET(PU) Page No:44

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty, deletion not possible.\n");
return;
}
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
struct Node* secondLast = *head;
while (secondLast->next->next != NULL) {
secondLast = secondLast->next;
}
free(secondLast->next);
secondLast->next = NULL;
}
void deleteAfterNode(struct Node* prevNode) {

CSE-PIET(PU) Page No:45

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

if (prevNode == NULL || prevNode->next == NULL) {

printf("No node to delete.\n");
return;
}
struct Node* temp = prevNode->next;
prevNode->next = temp->next;
free(temp);
}
void deleteBeforeNode(struct Node** head, struct
Node* nextNode) {
if (*head == NULL || *head == nextNode || (*head)
>next == nextNode) {
printf("No node to delete.\n");
return;
}
struct Node* temp = *head;
while (temp->next->next != nextNode) {
temp = temp->next;
}
struct Node* nodeToDelete = temp->next;
temp->next = nextNode;
free(nodeToDelete);
}

CSE-PIET(PU) Page No:46

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

// Function to delete a particular node

void deleteNode(struct Node** head, struct Node*
keyNode) {
if (*head == NULL) {
printf("List is empty, deletion not possible.\n");
return;
}
if (*head == keyNode) {
deleteAtBeginning(head);
return;
}
struct Node* temp = *head;
while (temp->next != keyNode) {
temp = temp->next;
if (temp == NULL) {
printf("Node not found in the list.\n");
return;
}
}
temp->next = keyNode->next;
free(keyNode);
}
// Function to delete a node at a specific position

CSE-PIET(PU) Page No:47

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

void deleteAtPosition(struct Node** head, int position)

{
if (*head == NULL || position < 0) {
printf("List is empty or position is invalid.\n");
return;
}
if (position == 0) {
deleteAtBeginning(head);
return;
}
struct Node* temp = *head;
for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) {
printf("Position out of range.\n");
return;
}
struct Node* nodeToDelete = temp->next;
temp->next = nodeToDelete->next;
free(nodeToDelete);
}
void printList(struct Node* head) {

CSE-PIET(PU) Page No:48

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (head != NULL) {

printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
void freeList(struct Node** head) {
struct Node* temp;
while (*head != NULL) {
temp = *head;
*head = (*head)->next;
free(temp);
}
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
insertAtEnd(&head, 40);
printf("Original List: ");
printList(head);
// Perform operations

CSE-PIET(PU) Page No:49

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

insertAtBeginning(&head, 5);
printf("List after inserting at beginning: ");
printList(head);
insertAfterNode(head->next, 25);
printf("List after inserting after a particular node: ");
printList(head);
insertBeforeNode(&head, head->next->next->next, 35);
printf("List after inserting before a particular node: ");
printList(head);
insertAtPosition(&head, 2, 15);
printf("List after inserting at specific position: ");
printList(head);
struct Node* searchedNode = searchNode(head, 30);
if (searchedNode != NULL)
printf("Node found: %d\n", searchedNode->data);
else
printf("Node not found.\n");
deleteAtBeginning(&head);
printf("List after deletion at beginning: ");
printList(head);
deleteAtEnd(&head);
printf("List after deletion at end: ");
printList(head);

CSE-PIET(PU) Page No:50

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

deleteAfterNode(head->next);
printf("List after deletion after a particular node: ");
printList(head);
deleteBeforeNode(&head, head->next->next);
printf("List after deletion before a particular node: ");
printList(head);
deleteNode(&head, head->next);
printf("List after deleting a particular node: ");
printList(head);
deleteAtPosition(&head, 2);
printf("List after deletion at specific position: ");
printList(head);
// Free the memory allocated to the linked list
freeList(&head);
return o;
}
OUTPUT:

CSE-PIET(PU) Page No:51

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

CSE-PIET(PU) Page No:52

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-11
a) Write a program to Reverse a singly Linked list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

CSE-PIET(PU) Page No:53

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

void printList(struct Node* head) {

while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
struct Node* reverseList(struct Node* head) {
struct Node *prevNode = NULL, *currNode = head,
*nextNode = NULL;
while (currNode != NULL) {
nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);

CSE-PIET(PU) Page No:54

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

insertAtBeginning(&head, 40);
printf("Original List: ");
printList(head);
head = reverseList(head);
printf("Reversed List: ");
printList(head);
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}

CSE-PIET(PU) Page No:55

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

OUTPUT:

CSE-PIET(PU) Page No:56

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

B. Write a c program to check whether the created

linked list is palindrome or not
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node {
char data;
struct Node* next;
};
struct Node* createNode(char data) {
struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtEnd(struct Node** head, char data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {

CSE-PIET(PU) Page No:57

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%c ", head->data);
head = head->next;
}
printf("\n");
}
struct Node* reverseList(struct Node* head) {
struct Node* prevNode = NULL;
struct Node* currNode = head;
while (currNode != NULL) {
struct Node* nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;

CSE-PIET(PU) Page No:58

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

currNode = nextNode;
}
return prevNode;
}
bool isPalindrome(struct Node* head) {
if (head == NULL || head->next == NULL) {
return true;
}
struct Node* slow = head;
struct Node* fast = head;
while (fast->next != NULL && fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
struct Node* secondHalf = reverseList(slow->next);
struct Node* firstHalf = head;
while (secondHalf != NULL) {
if (firstHalf->data != secondHalf->data) {
secondHalf = reverseList(secondHalf);
return false;
}
f

CSE-PIET(PU) Page No:59

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

irstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
secondHalf = reverseList(secondHalf);
return true;
}
void freeList(struct Node** head) {
struct Node* temp;
while (*head != NULL) {
temp = *head;
*head = (*head)->next;
free(temp);
}
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 'r');
insertAtEnd(&head, 'a');
insertAtEnd(&head, 'd');
insertAtEnd(&head, 'a');
insertAtEnd(&head, 'r');
printf("Original List: ");
printList(head);

CSE-PIET(PU) Page No:60

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

if (isPalindrome(head))
printf("The linked list is a palindrome.\n");
else
printf("The linked list is not a palindrome.\n");
freeList(&head);
return 0;
}
OUTPUT:

CSE-PIET(PU) Page No:61

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-12
Write a c program to Create a Circular Linked list and
perform Following Operations
A. Insertion At Beginning
B. Insertion At End
C. Insertion After a particular node
D. Insertion Before a particular node
E. Insertion at specific position
F. Search a particular node
G. Return a particular node
H. Deletion at the beginning
I. Deletion at the end
J. Deletion after a particular node
K. Deletion before a particular node
L. Delete a particular node
M. Deletion at a specific position

CSE-PIET(PU) Page No:62

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
// Function to create a new node
struct Node* createNode(int value) {
struct Node*newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {

CSE-PIET(PU) Page No:63

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

head = newNode;
newNode->next = head;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
head = newNode;
}
printf("List after insertion at beginning: %d\n", value);
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
newNode->next = head;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;

CSE-PIET(PU) Page No:64

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
temp->next = newNode;
newNode->next = head;
}
printf("List after insertion at end: ");
struct Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
// Function to insert a node after a particular node
void insertAfterNode(int key, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
while (temp->data != key) {
temp = temp->next;
if (temp == head) {

CSE-PIET(PU) Page No:65

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("Node with key %d not found.\n", key);

return;
}
}
newNode->next = temp->next;
temp->next = newNode;
printf("List after insertion after a particular node: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
// Function to insert a node before a particular node
void insertBeforeNode(int key, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
struct Node* prev = NULL;

CSE-PIET(PU) Page No:66

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

do {
prev = temp;
temp = temp->next;
if (temp->data == key) {
prev->next = newNode;
newNode->next = temp;
printf("List after insertion before a particular node: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
return;
}
} while (temp != head);
printf("Node with key %d not found.\n", key);
}

// Function to insert a node at a specific position

void insertAtPosition(int position, int value) {
if (position < 1) {
printf("Invalid position.\n");

CSE-PIET(PU) Page No:67

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

return;
}
if (position == 1) {
insertAtBeginning(value);
return;
}
struct Node* newNode = createNode(value);
struct Node* temp = head;
for (int i = 1; i < position - 1; i++) {
if (temp->next == head) {
printf("Position out of range.\n");
return;
}
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
printf("List after insertion at specific position: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);

CSE-PIET(PU) Page No:68

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("\n");
}
// Function to search for a particular node
void searchNode(int key) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
do {
if (temp->data == key) {
printf("Node found: %d\n", key);
return;
}
temp = temp->next;
} while (temp != head);
printf("Node with key %d not found.\n", key);
}
// Function to delete the first node
void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty.\n");
return;

CSE-PIET(PU) Page No:69

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
if (head->next == head) {
free(head);
head = NULL;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = head->next;
struct Node* toDelete = head;
head = head->next;
free(toDelete);
}
printf("List after deletion at beginning: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
// Function to delete the last node

CSE-PIET(PU) Page No:70

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

void deleteAtEnd() {
if (head == NULL) {
printf("List is empty.\n");
return;
}
if (head->next == head) {
free(head);
head = NULL;
} else {
struct Node* temp = head;
struct Node* prev = NULL;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
free(temp);
}
printf("List after deletion at end: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;

CSE-PIET(PU) Page No:71

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

} while (current != head);

printf("\n");
}
// Function to delete the node after a particular node
void deleteAfterNode(int key) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
while (temp->data != key) {
temp = temp->next;
if (temp == head) {
printf("Node with key %d not found.\n", key);
return;
}
}
struct Node* toDelete = temp->next;
temp->next = toDelete->next;
free(toDelete);
printf("List after deletion after a particular node: ");
struct Node* current = head;
do {

CSE-PIET(PU) Page No:72

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

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

current = current->next;
} while (current != head);
printf("\n");
}
// Function to delete the node before a particular node
void deleteBeforeNode(int key) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
struct Node* prev = NULL;
while (temp->data != key) {
prev = temp;
temp = temp->next;
if (temp == head) {
printf("Node with key %d not found.\n", key);
return;
}
}
if (temp == head) {
printf("No node found before %d.\n", key);

CSE-PIET(PU) Page No:73

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

return;
}
struct Node* toDelete = prev->next;
prev->next = toDelete->next;
free(toDelete);
printf("List after deletion before a particular node: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
// Function to delete a particular node
void deleteNode(int key) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
struct Node* prev = NULL;
while (temp->data != key) {
prev = temp;

CSE-PIET(PU) Page No:74

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

temp = temp->next;
if (temp == head) {
printf("Node with key %d not found.\n", key);
return;
}
}
if (temp == head) {
deleteAtBeginning();
return;
}
prev->next = temp->next;
free(temp);
printf("List after deleting a particular node: ");
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
// Function to delete a node at a specific position
void deleteAtPosition(int position) {
if (head == NULL) {

CSE-PIET(PU) Page No:75

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("List is empty.\n");
return;
}
if (position < 1) {
printf("Invalid position.\n");
return;
}
if (position == 1) {
deleteAtBeginning();
return;
}
struct Node* temp = head;
struct Node* prev = NULL;
for (int i = 1; i < position; i++) {
prev = temp;
temp = temp->next;
if (temp == head) {
printf("Position out of range.\n");
return;
}
}
prev->next = temp->next;
free(temp);

CSE-PIET(PU) Page No:76

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("List after deletion at specific position: ");

struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
// Function to display the list
void display() {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
printf("Circular Linked List: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {

CSE-PIET(PU) Page No:77

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

insertAtBeginning(10);
insertAtEnd(20);
insertAfterNode(10, 15);
insertBeforeNode(20, 25);
searchNode(15);
insertAtPosition(3, 30);
deleteAtBeginning();
deleteAtEnd();
deleteAfterNode(10);
deleteBeforeNode(20);
deleteNode(30);
deleteAtPosition(1);
return 0;
}OUTPUT:

CSE-PIET(PU) Page No:78

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-13
Write a c program to Create a Circular single Linked list and perform Following
Operations
A. Insertion After a particular node
B. Insertion Before a particular node
C. Search a particular node
D. Return a particular node
E. Deletion before a particular node
F. Delete a particular node

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

CSE-PIET(PU) Page No:79

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

void insertAfter(struct Node* prevNode, int value) {

if (prevNode == NULL) {
printf("Previous node cannot be NULL.\n");
return;
}
struct Node* newNode = createNode(value);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void insertBefore(struct Node** headRef, struct Node*
nextNode, int value) {
struct Node* newNode = createNode(value);
if (*headRef == NULL) {
*headRef = newNode;
newNode->next = newNode;
return;
}
struct Node* current = *headRef;
while (current->next != nextNode) {
current = current->next;
if (current == *headRef) {
printf("Node not found.\n");
return;

CSE-PIET(PU) Page No:80

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

}
}
newNode->next = nextNode;
current->next = newNode;
if (current == *headRef)
*headRef = newNode;
}
struct Node* searchNode(struct Node* head, int key) {
if (head == NULL)
return NULL;
struct Node* current = head;
do {
if (current->data == key)
return current;
current = current->next;
} while (current != head);
return NULL;
}
void deleteBefore(struct Node** headRef, struct Node*
nextNode) {
if (*headRef == NULL || (*headRef)->next ==
nextNode) {
printf("No node to delete before the given node.\n");

CSE-PIET(PU) Page No:81

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

return;
}
struct Node* current = *headRef;
while (current->next->next != nextNode) {
current = current->next;
if (current->next == *headRef) {
printf("Node not found.\n");
return;
}
}
struct Node* temp = current->next;
current->next = nextNode;
free(temp);
}
void deleteNode(struct Node** headRef, struct Node*
delNode) {
if (*headRef == NULL) {
printf("List is empty.\n");
return;
}
struct Node* current = *headRef;
if (current == delNode) {
struct Node* temp = *headRef;

CSE-PIET(PU) Page No:82

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (temp->next != *headRef)

temp = temp->next;
temp->next = (*headRef)->next;
*headRef = (*headRef)->next;
free(current);
return;
}
while (current->next != delNode) {
current = current->next;
if (current->next == *headRef) {
printf("Node not found.\n");
return;
}
}
current->next = delNode->next;
free(delNode);
}
void displayList(struct Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* current = head;

CSE-PIET(PU) Page No:83

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("\n");
}
int main() {
struct Node* head = NULL;
head = createNode(1);
head->next = head; // Circular reference
insertAfter(head, 2);
insertAfter(head->next, 3);
insertAfter(head->next->next, 4);
printf("Circular linked list: ");
displayList(head);
insertBefore(&head, head, 0);
printf("After inserting before head: ");
displayList(head);
int key = 3;
struct Node* foundNode = searchNode(head, key);
if (foundNode != NULL)
printf("Node with value %d found.\n", key);
else

CSE-PIET(PU) Page No:84

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("Node with value %d not found.\n", key);

deleteBefore(&head, head->next->next);
printf("After deleting node before 4: ");
displayList(head);
deleteNode(&head, head->next->next);
printf("After deleting node with value 4: ");
displayList(head);
return 0;
}
OUTPUT:

CSE-PIET(PU) Page No:85

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

PRACTICAL-14
Write a c program to Create a Circular Double Linked
list and perform Following Operations
A. Insertion After a particular node
B. Insertion Before a particular node
C. Search a particular node
D. Return a particular node
E. Deletion before a particular node
F. Delete a particular node

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node* createNode(int data);
void insertAfter(struct Node** head_ref, int value, int key);
void insertBefore(struct Node** head_ref, int value, int key);
struct Node* searchNode(struct Node* head, int key);
struct Node* returnNode(struct Node* head, int key);
void deleteBefore(struct Node** head_ref, int key);

CSE-PIET(PU) Page No:86

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

void deleteNode(struct Node** head_ref, int key);

void displayList(struct Node* head);
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void insertAfter(struct Node** head_ref, int value, int key) {
struct Node* newNode = createNode(value);
if (*head_ref == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head_ref;
while (temp->data != key) {
temp = temp->next;
if (temp == *head_ref) {
printf("Key not found in the list.\n");
return;
}
}

CSE-PIET(PU) Page No:87

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

newNode->prev = temp;
newNode->next = temp->next;
temp->next->prev = newNode;
temp->next = newNode;
}
void insertBefore(struct Node** head_ref, int value, int key) {
struct Node* newNode = createNode(value);
if (*head_ref == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head_ref;
while (temp->data != key) {
temp = temp->next;
if (temp == *head_ref) {
printf("Key not found in the list.\n");
return;
}
}
newNode->prev = temp->prev;
newNode->next = temp;
temp->prev->next = newNode;
temp->prev = newNode;

CSE-PIET(PU) Page No:88

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

if (temp == *head_ref)
*head_ref = newNode;
}
struct Node* searchNode(struct Node* head, int key) {
if (head == NULL) {
printf("List is empty.\n");
return NULL;
}
struct Node* temp = head;
do {
if (temp->data == key)
return temp;
temp = temp->next;
} while (temp != head);
printf("Key not found in the list.\n");
return NULL;
}
struct Node* returnNode(struct Node* head, int key) {
return searchNode(head, key);
}
void deleteBefore(struct Node** head_ref, int key) {
if (*head_ref == NULL) {
printf("List is empty.\n");

CSE-PIET(PU) Page No:89

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

return;
}
struct Node* temp = *head_ref;
while (temp->data != key) {
temp = temp->next;
if (temp == *head_ref) {
printf("Key not found in the list.\n");
return;
}
}
struct Node* delNode = temp->prev;
delNode->prev->next = temp;
temp->prev = delNode->prev;
if (delNode == *head_ref)
*head_ref = temp;
free(delNode);
}
void deleteNode(struct Node** head_ref, int key) {
if (*head_ref == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = *head_ref;

CSE-PIET(PU) Page No:90

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

while (temp->data != key) {

temp = temp->next;
if (temp == *head_ref) {
printf("Key not found in the list.\n");
return;
}
}
if (temp == *head_ref) {
*head_ref = temp->next;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
void displayList(struct Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;

CSE-PIET(PU) Page No:91

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

} while (temp != head);

printf("\n");
}
int main() {
struct Node* head = NULL;
head = createNode(1);
head->next = createNode(2);
head->next->prev = head;
head->next->next = head;
head->prev = head->next;
printf("Initial list: ");
displayList(head);
insertAfter(&head, 3, 2);
printf("List after insertion after 2: ");
displayList(head);
insertBefore(&head, 4, 3);
printf("List after insertion before 3: ");
displayList(head);
struct Node* searchedNode = searchNode(head, 3);
printf("Searched node: %d\n", searchedNode->data);
struct Node* returnedNode = returnNode(head, 2);
printf("Returned node: %d\n", returnedNode->data);
deleteBefore(&head, 3);

CSE-PIET(PU) Page No:92

 Faculty of Engineering and
Technology
Subject: CTSD-2 (303105151) ERP No: 2303031240642

printf("List after deletion before 3: ");

displayList(head);
deleteNode(&head, 3);
printf("List after deletion of 3: ");
displayList(head);
return 0;
}
OUTPUT:-

CSE-PIET(PU) Page No:93