Set A
a) Write a menu driven program for the following operations.
i. Insert an element in a linked list in a particular position
ii. Search an element in a linked list.
iii. Delete a particular element from a linked list.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
// Insert at a particular position
void insert()
{
struct node *newnode, *temp;
int data, pos, i;
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &data);
newnode->data = data;
newnode->next = NULL;
printf("Enter position: ");
scanf("%d", &pos);
if (pos == 1)
{
newnode->next = head;
head = newnode;
return;
}
temp = head;
for (i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL)
{
printf("Invalid Position\n");
free(newnode);
return;
}
newnode->next = temp->next;
temp->next = newnode;
printf("Node Inserted Successfully.\n");
}
// Search an element
void search()
{
struct node *temp = head;
int key, pos = 1;
printf("Enter element to search: ");
scanf("%d", &key);
while (temp != NULL)
{
if (temp->data == key)
{
printf("Element found at position %d\n", pos);
return;
}
temp = temp->next;
pos++;
}
printf("Element not found.\n");
}
// Delete a particular element
void deleteNode()
{
struct node *temp = head, *prev = NULL;
int key;
printf("Enter element to delete: ");
scanf("%d", &key);
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL)
{
printf("Element not found.\n");
return;
}
if (prev == NULL)
head = temp->next;
else
prev->next = temp->next;
free(temp);
printf("Element deleted successfully.\n");
}
// Display linked list
void display()
{
struct node *temp = head;
if (head == NULL)
{
printf("List is Empty.\n");
return;
}
printf("Linked List: ");
while (temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
int choice;
while (1)
{
printf("\n----- MENU -----\n");
printf("1. Insert at Particular Position\n");
printf("2. Search Element\n");
printf("3. Delete Element\n");
printf("4. Display List\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
search();
break;
case 3:
deleteNode();
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid Choice!\n");
}
}
return 0;
}
b) Write a menu driven program for the following operations.
i. Reverse a linked list and display it.
ii. Accept an element from user and Concatenate it with a created link list.
iii. Merge two linked list and display it.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head1 = NULL, *head2 = NULL;
// Create a linked list
void create(struct node **head)
{
struct node *newnode, *temp;
int n, i;
printf("Enter number of nodes: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(*head == NULL)
{
*head = newnode;
}
else
{
temp = *head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
}
}
// Display linked list
void display(struct node *head)
{
while(head != NULL)
{
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Reverse linked list
void reverse()
{
struct node *prev = NULL, *curr = head1, *next;
while(curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head1 = prev;
printf("Reversed Linked List:\n");
display(head1);
}
// Concatenate one element
void concatenate()
{
struct node *newnode, *temp;
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter element: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(head1 == NULL)
{
head1 = newnode;
}
else
{
temp = head1;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
printf("After Concatenation:\n");
display(head1);
}
// Merge two linked lists
void merge()
{
struct node *temp;
if(head1 == NULL)
{
head1 = head2;
}
else
{
temp = head1;
while(temp->next != NULL)
temp = temp->next;
temp->next = head2;
}
printf("Merged Linked List:\n");
display(head1);
}
int main()
{
int ch;
printf("Create First Linked List\n");
create(&head1);
while(1)
{
printf("\n----- MENU -----\n");
printf("1. Reverse Linked List\n");
printf("2. Concatenate Element\n");
printf("3. Merge Two Linked Lists\n");
printf("4. Display First List\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
reverse();
break;
case 2:
concatenate();
break;
case 3:
printf("Create Second Linked List\n");
create(&head2);
merge();
break;
case 4:
display(head1);
break;
case 5:
exit(0);
default:
printf("Invalid Choice\n");
}
}
return 0;
}
Set B
Implement a list library (doublylist.h) for a doubly linked list with Append, Insert, Search and Delete operations.
a) Write a menu driven program for the following operations.
i. Insert an element in a linked list in a particular position
ii. Search an element in a linked list.
iii. Delete a particular element from a linked list.
1. Header File: doublylist.h
2. Main Program: main.c
b) Write a menu driven program for the following operations.
i. Reverse a linked list and display it.
ii. Accept an element from user and Concatenate it with a created link list.
iii. Merge two linked list and display it.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head1 = NULL, *head2 = NULL;
// Create a linked list
void create(struct node **head)
{
struct node *newnode, *temp;
int n, i;
printf("Enter number of nodes: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(*head == NULL)
{
*head = newnode;
}
else
{
temp = *head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
}
}
// Display linked list
void display(struct node *head)
{
if(head == NULL)
{
printf("List is Empty\n");
return;
}
while(head != NULL)
{
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Reverse linked list
void reverse()
{
struct node *prev = NULL, *curr = head1, *next;
while(curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head1 = prev;
printf("Reversed Linked List:\n");
display(head1);
}
// Concatenate an element
void concatenate()
{
struct node *newnode, *temp;
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter element to concatenate: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(head1 == NULL)
{
head1 = newnode;
}
else
{
temp = head1;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
printf("After Concatenation:\n");
display(head1);
}
// Merge two linked lists
void merge()
{
struct node *temp;
printf("Create Second Linked List\n");
create(&head2);
if(head1 == NULL)
{
head1 = head2;
}
else
{
temp = head1;
while(temp->next != NULL)
temp = temp->next;
temp->next = head2;
}
printf("Merged Linked List:\n");
display(head1);
}
int main()
{
int ch;
printf("Create First Linked List\n");
create(&head1);
while(1)
{
printf("\n----- MENU -----\n");
printf("1. Reverse Linked List\n");
printf("2. Concatenate Element\n");
printf("3. Merge Two Linked Lists\n");
printf("4. Display Linked List\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
reverse();
break;
case 2:
concatenate();
break;
case 3:
merge();
break;
case 4:
display(head1);
break;
case 5:
exit(0);
default:
printf("Invalid Choice\n");
}
}
return 0;
}
c) Write a program that adds two single variable polynomials. Each polynomial should be
represented as a list with linked list implementation
#include <stdio.h>
#include <stdlib.h>
struct node
{
int coeff;
int exp;
struct node *next;
};
// Create polynomial
void create(struct node **head)
{
struct node *newnode, *temp;
int n, i;
printf("Enter number of terms: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter coefficient and exponent: ");
scanf("%d%d", &newnode->coeff, &newnode->exp);
newnode->next = NULL;
if(*head == NULL)
{
*head = newnode;
}
else
{
temp = *head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newnode;
}
}
}
// Display polynomial
void display(struct node *head)
{
while(head != NULL)
{
printf("%dx^%d", head->coeff, head->exp);
if(head->next != NULL)
printf(" + ");
head = head->next;
}
printf("\n");
}
// Add two polynomials
struct node* add(struct node *p1, struct node *p2)
{
struct node *result = NULL, *temp = NULL, *newnode;
while(p1 != NULL && p2 != NULL)
{
newnode = (struct node *)malloc(sizeof(struct node));
newnode->next = NULL;
if(p1->exp == p2->exp)
{
newnode->coeff = p1->coeff + p2->coeff;
newnode->exp = p1->exp;
p1 = p1->next;
p2 = p2->next;
}
else if(p1->exp > p2->exp)
{
newnode->coeff = p1->coeff;
newnode->exp = p1->exp;
p1 = p1->next;
}
else
{
newnode->coeff = p2->coeff;
newnode->exp = p2->exp;
p2 = p2->next;
}
if(result == NULL)
{
result = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
while(p1 != NULL)
{
newnode = (struct node *)malloc(sizeof(struct node));
newnode->coeff = p1->coeff;
newnode->exp = p1->exp;
newnode->next = NULL;
temp->next = newnode;
temp = newnode;
p1 = p1->next;
}
while(p2 != NULL)
{
newnode = (struct node *)malloc(sizeof(struct node));
newnode->coeff = p2->coeff;
newnode->exp = p2->exp;
newnode->next = NULL;
temp->next = newnode;
temp = newnode;
p2 = p2->next;
}
return result;
}
int main()
{
struct node *poly1 = NULL, *poly2 = NULL, *result = NULL;
printf("Enter First Polynomial (Descending order of exponents)\n");
create(&poly1);
printf("\nEnter Second Polynomial (Descending order of exponents)\n");
create(&poly2);
printf("\nFirst Polynomial:\n");
display(poly1);
printf("Second Polynomial:\n");
display(poly2);
result = add(poly1, poly2);
printf("Resultant Polynomial:\n");
display(result);
return 0;
}