//C Program to Implement Singly Linked List using Dynamic Memory Allocation

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
// Node Declaration
struct node
{
 int data;
 struct node *next;
};
// Function prototypes
struct node *create_node(int x);
void insert_first();
void insert_last();
void insert_pos();
void delete_pos();
void search();
void traverse();
// Global variable to store the head of the linked list
struct node *start = NULL;
// Main function
int main()
{
 int ch;
 char ans;
 do
 {
 // Display menu
 printf("\n1.Insert at the beginning");
 printf("\n2.Insert at the end");
 printf("\n3.Insert at the middle");
 printf("\n4.Delete ");
 printf("\n5.Search ");
 printf("\n6.Traverse");
 printf("\n7.Exit\n");
 printf("\nEnter your choice: ");
 scanf("%d", &ch);
 // Switch statement to perform the selected operation
 switch (ch)
 {
 case 1:
 insert_first();
 break;
 case 2:
 insert_last();
 break;
 case 3:
 insert_pos();
 break;
 case 4:
 delete_pos();
 break;
 case 5:
 search();
 break;
 case 6:
 traverse();
 break;
 case 7:
 exit(0);
 default:
 printf("\n...Invalid Choice...\n");
 break;
 }
 // Ask the user if they want to continue
 printf("\nDo you want to continue? (y/n): ");
 scanf(" %c", &ans);
 } while (ans == 'y' || ans == 'Y');
 return 0;
}
// Function to create a new node with the given data
struct node *create_node(int x)
{
 struct node *newnode;
 newnode = (struct node *)malloc(sizeof(struct node));
 if (newnode == NULL)
 {
 printf("\nMemory was not allocated");
 return NULL;
 }
 else
 {
 newnode->data = x;
 newnode->next = NULL;
 return newnode;
 }
}
// Function to insert a new node at the beginning of the linked list
void insert_first()
{
 struct node *newnode;
 int x;
 printf("\nEnter the data for the node: ");
 scanf("%d", &x);
 newnode = create_node(x);
 newnode->next = start;
 start = newnode;
}
// Function to insert a new node at the end of the linked list
void insert_last()
{
 int x;
 struct node *ptr, *newnode;
 printf("\nEnter the data for the Node: ");
 scanf("%d", &x);
 newnode = create_node(x);
 if (start == NULL)
 {
 start = newnode;
 }
 else
 {
 ptr = start;
 while (ptr->next != NULL)
 ptr = ptr->next;
 ptr->next = newnode;
 }
}
// Function to insert a new node at a specified position in the linked list
void insert_pos()
{
 int pos, x, i;
 struct node *ptr, *newnode;
 printf("\nEnter the data for the Node: ");
 scanf("%d", &x);
 printf("\nEnter the position: ");
 scanf("%d", &pos);
 ptr = start;
 if (pos == 1)
 {
 insert_first(); // Call the insert_first function for position 1
 return;
 }
 for (i = 0; i < pos - 2 && ptr != NULL; i++)
 {
 ptr = ptr->next;
 }
 if (ptr == NULL)
 {
 printf("\nInvalid position\n");
 return;
 }
 newnode = create_node(x);
 newnode->next = ptr->next;
 ptr->next = newnode;
}
// Function to delete a node with the specified data from the linked list
void delete_pos()
{
 int x;
 struct node *ptr, *temp;
 printf("\nEnter the data to be deleted: ");
 scanf("%d", &x);
 if (start->data == x)
 {
 temp = start;
 start = start->next;
 free(temp);
 }
 else
 {
 ptr = start;
 while (ptr->next != NULL && ptr->next->data != x)
 {
 ptr = ptr->next;
 }
 if (ptr->next == NULL)
 {
 printf("\nElement %d not found in list\n", x);
 return;
 }
 temp = ptr->next;
 ptr->next = ptr->next->next;
 free(temp);
 }
}
// Function to search for a node with the specified data in the linked list
void search()
{
 int x;
 struct node *ptr;
 if (start == NULL)
 {
 printf("Linked list is empty.\n");
 }
 else
 {
 printf("\nEnter the data to search: ");
 scanf("%d", &x);
 ptr = start;
 while (ptr != NULL)
 {
 if (ptr->data == x)
 {
 printf("\nData is present.\n");
 return;
 }
 ptr = ptr->next;
 }
 printf("\nElement %d not found in list\n", x);
 }
}
// Function to print the elements of the linked list
void traverse()
{
 struct node *ptr;
 if (start == NULL)
 {
 printf("Linked list is empty.\n");
 }
 else
 {
 printf("Linked list elements: ");
 for (ptr = start; ptr != NULL; ptr = ptr->next)
 {
 printf("%d\t", ptr->data);
 }
 printf("\n");
 }
}