GURU JAMBHESHWAR UNIVERSITY OF

SCIENCE AND TECHNOLOGY, HISAR

DEPARTMENT OF COMPUTER SCIENCE AND
ENGINEERING

A PRACTICAL FILE OF DSA LAB

[Link] 2nd year- 3rd semester

SUBMITTED TO: SUBMITTED BY:

Mrs. Sharmila Prantika Maurya
Roll No. 240010150020
CSE(AI&ML) Batch-1

1
 INDEX

[Link]. Program Page No. Signature

Program to implement array operations, including

1 element insertion deletion, and traversal. 3

Program to implement 2D array operations, including

2 element traversal, matrix addition, multiplication. 7

Program to perform manage a singly linked list that

3 support operations such as insertion, deletion and 11
traversal.
Program to handle a doubly linked list, supporting
4 insertion, deletion and traversal operation. 17

Program to handle a circular linked list, supporting

5 traversing, insertion and deletion operations. 22

Program that implements a stack using array and

6 linked list, support operations such as push and pop. 28

Program to implement a queue using array and linked

7 list, to perform enqueue, dequeue operations. 34

Program to implement linear search in array.

8 40

Program to implement binary search in array.

9 42

Program to implement bubble sort.

10 45

Program to implement selection sort.

11 47

Program to implement insertion sort.

12 49

Program to implement quick sort.

13 51

2
1: Write a program to implement array operations, including element
insertion, deletion, and traversal.
#include <stdio.h>

