BMS COLLEGE OF ENGINEERING
(Autonomous College under VTU)
Bull Temple Road, Basavanagudi, Bangalore - 560019
A report on
“Data structures and Applications Laboratory”
Submitted in partial fulfilment of the requirements for the award of degree
BACHELOR OF ENGINEERING
IN
COMPUTER SCIENCE AND BUSINESS SYSTEMS
By
Student Name
Mahesh (1BM24CB033)
Course in Charge
Tejaswini K
Assistant Professor
Department of Computer Science and Business Systems
2024-2025
BMS COLLEGE OF ENGINEERING
(Autonomous College under VTU)
Bull Temple Road, Basavanagudi, Bangalore –560019
Department of Computer Science and Business Systems
C E R T I F I C A T E
This is to certify that the lab report entitled “Data structures and Applications
Laboratory” is a bona-fide work carried out by Mahesh(1BM24CB033) in partial
fulfilment for the award of degree of Bachelor of Engineering in Computer Science
and Business Systems from Visvesvaraya Technological University, Belgaum
during the year 2024-2025. The report has been approved as it satisfies the academic
requirements in respect of technical activity prescribed for the Bachelor of Engineering
Degree.
Signature of Course in Charge Signature of the HoD
Tejaswini K Dr. R. Ashok Kumar
Assistant Professor Professor and HoD
Dept of CSBS, BMSCE Dept of CSBS, BMSCE
Name of the Examiners Signature of the Examiners
1.
2.
Maximum Marks
Marks Obtained
Table of Contents
[Link]. Program Details Page No.
1 Write a program to implement Singly Linked List with following
operations
a) Create a linked list.
b) Insertion of a node at first position, at any position and
c) Deletion of first element, last element in the list
d) Display the contents of the linked list
2 Write a C program to perform polynomial addition using a linked list
with following operations.
a) Create two linked list to Accept two polynomials as input from
the user.
b) Perform the addition of these two polynomials.
c) Display the input polynomials and the resulting polynomial in a
readable format.
3 Write a program to Implement Singly Linked List with following
operations
a) Sort the linked list.
b) Reverse the linked list.
c) Concatenation of two linked lists
4 Write a program to Implement doubly linked list with primitive
operations.
a) Create a doubly linked list.
b) Insert a new node to the left of the node.
c) Delete the node based on a specific value
d) Display the contents of the list
5 Write a program to convert a given valid parenthesized infix arithmetic
expression to postfix expression. The expression consists of single
character operands and the binary operators + (plus), - (minus), *
(multiply) and / (divide)
6 Write a C program to check if parentheses (and other types of brackets)
are balanced in an expression.
7 Write a program to simulate the working of a circular queue of integers
using an array. Provide the following operations. a) Insert b) Delete c)
Display
The program should print appropriate messages for queue empty and
queue overflow conditions.
8 Write a program
a) To construct a binary Search tree.
b) To traverse the tree using all the methods i.e., in-order, pre order and
post order
c) To display the elements in the tree.
9 Write a program
a. To construct a binary search tree
b. To implement iterative in order traversal
c. To delete a given element
10 Write a program to construct an AVL tree of integers
1. Write a program to implement Singly Linked List with following operations
a) Create a linked list.
b) Insertion of a node at first position, at any position and
c) Deletion of first element, last element in the list
d) Display the contents of the linked list
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
};
//creating a Linked List
struct Node* head=NULL;
struct Node* createNode(int val)
{
struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
newNode->data=val;
newNode->next=NULL;
return newNode;
}
//Insertion at any position
void insertion(int val,int pos)
{
struct Node* newNode=createNode(val);
if(pos==1)
{
newNode->next=head;
head=newNode;
return ;
}
struct Node* temp=head;
for(int i=1;i<pos-1 && temp!=NULL ; i++)
{
temp=temp->next;
}
if(temp==NULL)
{
printf("Out of bound position\n");
return ;
}
newNode->next=temp->next;
temp->next=newNode;
}
//deletion of first element
void deleteHead()
{
if(head==NULL)
{
printf("List is empty\n");
return;
}
struct Node* temp=head;
head=head->next;
free(temp);
}
//deletion at end
void deleteEnd()
{
if(head==NULL)
{
printf("List is empty\n");
return;
}
struct Node* temp=head;
if(temp->next==NULL)
{
head=NULL;
return;
}
while(temp->next->next!=NULL)//reaching second last element
{
temp=temp->next;
}
temp->next=temp->next->next;
free(temp->next);
}
//display
void display()
{
if(head==NULL)
{
printf("List is empty\n");
return ;
}
struct Node* temp=head;
while(temp!=NULL)
{
printf("%d -> ",temp->data);
temp=temp->next;
}
printf("\n");
}
int main()
{
int value,choice;
printf("Single Linked List Operation \n\n");
printf("[Link]\[Link] Head\[Link] Tail\[Link]\[Link]\n");
do
{
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("Enter the value to insert: ");
scanf("%d",&value);
int pos;
printf("Enter position: ");
scanf("%d",&pos);
insertion(value,pos);
break;
case 2:deleteHead();
break;
case 3:deleteEnd();
break;
case 4:display();
break;
case 5:printf("Exiting\n");
break;
default:printf("Invalid option!\n");
}
} while (choice!=5);
return 0;
}
2. Write a C program to perform polynomial addition using a linked list with following
operations.
a) Create two linked list to Accept two polynomials as input from the user.
b) Perform the addition of these two polynomials.
c) Display the input polynomials and the resulting polynomial in a readable format.
#include <stdio.h>
#include <stdlib.h>
typedef struct term
{
int coeff;
int exp;
struct term *next;
}TERM;
TERM *poly1=NULL,*poly2=NULL,*res_poly=NULL;
TERM *tail1=NULL,*tail2=NULL,*tail3=NULL;
TERM *createNode(int c,int e)
{
TERM *ptr=(TERM*)malloc(sizeof(TERM));
if(ptr!=NULL)
{
ptr->coeff=c;
ptr->exp=e;
ptr->next=NULL;
}
return ptr;
}
void insert_term(int c,int e,TERM **poly)
{
TERM *newNode=createNode(c,e);
if (*poly == NULL)
{
*poly = newNode;
}
else
{
TERM* temp = *poly;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
void displayPolynomial(TERM *poly)
{
if(poly==NULL)
{
printf("\nPolynomial does not consist of any terms.\n");
}
else
{
while(poly!=NULL)
{
printf("%dx^%d",poly->coeff,poly->exp);
poly=poly->next;
if(poly!=NULL)
printf("+");
}
}
}
void addPolynomials(TERM *p1,TERM *p2)
{
while(p1!=NULL && p2!=NULL)
{
if(p1->exp > p2->exp)
{
insert_term(p1->coeff,p1->exp,&res_poly);
p1=p1->next;
}
else if(p1->exp < p2->exp)
{
insert_term(p2->coeff,p2->exp,&res_poly);
p2=p2->next;
}
else
{
int c_sum=p1->coeff+p2->coeff;
if(c_sum!=0)
insert_term(c_sum,p1->exp,&res_poly);
p1=p1->next;
p2=p2->next;
}
}
while(p1!=NULL)
{
insert_term(p1->coeff,p1->exp,&res_poly);
p1=p1->next;
}
while(p2!=NULL)
{
insert_term(p2->coeff,p2->exp,&res_poly);
p2=p2->next;
}
}
void readPolynomial(TERM **poly)
{
int n,c,e;
printf("\nEnter number of terms in the polynomial equation\n");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\nEnter coefficient and exponent of term %d\n",i);
scanf("%d%d",&c,&e);
insert_term(c,e,poly);
}
}
int main()
{
printf("Enter the first polynomial:\n");
readPolynomial(&poly1);
printf("Enter the second polynomial:\n");
readPolynomial(&poly2);
printf("\nFirst Polynomial: ");
displayPolynomial(poly1);
printf("\nSecond Polynomial: ");
displayPolynomial(poly2);
addPolynomials(poly1, poly2);
printf("\nSum of Polynomials: ");
displayPolynomial(res_poly);
}
[Link] a program to Implement Singly Linked List with following operations
a) Sort the linked list.
b) Reverse the linked list.
c) Concatenation of two linked lists
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node
{
int data;
struct Node* next;
};
// 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;
}
// Display list
void display(struct Node* head)
{
if (head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// a) Sort the linked list using Bubble Sort
void sortList(struct Node* head)
{
if (head == NULL) return;
struct Node *i, *j;
int temp;
for (i = head; i->next != NULL; i = i->next) {
for (j = i->next; j != NULL; j = j->next) {
if (i->data > j->data) {
temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}
printf("List sorted successfully.\n");
}
// b) Reverse the linked list
void reverseList(struct Node** head)
{
struct Node *prev = NULL, *curr = *head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
printf("List reversed successfully.\n");
}
// c) Concatenate two linked lists
struct Node* concatenate(struct Node* head1, struct Node* head2)
{
if (head1 == NULL) return head2;
if (head2 == NULL) return head1;
struct Node* temp = head1;
while (temp->next != NULL)
temp = temp->next;
temp->next = head2;
return head1;
}
// MAIN MENU
int main()
{
struct Node *list1 = NULL, *list2 = NULL, *result = NULL;
int choice, val;
while (1) {
printf("\n----- MENU -----\n");
printf("1. Insert into List 1\n");
printf("2. Insert into List 2\n");
printf("3. Display List 1\n");
printf("4. Display List 2\n");
printf("5. Sort List 1\n");
printf("6. Reverse List 1\n");
printf("7. Concatenate List 1 and List 2\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value: ");
scanf("%d", &val);
insertEnd(&list1, val);
break;
case 2:
printf("Enter value: ");
scanf("%d", &val);
insertEnd(&list2, val);
break;
case 3:
printf("List 1: ");
display(list1);
break;
case 4:
printf("List 2: ");
display(list2);
break;
case 5:
sortList(list1);
break;
case 6:
reverseList(&list1);
break;
case 7:
result = concatenate(list1, list2);
printf("After concatenation: ");
display(result);
break;
case 8:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
[Link] a program to Implement doubly linked list with primitive operations.
a) Create a doubly linked list.
b) Insert a new node to the left of the node.
c) Delete the node based on a specific value
d) Display the contents of the list
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
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));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Insertion at beginning
void insertAtBeginning(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Deletion of node with given value
void deleteByValue(int value) {
struct Node* temp = head;
while (temp != NULL && temp->data != value)
temp = temp->next;
if (temp == NULL) {
printf("Value %d not found in list.\n", value);
return;
}
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);
}
// Traversal
void display() {
struct Node* temp = head;
if (temp == NULL) {
printf("List is empty.\n");
return;
}
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main Menu
int main() {
int choice, value, pos;
do {
printf("\nDoubly Linked List Operations:\n");
printf("1. Insert at Beginning\n");
printf("2. Delete by Value\n");
printf("3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtBeginning(value);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteByValue(value);
break;
case 3:
display();
break;
case 4:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice! Try again.\n");
}
} while(choice != 4);
return 0;
}
[Link] a program to convert a given valid parenthesized infix arithmetic expression to
postfix expression. The expression consists of single character operands and the binary
operators + (plus), - (minus), *(multiply) and / (divide)
#include <stdio.h>
#include <ctype.h> // for isalnum()
#include <string.h> // for strlen()
#define MAX 100
// Stack implementation
char stack[MAX];
int top = -1;
void push(char x) {
stack[++top] = x;
}
char pop() {
if (top == -1)
return -1;
return stack[top--];
}
// Function to define precedence
int precedence(char x) {
if (x == '(')
return 0;
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/')
return 2;
return -1;
}
int main() {
char infix[MAX], postfix[MAX];
int i, j = 0;
char ch;
printf("Enter a valid parenthesized infix expression: ");
scanf("%s", infix);
for (i = 0; i < strlen(infix); i++) {
ch = infix[i];
// If operand, add to postfix
if (isalnum(ch)) {
postfix[j++] = ch;
}
// If opening bracket, push to stack
else if (ch == '(') {
push(ch);
}
// If closing bracket, pop until '('
else if (ch == ')') {
while (stack[top] != '(') {
postfix[j++] = pop();
}
pop(); // remove '('
}
// If operator
else {
while (top != -1 && precedence(stack[top]) >= precedence(ch)) {
postfix[j++] = pop();
}
push(ch);
}
}
// Pop remaining operators
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; // Null-terminate result
printf("Postfix Expression: %s\n", postfix);
return 0;
}
6. Write a C program to check if parentheses (and other types of brackets) are balanced
in an expression.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
// Stack implementation
char stack[MAX];
int top = -1;
void push(char c) {
stack[++top] = c;
}
char pop() {
if (top == -1)
return '\0';
return stack[top--];
}
// Function to check matching brackets
int isMatchingPair(char opening, char closing) {
if (opening == '(' && closing == ')') return 1;
if (opening == '{' && closing == '}') return 1;
if (opening == '[' && closing == ']') return 1;
return 0;
}
int isBalanced(char *exp) {
int i;
char popped;
for (i = 0; exp[i] != '\0'; i++) {
// If opening brackets, push into stack
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
push(exp[i]);
}
// If closing brackets, check stack
else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
if (top == -1) // stack empty
return 0;
popped = pop();
if (!isMatchingPair(popped, exp[i]))
return 0;
}
}
// At end, stack must be empty
if (top == -1)
return 1;
else
return 0;
}
int main() {
char expression[MAX];
printf("Enter an expression: ");
scanf("%s", expression);
if (isBalanced(expression))
printf("The expression is BALANCED.\n");
else
printf("The expression is NOT balanced.\n");
return 0;
}