Exercise 1: Array Manipulation

i) Write a program to reverse an array.

#include <stdio.h>
int main()
{
int arr[100], n, i, 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]);
}
for(i = 0; i < n / 2; i++)
{
temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
printf("Reversed array:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
Enter number of elements: 5
Enter 5 elements:
1 2 3 4 5
Reversed array:
5 4 3 2 1

ii)C Programs to implement the Searching Techniques – Linear & Binary Search
Linear search
Algorithm:
1. Start
2. Read the number of elements n
3. Read the element to be searched Key
4. Read the array elements A[ ]
5. set i=0
6. Compare A[i] with key
7. if A[i]==key , display element found at position i and stop
8. Else increase i=i+1
9. Repeat steps 6-8 until i<n
10. if the element is not found, display element not found
11. Stop
Program :
#include <stdio.h>
int main( )
{
int arr[100], n, i, key, found = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++)
{
 scanf("%d", &arr[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
for(i = 0; i < n; i++)
{
if(arr[i] == key)
{
printf("Element found at position %d", i );
found = 1;
break;
}
}
if(found == 0)
{
printf("Element not found");
}
return 0;
}
Output1:Enter number of elements 5
Enter 5 elements 10 40 50 20 30
Enter Key 50
Element found at position 2
Output 2:Enter number of elements 5
Enter 5 elements 10 40 50 20 30
Enter Key 60
Element not found
Binary search
Algorithm
1. start
2. read the number of elements
3. read the sorted array A[ ]
4. read the element to be searched key
5. set low=0 and high-n-1
6. Repeat while low<=high
7. find mid=(low+high)/2
[Link] A[mid]==key, display element found at position mid and stop
[Link] key<A[mid] set high=mid-1
10. Else set low=mid+1
11. if the element is not found , display element not found
12. stop
Program
#include <stdio.h>
int binarySearch(int arr[], int n, int key)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
 }
return -1;
}
int main()
{
int n, key,arr[100];
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter sorted elements:\n");
for(int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
int result = binarySearch(arr, n, key);
if(result == -1)
printf("Element not found");
else
printf("Element found at index %d", result);
return 0;
}
Output:
Enter number of elements: 5
Enter sorted elements:
10 20 30 40 50
Enter element to search: 40
Element found at index 3
iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort

Bubblesort
Algorithm
[Link]
[Link] the number of elements n
[Link] the array A[ ]
4. for i=0 to n-1
5. For j=0 to n-i-1
6. Compare A[j] and A[j+1]
[Link] A[j]>A[j+1] swap them
8. repeat until all passes are completed
9. stop
Program
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
for(i = 0; i < n - 1; i++) {
for(j = 0; j < n - i - 1; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void display(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
bubbleSort(arr, n);
printf("Sorted array:\n");
display(arr, n);
return 0;
}
Output:
Enter number of elements: 5
Enter elements:
40 50 20 10 70
Sorted array:10 20 40 50 70
Selectionsort
Algorithm
1. start
2. read the number of elements n
3. read the array A[]
4. for i=0 to n-1
5. set min=1
6. for j=i+1 to n-1
7. if A[j]<A[min] set min=j
8. After the inner loop swap A[i] and A[min]
9. repeat until the array is sorted
10. Stop
Program
#include <stdio.h>
void selectionSort(int arr[], int n)
{
int i, j, minIndex, temp;
for(i = 0; i < n - 1; i++)
{
minIndex = i;
for(j = i + 1; j < n; j++)
{
if(arr[j] < arr[minIndex])
{
minIndex = j;
}
}
temp = arr[i];
 arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
void display(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
selectionSort(arr, n);
printf("Sorted array:\n");
display(arr, n);
return 0;
}
Program
#include <stdio.h>
void insertionSort(int arr[], int n)
{
int i, key, j;
for(i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void display(int arr[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main( )
{
int arr[100], n, i;
 printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
insertionSort(arr, n);
printf("Sorted array:\n");
display(arr, n);
return 0;
}
Output:
Enter number of elements: 5
Enter elements:
80 30 10 20 15
Sorted array:
10 15 20 30 80
Exercise 2: Linked List Implementation
i) Implement a singly linked list and perform insertion and deletion operations.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL, *temp, *newnode;
void create()
{
int choice;
do {
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(head == NULL)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
printf("Add another node? (1/0): ");
 scanf("%d", &choice);
} while(choice == 1);
}

void display()
{
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");
}
void insert_begin()
{
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
newnode->next = head;
head = newnode;
}
void insert_end()
{
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;
}
}
void insert_pos()
{
int pos;
printf("Enter position: ");
scanf("%d", &pos);
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
temp = head;
for(int i = 1; i < pos-1; i++)
{
 temp = temp->next;
}
newnode->next = temp->next;
temp->next = newnode;
}
void delete_begin()
{
if(head == NULL)
{
printf("List empty\n");
return;
}
temp = head;
head = head->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}
void delete_end()
{
struct node *temp;
if(head == NULL)
printf("List is empty\n");
else
if(head->next == NULL)
{
free(head);
head = NULL;
}
 else
{
temp = head;
while(temp->next->next != NULL)
{
temp = temp->next;
}
free(temp->next);
temp->next = NULL;

}
}
void delete_pos()
{
int pos;
struct node *prev;
printf("Enter position: ");
scanf("%d", &pos);

temp = head;
for(int i = 1; i < pos; i++) {
prev = temp;
temp = temp->next;
}
prev->next = temp->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}
int main()
{
int choice;
do {
printf("\n--- MENU ---\n");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link] at Beginning\n");
printf("[Link] at End\n");
printf("[Link] at Position\n");
printf("[Link] from Beginning\n");
printf("[Link] from End\n");
printf("[Link] from Position\n");
printf("[Link]\n");
printf("Enter choice: ");
scanf("%d", &choice);

switch(choice)
{
case 1: create(); break;
case 2: display(); break;
case 3: insert_begin(); break;
case 4: insert_end(); break;
case 5: insert_pos(); break;
case 6: delete_begin(); break;
case 7: delete_end(); break;
case 8: delete_pos(); break;
case 9: printf("Exiting...\n"); break;
 default: printf("Invalid choice\n");
}
} while(choice != 9);
return 0;
}

Output

--- MENU ---

[Link]
[Link]
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 4
Enter data: 25

--- MENU ---

[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 2
Linked List: 5 -> 10 -> 20 -> 25 -> NULL

--- MENU ---

[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 5
Enter position: 3
Enter data: 15

--- MENU ---

[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 2
Linked List: 5 -> 10 -> 15 -> 20 -> 25 -> NULL

--- MENU ---

[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 6
Deleted: 5

--- MENU ---

[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice: 2
Linked List: 10 -> 15 -> 20 -> 25 -> NULL
--- MENU ---
[Link]
[Link]
[Link] at Beginning
[Link] at End
[Link] at Position
[Link] from Beginning
[Link] from End
[Link] from Position
[Link]
Enter choice:
 ii) Develop a program to reverse a linked list iteratively and recursively.
Iterative Method
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
int main()
{
struct node *head=NULL,*temp,*newnode;
int choice=1;
while(choice)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter Data: ");
scanf("%d",&newnode->data);
newnode->next=NULL;
if(head==NULL)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
}
 printf("Add another node (1/0): ");
scanf("%d",&choice);
}
printf("\nOriginal List:");
temp=head;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
struct node *prev=NULL,*current=head,*next;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
head=prev;
printf("\nReversed List:");
temp=head;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
 return 0;
}

Output: Enter Data: 10

Add another node (1/0): 1
Enter Data: 20
Add another node (1/0): 1
Enter Data: 30
Add another node (1/0): 0
Original List: 10->20->30->NULL
Reversed List:30->20->10->NULL

Recursive Method
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node* reverse(struct node *head)
{
if(head == NULL || head->next == NULL)
return head;
struct node *temp = reverse(head->next);
head->next->next = head;
head->next = NULL;
 return temp;
}
int main()
{
struct node *head=NULL,*temp,*newnode;
int choice=1;
while(choice)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter Data: ");
scanf("%d",&newnode->data);
newnode->next=NULL;
if(head==NULL)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
}
printf("Add another node (1/0): ");
scanf("%d",&choice);
}
printf("\nOriginal List: ");
temp=head;
while(temp!=NULL)
{
 printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
// Reverse using recursion
head = reverse(head);
printf("\nReversed List: ");
temp=head;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
return 0;
}
Output:
Enter Data: 10
Add another node (1/0): 1
Enter Data: 20
Add another node (1/0): 1
Enter Data: 30
Add another node (1/0): 1
Enter Data: 40
Add another node (1/0): 0
Original List: 10->20->30->40->NULL
Reversed List: 40->30->20->10->NULL
iii) Solve problems involving linked list traversal and manipulation.
#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));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void traverse(struct Node* head)

{
 return NULL;
}
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}

struct Node* deleteEnd(struct Node* head)

{
if (head == NULL) {
printf("List is empty\n");
return NULL;
}
if (head->next == NULL) {
free(head);
return NULL;
}

struct Node* temp = head;

while (temp->next->next != NULL)
temp = temp->next;

free(temp->next);
temp->next = NULL;
return head;
}
void search(struct Node* head, int key)
{
struct Node* temp = head;
int pos = 1;

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");
}
struct Node* reverse(struct Node* head)
{
struct Node *prev = NULL, *curr = head, *next;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
int main()
{
struct Node* head = NULL;
int choice, data;
while (1) {
printf("\n--- LINKED LIST MENU ---\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Delete from Beginning\n");
printf("4. Delete from End\n");
printf("5. Traverse\n");
printf("6. Search\n");
printf("7. Reverse\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data: ");
scanf("%d", &data);
head = insertBegin(head, data);
break;
case 2:
printf("Enter data: ");
scanf("%d", &data);
head = insertEnd(head, data);
break;
 case 3:
head = deleteBegin(head);
break;

case 4:
head = deleteEnd(head);
break;
case 5:
traverse(head);
break;
case 6:
printf("Enter element to search: ");
scanf("%d", &data);
search(head, data);
break;
case 7:
head = reverse(head);
printf("List reversed\n");
break;
case 8:
exit(0);
default:
printf("Invalid choice\n");
}
}
}
Output
--- LINKED LIST MENU ---
1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 1
Enter data: 10

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 2
Enter data: 20

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 1
Enter data: 5

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 5
5 -> 10 -> 20 -> NULL

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 2
Enter data: 25

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 5
5 -> 10 -> 20 -> 25 -> NULL

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Reverse
8. Exit
Enter your choice: 6
Enter element to search: 25
Element found at position 4

--- LINKED LIST MENU ---

1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
Exercise 3: Linked List Applications
i) Create a program to detect and remove duplicates from a linked list.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node* createList()
{
struct node *head = NULL, *temp, *newnode;
int choice = 1;
while(choice)
{
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d", &newnode->data);
newnode->next = NULL;
if(head == NULL)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
 printf("Continue? (1/0): ");
scanf("%d", &choice);
}
return head;
}
void display(struct node *head)
{
struct node *temp = head;
while(temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
struct node* removeDuplicates(struct node *head)
{
struct node *ptr1, *ptr2, *dup;
ptr1 = head;
while(ptr1 != NULL)
{
ptr2 = ptr1;
while(ptr2->next != NULL)
{
if(ptr1->data == ptr2->next->data)
{
dup = ptr2->next;
ptr2->next = ptr2->next->next;
free(dup);
 }
else
{
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
return head;
}
int main()
{
struct node *head;
head = createList();
printf("\nList before removing duplicates:\n");
display(head);
head = removeDuplicates(head);
printf("\nList after removing duplicates:\n");
display(head);
return 0;
}
Output:
Enter data: 10
Continue? (1/0): 1
Enter data: 20
Continue? (1/0): 1
Enter data: 30
Continue? (1/0): 1
Enter data: 20
Continue? (1/0): 1
Enter data: 40
Continue? (1/0): 1
Enter data: 10
Continue? (1/0): 1
Enter data: 50
Continue? (1/0): 0
List before removing duplicates:
10 -> 20 -> 30 -> 20 -> 40 -> 10 -> 50 -> NULL

List after removing duplicates:

10 -> 20 -> 30 -> 40 -> 50 -> NULL

ii) Implement a linked list to represent polynomials and perform addition.

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

struct Node* createNode(int coeff, int exp)

{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = coeff;
 newNode->exp = exp;
newNode->next = NULL;
return newNode;
}

struct Node* insert(struct Node* head, int coeff, int exp)

{
struct Node* newNode = createNode(coeff, exp);

if (head == NULL || head->exp < exp) {

newNode->next = head;
return newNode;
}

struct Node* temp = head;

while (temp->next != NULL && temp->next->exp > exp)
temp = temp->next;

newNode->next = temp->next;
temp->next = newNode;

return head;
}

void display(struct Node* head)

{
struct Node* temp = head;
while (temp != NULL) {
 printf("%dx^%d", temp->coeff, temp->exp);
if (temp->next != NULL)
printf(" + ");
temp = temp->next;
}
printf("\n");
}

struct Node* addPoly(struct Node* p1, struct Node* p2)

{
struct Node* result = NULL;

while (p1 != NULL && p2 != NULL) {

if (p1->exp == p2->exp) {
result = insert(result, p1->coeff + p2->coeff, p1->exp);
p1 = p1->next;
p2 = p2->next;
}
else if (p1->exp > p2->exp) {
result = insert(result, p1->coeff, p1->exp);
p1 = p1->next;
}
else {
result = insert(result, p2->coeff, p2->exp);
p2 = p2->next;
}
}
 while (p1 != NULL) {
result = insert(result, p1->coeff, p1->exp);
p1 = p1->next;
}

while (p2 != NULL) {

result = insert(result, p2->coeff, p2->exp);
p2 = p2->next;
}

return result;
}

int main()
{
struct Node *p1 = NULL, *p2 = NULL, *result = NULL;
int n, coeff, exp, i;

printf("Enter number of terms for first polynomial: ");

scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Enter coeff and exponent: ");
scanf("%d %d", &coeff, &exp);
p1 = insert(p1, coeff, exp);
}

printf("Enter number of terms for second polynomial: ");

scanf("%d", &n);
 for (i = 0; i < n; i++) {
printf("Enter coeff and exponent: ");
scanf("%d %d", &coeff, &exp);
p2 = insert(p2, coeff, exp);
}
printf("\nFirst Polynomial: ");
display(p1);
printf("Second Polynomial: ");
display(p2);
result = addPoly(p1, p2);
printf("Resultant Polynomial: ");
display(result);
return 0;
}
Output:
Enter number of terms for first polynomial: 3
Enter coeff and exponent: 5 3
Enter coeff and exponent: 4 2
Enter coeff and exponent: 6 0
Enter number of terms for second polynomial: 2
Enter coeff and exponent: 6 4
Enter coeff and exponent: 2 0

First Polynomial: 5x^3 + 4x^2 + 6x^0

Second Polynomial: 6x^4 + 2x^0
Resultant Polynomial: 6x^4 + 5x^3 + 4x^2 + 8x^0
iii)Implement a double-ended queue (deque) with essential operations.

Exercise 4: Double Linked List Implementation

i) Implement a doubly linked list and perform various operations to understand its
properties and applications.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node *head = NULL;
void insertBeginning()
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 struct Node *temp = head;
for(i=1;i<pos - 1 && temp != NULL;i++)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Position out of range\n");
free(newNode);
return;
}
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL)
temp->next->prev = newNode;
temp->next = newNode;
}
void deleteBeginning()
{
if (head == NULL)
{
printf("List is empty\n");
return;
}
struct Node* temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
free(temp);
}
void deleteEnd()
{
if (head == NULL)
{
printf("List is empty\n");
return;
}
struct Node* temp = head;
if (temp->next == NULL)
{
free(temp);
head = NULL;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->prev->next = NULL;
free(temp);
}
void deletePosition()
{
if (head == NULL) {
printf("List is empty\n");
return;
}
int pos, i = 1;
printf("Enter position to delete: ");
scanf("%d", &pos);
struct Node* temp = head;
if (pos == 1)
 {
head = head->next;
if (head != NULL)
head->prev = NULL;
free(temp);
return;
}
for(i=1;i<pos&&temp!=NULL;i++)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Position out of range\n");
return;
}

if (temp->next != NULL)
temp->next->prev = temp->prev;
if (temp->prev != NULL)
temp->prev->next = temp->next;
free(temp);
}

void display()
{
struct Node* temp = head;
if (temp == NULL) {
printf("List is empty\n");
 return;
}
while (temp != NULL)
{
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
int choice;

while (1)
{
printf("\n--- Doubly Linked List ---\n");
printf("1. Insert Beginning\n");
printf("2. Insert End\n");
printf("3. Insert Position\n");
printf("4. Delete Beginning\n");
printf("5. Delete End\n");
printf("6. Delete Position\n");
printf("7. Display\n");
printf("8. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: insertBeginning(); break;
case 2: insertEnd(); break;
 case 3: insertPosition(); break;
case 4: deleteBeginning(); break;
case 5: deleteEnd(); break;
case 6: deletePosition(); break;
case 7: display(); break;
case 8: exit(0);
default: printf("Invalid choice\n");
}
}
return 0;
}

Output:
--- Doubly Linked List ---
1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice: 1
Enter Data10

--- Doubly Linked List ---

1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice: 2
Enter Data20

--- Doubly Linked List ---

1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice: 3
Enter Data15
enter Position2

--- Doubly Linked List ---

1. Insert Beginning
2. Insert End
--- Doubly Linked List ---
1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice: 6
Enter position to delete: 3

--- Doubly Linked List ---

1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice: 7
5 <-> 10 <-> 20 <-> NULL

--- Doubly Linked List ---

1. Insert Beginning
2. Insert End
3. Insert Position
4. Delete Beginning
5. Delete End
6. Delete Position
7. Display
8. Exit
Enter choice:

ii) Implement a circular linked list and perform insertion, deletion, and traversal.

#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
void display()
{
struct node *temp;

if(head == NULL) {
printf("List is empty\n");
return;
}
temp = head;
while(temp->next != head) {
printf("%d -> ", temp->data);
 temp = temp->next;
}
printf("%d -> HEAD\n", temp->data);
}

void insertBegin( )
{
struct node *newnode, *temp;
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter Data");
scanf("%d",&newnode->data);
if(head == NULL) {
head = newnode;
newnode->next = head;
} else {
temp = head;
while(temp->next != head)
temp = temp->next;

newnode->next = head;
temp->next = newnode;
head = newnode;
}
}
void insertEnd( )
{
struct node *newnode, *temp;
 newnode = (struct node*)malloc(sizeof(struct node));

printf("Enter Data");
scanf("%d",&newnode->data);
if(head == NULL) {
head = newnode;
newnode->next = head;
} else {
temp = head;
while(temp->next != head)
temp = temp->next;

temp->next = newnode;
newnode->next = head;
}
}
void insertPos( )
{
struct node *newnode, *temp;
int i = 1,pos;
newnode = (struct node*)malloc(sizeof(struct node));
printf("Enter Data");
scanf("%d",&newnode->data);
printf("Enter position");
scanf("%d",&pos);
if(pos == 1) {
insertBegin();
return;
 }
temp = head;
for(i=1;i<pos-1 && temp->next != head;i++)
{
temp = temp->next;

}
newnode->next = temp->next;
temp->next = newnode;
}
void deleteBegin()
{
struct node *temp, *last;

if(head == NULL)
{
printf("List empty\n");
return;
}
temp = head;
if(head->next == head) {
head = NULL;
free(temp);
} else {
last = head;
while(last->next != head)
last = last->next;
 head = head->next;
last->next = head;
free(temp);
}
}

void deleteEnd()
{
struct node *temp, *prev;

if(head == NULL)
{
printf("List empty\n");
return;
}
if(head->next == head) {
free(head);
head = NULL;
} else {
temp = head;
while(temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
free(temp);
}
}
void deletePos( )
{
struct node *temp, *prev;
int i = 1,pos;
printf("Enter position");
scanf("%d",&pos);
if(head == NULL) {
printf("List empty\n");
return;
}
if(pos == 1) {
deleteBegin();
return;
}
temp = head;
for(i=1;i<pos-1 && temp->next != head;i++)
{
prev = temp;
temp = temp->next;

}
prev->next = temp->next;
free(temp);
}
int main()
{
int choice;
while(1) {
printf("\[Link] Begin\[Link] End\[Link] Position\n");
printf("[Link] Begin\[Link] End\[Link] Position\n");
printf("[Link]\[Link]\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
insertBegin();
break;
case 2:
Enter Data 20

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 1
Enter Data 5

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 7
5 -> 10 -> 20 -> HEAD

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 3
Enter Data 15
Enter position 3

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 7
5 -> 10 -> 15 -> 20 -> HEAD

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 2
Enter Data 25

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 7
5 -> 10 -> 15 -> 20 -> 25 -> HEAD

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 4
[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 7
10 -> 15 -> 20 -> 25 -> HEAD

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 5

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]
Enter choice: 7
10 -> 15 -> 20 -> HEAD

[Link] Begin
[Link] End
[Link] Position
[Link] Begin
[Link] End
[Link] Position
[Link]
[Link]