int main() {

int arr[100], n, i, pos, element, choice;

printf("Enter number of elements in array: ");

scanf("%d", &n);

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

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

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

while (1) {

printf("\n\n----- Array Operations Menu -----\n");

printf("1. Display elements\n");

printf("2. Insert an element\n");

printf("3. Delete an element\n");

printf("4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Array elements are: ");

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

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

printf("\n");

3
 break;

case 2:

printf("Enter position to insert (1 to %d): ", n + 1);

scanf("%d", &pos);

if (pos < 1 || pos > n + 1) {

printf("Invalid position!\n");

break;

printf("Enter element to insert: ");

scanf("%d", &element);

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

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

arr[pos - 1] = element;

n++;

printf("Element inserted successfully.\n");

break;

case 3:

printf("Enter position to delete (1 to %d): ", n);

scanf("%d", &pos);

if (pos < 1 || pos > n) {

printf("Invalid position!\n");

break;

element = arr[pos - 1];

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

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

n--;

4
 printf("Deleted element: %d\n", element);

break;

case 4:

printf("Exiting program.\n");

return 0;

default:

printf("Invalid choice! Please try again.\n");

return 0;

5
OUTPUT:

6
2: Write a program to implement 2D array operations, including element
traversal, matrix addition, multiplication.
#include <stdio.h>

int main() {
int a[10][10], b[10][10], sum[10][10], product[10][10];
int r1, c1, r2, c2, i, j, k;

// Input for first matrix

printf("Enter rows and columns of first matrix: ");
scanf("%d %d", &r1, &c1);

printf("Enter elements of first matrix:\n");

for (i = 0; i < r1; i++) {
for (j = 0; j < c1; j++) {
scanf("%d", &a[i][j]);
}
}

// Input for second matrix

printf("Enter rows and columns of second matrix: ");
scanf("%d %d", &r2, &c2);

printf("Enter elements of second matrix:\n");

for (i = 0; i < r2; i++) {
for (j = 0; j < c2; j++) {
scanf("%d", &b[i][j]);
}
}

7
// Traversal
printf("\nFirst Matrix:\n");
for (i = 0; i < r1; i++) {
for (j = 0; j < c1; j++) {
printf("%d\t", a[i][j]);
}
printf("\n");
}

printf("\nSecond Matrix:\n");
for (i = 0; i < r2; i++) {
for (j = 0; j < c2; j++) {
printf("%d\t", b[i][j]);
}
printf("\n");
}

// Matrix Addition
if (r1 == r2 && c1 == c2) {
printf("\nMatrix Addition:\n");
for (i = 0; i < r1; i++) {
for (j = 0; j < c1; j++) {
sum[i][j] = a[i][j] + b[i][j];
printf("%d\t", sum[i][j]);
}
printf("\n");
}
} else {

8
 printf("\nMatrix addition not possible (dimension mismatch).\n");
}

// Matrix Multiplication
if (c1 == r2) {
printf("\nMatrix Multiplication:\n");
for (i = 0; i < r1; i++) {
for (j = 0; j < c2; j++) {
product[i][j] = 0;
for (k = 0; k < c1; k++) {
product[i][j] += a[i][k] * b[k][j];
}
printf("%d\t", product[i][j]);
}
printf("\n");
}
} else {
printf("\nMatrix multiplication not possible (invalid dimensions).\n");
}
return 0;
}

9
OUTPUT:

10
3: Write a program to perform manage a singly linked list that supports
operations such as insertion, deletion, reversal, and traversal.
#include <stdio.h>
#include <stdlib.h>
// Define node structure
struct Node {
int data;
struct Node* next;
};

// Function prototypes
void insertAfterValue(struct Node* head, int value, int after);
void deleteByValue(struct Node** head, int value);
void reverseList(struct Node** head);
void traverse(struct Node* head);

int main() {
struct Node* head = NULL;
int choice, value, after;

while (1) {
printf("\n--- Singly Linked List Operations ---\n");
printf("[Link] after a value\n");
printf("[Link] by value\n");
printf("[Link] list\n");
printf("[Link] list\n");
printf("[Link]\n");
printf("Enter your choice: ");
scanf("%d", &choice);

11
switch (choice){
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
printf("Insert after which value? ");
scanf("%d", &after);
insertAfterValue(head, value, after);
break;

case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteByValue(&head, value);
break;

case 3:
reverseList(&head);
printf("List reversed successfully.\n");
break;

case 4:
traverse(head);
break;

case 5:
printf("Exiting program.\n");
exit(0);

12
 default:
printf("Invalid choice! Please try again.\n");
}
}

return 0;
}

// Insert after a specific value

void insertAfterValue(struct Node* head, int value, int after) {
struct Node* temp = head;
while (temp != NULL && temp->data != after)
temp = temp->next;

if (temp == NULL) {
printf("Value %d not found in the list.\n", after);
return;
}

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

newNode->data = value;
newNode->next = temp->next;
temp->next = newNode;
printf("Inserted %d after %d.\n", value, after);
}

// Delete by value
void deleteByValue(struct Node** head, int value) {
struct Node *temp = *head, *prev = NULL;

13
 // If head node holds the value
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
printf("Deleted %d from the list.\n", value);
return;
}

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

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

if (temp == NULL) {
printf("Value %d not found in the list.\n", value);
return;
}

prev->next = temp->next;
free(temp);
printf("Deleted %d from the list.\n", value);
}

// Reverse the linked list

void reverseList(struct Node** head) {
struct Node *prev = NULL, *current = *head, *next = NULL;

while (current != NULL) {

14
 next = current->next;
current->next = prev;
prev = current;
current = next;
}

*head = prev;
}

// Traverse the list

void traverse(struct Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}

printf("Linked List: ");

while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}

15
OUTPUT:

16
4: Write a program to handle a doubly linked list, supporting insertion,
deletion, and traversal operations.
#include <stdio.h>
#include <stdlib.h>

// Doubly Linked List Node

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

// Function Prototypes
void insertAtBeginning(struct Node** head, int data);
void insertAtEnd(struct Node** head, int data);
void deleteByValue(struct Node** head, int value);
void traverseForward(struct Node* head);
void traverseBackward(struct Node* head);

int main() {
struct Node* head = NULL;
int choice, value;

while (1) {
printf("\n--- Doubly Linked List Menu ---\n");
printf("1. Insert at beginning\n");
printf("2. Delete by value\n");
printf("3. Traverse forward\n");
printf("4. Exit\n");

17
 printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert at beginning: ");
scanf("%d", &value);
insertAtBeginning(&head, value);
break;

case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteByValue(&head, value);
break;

case 3:
traverseForward(head);
break;

case 4:
printf("Exiting program.\n");
exit(0);

default:
printf("Invalid choice. Please try again.\n");
}
}

18
 return 0;
}

// Insert at beginning
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = *head;

if (*head != NULL)
(*head)->prev = newNode;

*head = newNode;
printf("Inserted %d at the beginning.\n", data);
}

// Delete by value
void deleteByValue(struct Node** head, int value) {
if (*head == NULL) {
printf("List is empty. Cannot delete.\n");
return;
}

struct Node* temp = *head;

// Find node with the value
while (temp != NULL && temp->data != value)
temp = temp->next;

19
 if (temp == NULL) {
printf("Value %d not found in the list.\n", value);
return;
}
// Update links
if (temp->prev != NULL)
temp->prev->next = temp->next;
else
*head = temp->next; // Deleting head
if (temp->next != NULL)
temp->next->prev = temp->prev;

free(temp);
printf("Deleted %d from the list.\n", value);
}
// Traverse forward
void traverseForward(struct Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
printf("List (forward): ");
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}

20
OUTPUT:

21
5: Write a program to handle a circular linked list, supporting traversing,
insertion, and deletion operations.
#include <stdio.h>
#include <stdlib.h>

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

// Function Prototypes
void insertEnd(struct Node** head, int value);
void deleteNode(struct Node** head, int key);
void traverse(struct Node* head);

