// Doubly Linked List In An Ordered Manner.
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<alloc.h>
void create();
void insert();
void delete();
void displayfor();
void displayrev();
typedef struct l_link{
			int data;
			struct l_link *flink,*blink;
			}node;
node *head,*p,*q,*next;
int item;
main()
{
	int ch;
	char choice='y';
	clrscr();
	while(choice=='y')
	{
//		clrscr();
		printf(" \n\n\n\t\t D O U B L Y  L I N K E D_L I S T   O P E R A T I O N\n");
    //		printf("\t\t\t(O R D E R E D  M A N N E R )\n");
		printf("\t\t\t  1.C R E A T I O N \n");
		printf("\t\t\t  2.I N S E R T I O N \n");
		printf("\t\t\t  3.D E L E T I O N\n");
		printf("\t\t\t  4.E X I T\n");
		printf("Enter Your choice:");
		scanf("%d",&ch);
		switch(ch)
			{
			case 1:
				create();
				break;
			case 2:
				insert();
				break;
			case 3:
				delete();
				break;
			case 4:
				exit(0);
			default:
				printf("Invalid Choice\n Retry:");
				break;
			}
		displayfor();
		displayrev();
		printf("\nDo you Want To Continue:");
		scanf("%c",&choice);
		choice=getchar();
	}

}

void create()
{
	int n,i=0;
	head=NULL;
	printf("\n Enter the No. Of Datas To Be Entered:");
	scanf("%d",&n);
	while(i<n)
	{
		insert();
		i++;
	}
	return;
}
void insert()
{
	printf("\n Enter The Data To Be Inserted:");
	scanf("%d",&item);
	q=(node*)malloc(sizeof(node));
	q->data=item;
	q->flink=NULL;
	q->blink=NULL;
	if(head==NULL)
	{
		head=q;
		return;
	}
	if(item < head->data)
	{
		q->flink=head;
		head->blink=q;
		head=q;
		return;
	}
	p=head;
	while(p->flink!=NULL)
	{
		if(item < p->flink->data)
			break;
		p=p->flink;
	}
	q->blink=p;
	p->flink->blink=q;
	q->flink=p->flink;
	p->flink=q;
	return;
}

void delete()
{
       int test=0;
	if(head==NULL)
		return;
       printf("\nEnter The Data To Be Deleted:");
	scanf("%d",&item);
	if(item == head->data)
	{
		head=head->flink;
		head->blink=NULL;
		test=1;
	}
	 p=head;
	while(p->flink!=NULL)
	{
		if(item == p->flink->data)
		{
			test=1;
			break;
		}
		p=p->flink;
	}
	q=p->flink;
	p->flink=q->flink;
	q->flink->blink=q->blink;
	if(test==1)
		printf("\n The Entered Item Is Deleted.");
	else
		printf("\n The Entered Item Is Not Found.");
	return;
}
void displayfor()
{
	p=head;
	head->blink=NULL;
	if(p==NULL)
	{
		printf("\n No Node Is Present.");
		return;
	}
	printf("\nThe contents Of Linked List(Forward)\n");
	while(p!=NULL)
	{
		item = p->data;
		printf("%d   ",item);
		p=p->flink;

	}
	return;
}
void displayrev()
{
	p=head;
      head->blink=NULL;
	if(p==NULL)
	{
		printf("\n No Node Is Present.");
		return;
	}
	printf("\nThe contents Of Linked List(Reverse)\n");
	for(p=head;p->flink!=NULL;p=p->flink);
	while(p !=NULL)
	{
		item = p->data;
		printf("%6d  ",item);

		p=p->blink;
	}
	return;
}