CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
Course Code : MCSL-209
Course Title : Data Structures and Algorithms Lab
Assignment Number : BCA_NEW(III)/L-209/Assignment/2025-26
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 31st October, 2025 (for July session)
: 30th April, 2026 (for January session)
There are two questions in this assignment carrying a total of 40 marks. Each
question carries 20 marks. Your Lab Record will carry 40 Marks. Rest 20 marks
are for viva voce. You may use illustrations and diagrams to enhance the
explanations. Please go through the guidelines regarding assignments given in
the Programme Guide for the format of presentation.
Question 1: Write an algorithm and program in ‘C’ language to merge two
sorted linked lists. The resultant linked list should be sorted.
Question 2: Write an algorithm and a program in ‘C’ language to insert and
delete edges in an adjacency list representation of an undirected
graph. Make assumptions, if necessary.
Answer
Question 1: Write an algorithm and program in ‘C’ language to merge two
sorted linked lists. The resultant linked list should be sorted.
Answer:-
Algorithm to Merge Two Sorted Linked Lists
1|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
1. Initialize a dummy node to help with result construction.
2. Use two pointers a and b to traverse both input lists.
3. Compare the current nodes pointed by a and b:
o Append the smaller node to the result list.
o Move the pointer of the list from which the node was taken.
4. Continue this until either list becomes NULL.
5. Append the remaining nodes (if any) from the non-empty list to the
result list.
6. Return the next node of the dummy (as it points to the merged list).
C Program: Merge Two Sorted Linked Lists
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node with given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end of the list
void appendNode(struct Node** headRef, int data) {
struct Node* newNode = createNode(data);
if (*headRef == NULL) {
*headRef = newNode;
} else {
struct Node* temp = *headRef;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
2|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
// Function to print the linked list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Function to merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* a, struct Node* b) {
struct Node dummy;
struct Node* tail = &dummy;
dummy.next = NULL;
while (a != NULL && b != NULL) {
if (a->data <= b->data) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
// Attach the remaining elements
tail->next = (a != NULL) ? a : b;
return dummy.next;
}
// Main function to test the merging
int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;
// Creating first sorted list: 1 -> 3 -> 5
3|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
appendNode(&list1, 1);
appendNode(&list1, 3);
appendNode(&list1, 5);
// Creating second sorted list: 2 -> 4 -> 6
appendNode(&list2, 2);
appendNode(&list2, 4);
appendNode(&list2, 6);
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
struct Node* mergedList = mergeSortedLists(list1, list2);
printf("Merged Sorted List: ");
printList(mergedList);
return 0;
}
Output
4|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
Question 2: Write an algorithm and a program in ‘C’ language to insert and delete
edges in an adjacency list representation of an undirected graph. Make
assumptions, if necessary.
Answer:-
Algorithm
Data Structures:
An array of linked lists: adjList[V]
Each linked list node contains:
o dest: the destination vertex
o next: pointer to the next node
Insert Edge (u, v):
1. Create a new node for vertex v and add it at the beginning of adjList[u].
2. Create a new node for vertex u and add it at the beginning of adjList[v].
Delete Edge (u, v):
1. Traverse adjList[u] and delete the node with value v.
2. Traverse adjList[v] and delete the node with value u.
C Program: Insert and Delete Edges in Undirected Graph
#include <stdio.h>
#include <stdlib.h>
// Structure for an adjacency list node
struct Node {
int dest;
struct Node* next;
};
// Function to create a new adjacency list node
struct Node* createNode(int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
5|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
// Function to insert an edge into the undirected graph
void insertEdge(struct Node* adjList[], int u, int v) {
// Add v to u's list
struct Node* newNode = createNode(v);
newNode->next = adjList[u];
adjList[u] = newNode;
// Add u to v's list (since undirected)
newNode = createNode(u);
newNode->next = adjList[v];
adjList[v] = newNode;
}
// Function to delete an edge from the undirected graph
void deleteEdge(struct Node* adjList[], int u, int v) {
struct Node* temp = adjList[u], *prev = NULL;
// Delete v from u's list
while (temp != NULL && temp->dest != v) {
prev = temp;
temp = temp->next;
}
if (temp != NULL) {
if (prev == NULL) {
adjList[u] = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
}
// Delete u from v's list
temp = adjList[v];
prev = NULL;
while (temp != NULL && temp->dest != u) {
prev = temp;
temp = temp->next;
}
if (temp != NULL) {
6|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
if (prev == NULL) {
adjList[v] = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
}
}
// Function to print the adjacency list
void printGraph(struct Node* adjList[], int V) {
for (int i = 0; i < V; i++) {
struct Node* temp = adjList[i];
printf("Vertex %d: ", i);
while (temp != NULL) {
printf("%d -> ", temp->dest);
temp = temp->next;
}
printf("NULL\n");
}
}
// Main function to test the program
int main() {
int V = 5;
struct Node* adjList[V];
// Initialize adjacency list
for (int i = 0; i < V; i++) {
adjList[i] = NULL;
}
// Insert some edges
insertEdge(adjList, 0, 1);
insertEdge(adjList, 0, 4);
insertEdge(adjList, 1, 2);
insertEdge(adjList, 1, 3);
insertEdge(adjList, 1, 4);
insertEdge(adjList, 2, 3);
insertEdge(adjList, 3, 4);
7|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
CREATED BY ONLINE SOLVED ASSIGNMENT YOUTUBE CHANNEL
printf("Graph after inserting edges:\n");
printGraph(adjList, V);
// Delete an edge
deleteEdge(adjList, 1, 4);
deleteEdge(adjList, 0, 4);
printf("\nGraph after deleting edges (1-4) and (0-4):\n");
printGraph(adjList, V);
return 0;
}
Output
8|Page NOT FOR SALE
🙏 PLEASE SUBSCRIBE OUR CHANNEL 🙏
