#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int no;
struct node *pre,*next;
};
struct node *start=NULL,*last=NULL;


void Append()
{

	struct node *n;
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nEnter no");
	scanf("%d",&n->no);
	n->next=NULL;
	if(start==NULL)
	{
		start=last=n;
		start->pre=NULL;
		return;
	}
	last->next=n;
	n->pre=last;
	last=n;
}

void ftraverse()
{
	struct node *p=start;
	if(start==NULL)
	{
		printf("\n Empty Link List");
		return;
	}
	while(p!=NULL)
	{
		printf("    %d",p->no);
		p=p->next;
	}
}





void insertafter()
{
	int val;
	struct node *p =start,*n;
	if(start==NULL)
	{
		printf("\nEmpty LINK lIST");
		return;
	}

	printf("\n Enter number after which you want to INSERT");
	scanf("%d",&val);
	if(val==last->no)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	last->next=n;
	n->pre=last;
	last=n;
	last->next=NULL;
	printf("\n NODE INSErted");
	return;
	}
	while(p->next!=NULL)
	{
	if(val==p->no)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	n->next=p->next;
	n->pre=p;
	p->next=n;
	n->next->pre=n;

	 printf("\n NODE INSErted");
	return;
	}
	  p=p->next;
	  }
	  printf("\n%d NOT found",val);
	  }



void insertbefore()
{
	int val;
	struct node *p =start,*n;
	if(start==NULL)
	{
		printf("\nEmpty LINK lIST");
		return;
	}

	printf("\n Enter number BEFORE which you want to INSERT");
	scanf("%d",&val);
	if(val==start->no)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	start->pre=n;
	n->next=last;
	start=n;
	start->pre=NULL;
	printf("\n NODE INSErted");
	return;
	}
	while(p!=NULL)
	{
	if(val==p->no)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	n->pre=p->pre;
	n->next=p;
	p->pre=n;
	n->pre->next=n;

	 printf("\n NODE INSErted");
	return;
	}
	  p=p->next;
	  }
	  printf("\n%d NOT found",val);
	  }




void insertbypos()
{
	int val;
	struct node *p =start,*n;
	int non=0,i,pos;
	if(start==NULL)
	{
		printf("\nEmpty LINK lIST");
		return;
	}


	printf("\nEnter the position");
	scanf("%d",&pos);
	while(p!=NULL)
	{
	non++;
	p=p->next;
	}

	if (pos<1&&pos>non+1)
	{
	printf("\n INvalid POSition");
	}
	if(pos==1)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	start->pre=n;
	n->next=start;
	start=n;
	start->pre=NULL;
	printf("\n NODE INSErted");
	return;
	}

	if(pos==non+1)
	{
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	last->next=n;
	n->pre=last;
	last=n;
	last->next=NULL;
	printf("\n NODE INSErted");
	return;
	}
	p=start;
	for(i=1;i<pos-1;i++)
	{
	p=p->next;
	}
	n=(struct node*)malloc(sizeof(struct node));
	printf("\nENTER number");
	scanf("%d",&n->no);
	n->next=p->next;
	n->pre=p;
	p->next=n;
	n->next->pre=n;
	 printf("\n NODE INSErted");
	return;
	}



	 void delByValue()
	 {


		int val;
	struct node *p =start;
	int i,pos;
	if(start==NULL)
	{
		printf("\nEmpty LINK lIST");
		return;
	}


	printf("\nEnter the number to be deleted");
	scanf("%d",&val);
	if(start==last&&val==start->no)
	{
	free(p);
	start=last=NULL;
	printf("\nNODE DEleted");
	return;
	}
	else if (val==start->no)
	{
	   start=start->next;
	   start->pre=NULL;
	   free(p);
	   printf("\nNOde DELeted");
	   return;
	   }
	   else if(val==last->no)
	   {
	   p=last;
	   last=last->pre;
	   last->next=NULL;
	   free(p);
	     printf("\nNOde DELeted");
	   return;

	   }
	   while(p->next!=NULL)
	   {
	   if(val==p->no)
	   {
	   p->pre->next=p->next;
	   p->next->pre=p->pre;

	   free(p);
	     printf("\nNOde DELeted");
	   }
	   p=p->next;
	   }
	   printf("\n NODE NOt FOUnd") ;

	   }





	 void delByPos()
	 {

	struct node *p =start;
	int non=0,i,pos;
	if(start==NULL)
	{
		printf("\nEmpty LINK lIST");
		return;
	}

	printf("\nEnter the POSITION which is to be deleted");
	scanf("%d",&pos);
	while(p!=NULL)
	{
	non++;
	p=p->next;
	}
	 p=start;
	 if(pos<1||pos>non);
	 {
	 printf("\n INvalid Position");
	 }

	if(start==last&&pos==1)
	{
	free(p);
	start=last=NULL;
	printf("\nNODE DEleted");
	return;
	}
	else if (pos==1)
	{
	   start=start->next;
	   start->pre=NULL;
	   free(p);
	   printf("\nNOde DELeted");
	   return;
	   }
	   else if(pos==non)
	   {
	   p=last;
	   last=last->pre;
	   last->next=NULL;
	   free(p);
	     printf("\nNOde DELeted");
	   return;

	   }
	   for(i=0;i<pos-1;i++)
	   {
	   p=p->next;
	   }
	   p->pre->next=p->next;
	   p->next->pre=p->pre;

	   free(p);
	     printf("\nNOde DELeted");
	   }


















 void main()
 {
 int ch;
 clrscr();
 do
 {
 printf("\n\n\n 1 Append");
 printf("\n 2 Forward TRAverse");
 printf("\n 3 INsert after the given number");

 printf("\n 4  INsert before the given number");
 printf("\n 5 INsert BY POsition ");
 printf("\n 6 DElerte By VAlue ");
  printf("\n 7 DElete by POSITION");

 printf("\n 0 EXIT");
 printf("\n Enter your choice");
 scanf("%d",&ch);
 switch(ch)
 {
 case 1:Append();
	break;
 case 2:ftraverse();
	break;

 case 3: insertafter();
	break;
 case 4: insertbefore();
	break;
 case 5:insertbypos();
	break;
 case 6:delByValue();
	break;
 case 7: delByPos();
	 break;
 case 0:
	  break;

 default: printf("\n Invalid Choice");
 }
 }while(ch!=0);
 getch();
 }