int main() {
struct Node* head = NULL;
int choice, value;

while (1) {
printf("\n--- Circular Linked List Menu ---\n");
printf("1. Insert at end\n");
printf("2. Delete by value\n");
printf("3. Traverse\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

22
 switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertEnd(&head, value);
break;

case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(&head, value);
break;

case 3:
traverse(head);
break;

case 4:
printf("Exiting program.\n");
exit(0);

default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

23
// Insert at the end
void insertEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; // Initially points to itself

if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;

// Traverse to the last node

while (temp->next != *head)
temp = temp->next;

temp->next = newNode;
newNode->next = *head;
}

printf("Inserted %d at the end.\n", value);

}

// Delete a node by value

void deleteNode(struct Node** head, int key) {
if (*head == NULL) {
printf("List is empty.\n");
return;
}

24
struct Node *current = *head, *prev = NULL;

// Special case: deleting the head node

if (current->data == key) {
if (current->next == *head) {
free(current);
*head = NULL;
printf("Deleted %d (only node).\n", key);
return;
}

// Find last node

struct Node* last = *head;
while (last->next != *head)
last = last->next;

last->next = current->next;
*head = current->next;
free(current);
printf("Deleted %d (head node).\n", key);
return;
}

// Find the node to delete

prev = current;
current = current->next;
while (current != *head && current->data != key) {
prev = current;
current = current->next;

25
 }

if (current == *head) {
printf("Value %d not found in the list.\n", key);
return;
}

prev->next = current->next;
free(current);
printf("Deleted %d.\n", key);
}

// Traverse the list

void traverse(struct Node* head) {
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("(back to head)\n");
}

26
OUTPUT:

27
6: Write a program that implements a stack using array and linked list,
support operations such as push and pop.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

// ---------- Stack using Array ----------

int stackArr[MAX];
int top = -1;

void pushArray(int value) {

if (top == MAX - 1)
printf("Stack Overflow (Array)\n");
else {
top++;
stackArr[top] = value;
printf("%d pushed to stack (Array)\n", value);
}
}

void popArray() {
if (top == -1)
printf("Stack Underflow (Array)\n");
else {
printf("%d popped from stack (Array)\n", stackArr[top]);
top--;
}
}

28
void displayArray() {
if (top == -1)
printf("Stack is empty (Array)\n");
else {
printf("Stack elements (Array): ");
for (int i = top; i >= 0; i--)
printf("%d ", stackArr[i]);
printf("\n");
}
}

// ---------- Stack using Linked List ----------

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

struct Node* topLL = NULL;

void pushList(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = topLL;
topLL = newNode;
printf("%d pushed to stack (Linked List)\n", value);

29
}

void popList() {
if (topLL == NULL)
printf("Stack Underflow (Linked List)\n");
else {
struct Node* temp = topLL;
printf("%d popped from stack (Linked List)\n", topLL->data);
topLL = topLL->next;
free(temp);
}
}

void displayList() {
if (topLL == NULL)
printf("Stack is empty (Linked List)\n");
else {
struct Node* temp = topLL;
printf("Stack elements (Linked List): ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}

// ---------- Main Function ----------

int main() {

30
int choice, value, type;

while (1) {
printf("\n--- Stack Implementation ---\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

if (choice == 4)
break;

printf("Choose stack type:\n1. Array\n2. Linked List\nEnter your choice: ");

scanf("%d", &type);

switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
if (type == 1) pushArray(value);
else if (type == 2) pushList(value);
else printf("Invalid stack type\n");
break;

case 2:
if (type == 1) popArray();
else if (type == 2) popList();
else printf("Invalid stack type\n");
break;

31
 case 3:
if (type == 1) displayArray();
else if (type == 2) displayList();
else printf("Invalid stack type\n");
break;

default:
printf("Invalid choice\n");
}
}

return 0;
}

32
OUTPUT:

33
7: Write a program to implement a queue using array and linked list to
perform enqueue, dequeue operations.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

// ---------- Queue using Array ----------

int queueArr[MAX];
int front = -1, rear = -1;

void enqueueArray(int value) {

if (rear == MAX - 1)
printf("Queue Overflow (Array)\n");
else {
if (front == -1)
front = 0;
rear++;
queueArr[rear] = value;
printf("%d enqueued to queue (Array)\n", value);
}
}

void dequeueArray() {
if (front == -1 || front > rear)
printf("Queue Underflow (Array)\n");
else {
printf("%d dequeued from queue (Array)\n", queueArr[front]);
front++;
}

34
}

void displayArray() {
if (front == -1 || front > rear)
printf("Queue is empty (Array)\n");
else {
printf("Queue elements (Array): ");
for (int i = front; i <= rear; i++)
printf("%d ", queueArr[i]);
printf("\n");
}
}

// ---------- Queue using Linked List ----------

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

struct Node* frontLL = NULL;

struct Node* rearLL = NULL;

void enqueueList(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;

35
 newNode->next = NULL;

if (rearLL == NULL) {
frontLL = rearLL = newNode;
} else {
rearLL->next = newNode;
rearLL = newNode;
}
printf("%d enqueued to queue (Linked List)\n", value);
}

void dequeueList() {
if (frontLL == NULL) {
printf("Queue Underflow (Linked List)\n");
return;
}
struct Node* temp = frontLL;
printf("%d dequeued from queue (Linked List)\n", frontLL->data);
frontLL = frontLL->next;
if (frontLL == NULL)
rearLL = NULL;
free(temp);
}

void displayList() {
if (frontLL == NULL)
printf("Queue is empty (Linked List)\n");
else {
struct Node* temp = frontLL;

36
 printf("Queue elements (Linked List): ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}

// ---------- Main Function ----------

int main() {
int choice, value, type;

while (1) {
printf("\n--- Queue Implementation ---\n");
printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

if (choice == 4)
break;

printf("Choose queue type:\n1. Array\n2. Linked List\nEnter your choice: ");

scanf("%d", &type);

switch (choice) {
case 1:
printf("Enter value to enqueue: ");
scanf("%d", &value);

37
 if (type == 1) enqueueArray(value);
else if (type == 2) enqueueList(value);
else printf("Invalid queue type\n");
break;

case 2:
if (type == 1) dequeueArray();
else if (type == 2) dequeueList();
else printf("Invalid queue type\n");
break;

case 3:
if (type == 1) displayArray();
else if (type == 2) displayList();
else printf("Invalid queue type\n");
break;

default:
printf("Invalid choice\n");
}
}

return 0;
}

38
OUTPUT:

39
8: Write a program to implement linear search in array.
#include <stdio.h>
int main() {
int arr[100], n, i, key, found = 0;
// Input number of elements
printf("Enter number of elements in array: ");
scanf("%d", &n);

// Input elements
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Input element to search
printf("Enter element to search: ");
scanf("%d", &key);

// Linear Search logic

for (i = 0; i < n; i++) {
if (arr[i] == key) {
printf("Element %d found at position %d\n", key, i + 1);
found = 1;
break;
}
}
if (!found)
printf("Element %d not found in the array\n", key);
return 0;
}

40
OUTPUT:

41
9: Write a program to implement binary search in array.
#include <stdio.h>

int main() {
int arr[100], n, i, key;
int low, high, mid, found = 0;

// Input number of elements

printf("Enter number of elements in array: ");
scanf("%d", &n);

// Input elements (must be sorted for binary search)

printf("Enter %d elements in sorted order:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input element to search

printf("Enter element to search: ");
scanf("%d", &key);

// Binary search logic

low = 0;
high = n - 1;

while (low <= high) {

mid = (low + high) / 2;

if (arr[mid] == key) {

42
 printf("Element %d found at position %d\n", key, mid + 1);
found = 1;
break;
} else if (arr[mid] < key) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}

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

return 0;
}

43
OUTPUT:

44
10: Write a program to implement bubble sort.
#include <stdio.h>
int main() {
int arr[100], 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", &arr[i]);
}
// Bubble Sort algorithm
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("\nSorted array in ascending order:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

45
OUTPUT:

46
11: Write a program to implement selection sort.
#include <stdio.h>
int main() {
int arr[100], n, i, j, minIndex, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Selection Sort algorithm
for (i = 0; i < n - 1; i++) {
minIndex = i; // assume the first element is the minimum
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // update index of the smallest element
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
printf("\nSorted array in ascending order:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

47
OUTPUT:

48
12: Write a program to implement insertion sort.
#include <stdio.h>
int main() {
int arr[100], n, i, j, key;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Insertion Sort algorithm
for (i = 1; i < n; i++) {
key = arr[i]; // Element to be inserted
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--;
}
arr[j + 1] = key; // Insert the key into correct position
}
printf("\nSorted array in ascending order:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

49
OUTPUT:

50
13: Write a program to implement quick sort.
#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing last element as pivot
int i = (low - 1);
int j;

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

if (arr[j] < pivot) { // If current element is smaller than pivot
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // Place pivot in correct position
return (i + 1);
}

// Quick Sort function (recursive)

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

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

// Recursively sort elements before and after partition

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int arr[100], n, i;

printf("Enter number of elements: ");

scanf("%d", &n);

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

for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

quickSort(arr, 0, n - 1);

printf("\nSorted array in ascending order:\n");

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

printf("\n");
return 0;
}

52
OUTPUT:

53