#include<stdio.h>
#include<stlib.h>
#include<conio.h>

struct node;
typedef struct node *ptr;
typedef ptr list;
typedef ptr position;
typedef int data;

struct node
{
 data element;
 struct node *next;
}

//function prototypes
void makeempty(void); //to make empty list
int isempty(void);  //to check list is empty or not
void create(void);  //to create initial set of elements
position findprevious(data); //to find position of previous element
void delet(data);  //to delete given element
void display(void);  //to display all the elements
void insert(data, int);  //to insert a new element
position getprevposition(int); //to find position of previous element
data getelement(int);  //to find the element at given position
int getposition(data);  //to find position of given element

//global variable declarations
position first;
position last;
position L;
int length;

//to make empty list
void makeempty(void)
{
 position tmp;
 tmp = malloc(sizeof(list));
 tmp->next = NULL;
 L = tmp;
 first = last = NULL;
}

//to check list is empty or not
int isempty(void)
{
 if (L->next = NULL)
  return 1;
 else
  return 0;
}

//to create initial set of elements
void create(void)
{
 data e;
 int n, i;
 position tmp;
 makeempty();
 printf(“Enter number of element : \ “);
 scanf(“%d”, &n);
 for (i=0; i<n; i++)
 {
  printf(“Enter an element : “);
  scanf(“%d”, &e);
  tmp = malloc(sizeof(list));
  tmp->element = e;
  tmp->next = NULL;
  if (L->next == NULL)
  {
   L->next = tmp;
   first = last = tmp;
  }
  else
  {
   last->next = tmp;
   last = tmp;
  }
 }
}

//to display all the elements
void display()
{
 position t;
 for(t=first; t!=NULL; t=t->next)
  printf(“%d --> “, t->element);
 getch();
}
//to find position of previous element
position getprevposition(int index)
{
 position tmp;
 int count = 1;
 if (index>length)
 {
  printf(“Invalid Position”);
  return NULL;
 }
 else
 {
  for (tmp=first; count<index-1; tmp=tmp->next)
   count++;
  return tmp;
 }
}

//to insert a new element
void insert(data x, int p)
{
 position pos, tmp;
 tmp = malloc(sizeof(list));
 tmp->element=x;
 if (p==1)  //first position
 {
  tmp->next = first;
  L->next = tmp;
  first = tmp;
  length++;
 }
 else if (p == length) //last position
 {
  last->next = tmp;
  last = tmp;
  tmp->next = NULL;
 }
 else   //arbitrary position
 {
  pos = getpreviousposition(p);
  if (pos == NULL)
  {
   printf(“Invalid position”);
   getch();
  }
  else
  {
   tmp->next = pos->next;
   pos->next = tmp;
   length++;
  }
 }
}

//to find position of previous element
position findprevious(data x)
{
 position p;
 p = L;
 while (p->next->element!=x && p->next!=NULL)
  p = p->next;
 return p;
}

//to delete given element
void delet(data x)
{
 position p, tmp;
 if (isempty())
 {
  printf(“List is empty”);
  getch();
 }
 else
 {
  p = findprevious(x);
  if (p->next = NULL)
  {
   printf(“Element not found”);
   getch();
  }
  else
  {
   if (p->next == last)
   {
    free (p->next);
    p->next =  NULL;
    last = p;
    length--;
    return;
   }
   if (p == L)
   {
    first = first->next;
   }
   tmp = p->next;
   p->next = tmp->next;
   free(tmp);
   length--;
  }
 }
}

int menu()
{
 int ch;
 printf(“1. Create\n2. Display\n3.Insert\n4.Get Element\n5.Get Position\n6. Delete\n7. Exit\n\n Enter your choice : “);
 scanf(“%d”, &choice);
 return choice;
}

//to find the element at given position
data getelement(int pos)
{
 position p;
 int i;
 p = L;
 if (pos > length)
  return NULL;
 else
 {
  for(i=0; i<pos; i++)
   p = p->next;
  return p->element;
 }
}

//to find position of given element
 int getposition(data e)
{
 position p;
 int i=0;
 for (p=first; p!=NULL; p=p->next)
 {
  if (p->element == e)
   return i+1;
  else
   i++;
 }
 return NULL;
}

void main()
{
 int ch;
 data n, p;
 while(1)
 {
  clrscr();
  ch = menu();
  switch (ch)
  {
   case 1:
    create();
    break;
   case 2:
    display();
    break;
   case 3:
    printf(“Enter an element : “);
    scanf(“%d”, &n);
    printf(“Enter Position : “);
    scanf(“%d”, &p);
    insert (n, p);
    break;
   case 4:
    printf(“Enter an element : “);
    scanf(“%d”, &n);
    delet (n);
    break;
   case 5:
    printf(“Enter position : “);
    scanf(“%d”, &p);
    if (p<1 || p>length)
     printf(“Invalid position”);
    else
     printf(“Element at position %d is %d”, p, getelement(p));
    getch();
    break;
   case 6:
    printf(“Enter an element : “);
    scanf(“%d”, &n);
    if (getposition(n) == NULL)
     printf(“Element doesn’t Exist”);
    else
     printf(“%d exists at position %d”, n, getposition(n));
    getch();
    break;
   default:
    printf(“Invalid Choice”);
    getch();
  }
 }
}

Sample Output:

1. Create
2. Display
3. Insert
4. Delete
5. Get element
6. Get position
7. Exit

Enter your Choice: 1

Enter number of element: 3
Enter an element: 10
Enter an element: 20
Enter an element: 30

Enter your Choice: 3

Enter element: 25
Enter Position: 3

Enter your Choice: 2

10 --> 20 --> 25 --> 30

Enter your Choice: 6

Enter an element:20
20 exists at position 2

Enter your Choice: 4

Enter an element 30

Enter your Choice: 2

10 --> 20 --> 25

Enter your Choice: 7