#include<stdio.h>
#include<stdlib.h>
struct node
{
	struct node *prev;
	int info;
	struct node *link;
};
struct node * create(struct node *,struct node *);
void display(struct node *,struct node *);
int count(struct node *,struct node *);
struct node * InsBeg(struct node *,struct node *);
struct node * InsEnd(struct node *,struct node *);
struct node * Insbetween(struct node *,struct node *);
struct node * DelBeg(struct node *,struct node *);
struct node * DelEnd(struct node *,struct node *);
struct node * Delbetween(struct node *,struct node *);
void search(struct node *);
int main()
{
        system("clear");
	struct node *start,*end,*ptr;
	int choice,c;
	start=(struct node *)malloc(sizeof(struct node));
	end=start;
	while(1)
	{
		printf("\n0: Quit");
		printf("\n1: Create");
		printf("\n2: Display");
		printf("\n3: Count");
		printf("\n4: Insert at begening");
		printf("\n5: Insert at End");
		printf("\n6: Insert inbetween a node");
		printf("\n7: Delete first node");
		printf("\n8: Delete last node");
		printf("\n9: Delete inbetween node");
		printf("\n10: Search an element");
		printf("\n\nEnter your option: ");
		scanf("%d",&choice);

		switch(choice)
		{
			case 0:	return 0;

			case 1:	end=create(start,end);
						break;
			case 2:	display(start,end);
						break;
			case 3:	c=count(start,end);
						printf("\nNumber of nodes in linklist= %d",c);
						break;
			case 4:	start = InsBeg(start,end);
						ptr=start;
						while(ptr->link!=NULL)
						  ptr=ptr->link;
						end=ptr;
						break;
			case 5:	end=InsEnd(start,end);
						ptr=end;
						while(ptr->prev!=NULL)
						  ptr=ptr->prev;
						start=ptr;
						break;
			case 6:	start=Insbetween(start,end);
						ptr=start;
						while(ptr->link!=NULL)
						  ptr=ptr->link;
						end=ptr;
						break;
			case 7:	start = DelBeg(start,end);
						if(start==NULL)
						  end=NULL;
						break;
			case 8:	end=DelEnd(start,end);
						if(end==NULL)
						  start=NULL;
						break;
			case 9:	start=Delbetween(start,end);
						ptr=start;
						while(ptr->link!=NULL)
						  ptr=ptr->link;
						end=ptr;
						break;
			case 10:	search(start);
						break;
			default:	printf("Invalid choice:::");
		}
	}
}

struct node * create(struct node *start,struct node *end)
{
	struct node *ptr,*tmp;
	int op;
	printf("\nEnter node value:");
	scanf("%d",&start->info);
	start->link=NULL;
	start->prev=NULL;
	ptr=start;
	printf("\nDo you want to add more nodes (1/0) :");
	scanf("%d",&op);
	while(op!=0)
	{
		tmp=ptr;
		ptr->link=(struct node *)malloc(sizeof(struct node));
		ptr=ptr->link;
		printf("\nEnter node value:");
		scanf("%d",&ptr->info);
		ptr->link=NULL;
		ptr->prev=tmp;
		end=ptr;
		printf("\nDo you want to add more nodes (1/0) :");
		scanf("%d",&op);
	}
	return end;
}

void display(struct node *start,struct node *end)
{
	struct node *ptr,*ptr1;
	printf("\nLinklist in forward traversing:\n ");
	ptr=start;
	while(ptr!=NULL)
	{
		printf("%d\t",ptr->info);
		ptr=ptr->link;
	}
	printf("\nLinklist in backward traversing:\n");
	ptr=end;
	while(ptr!=NULL)
	{
		printf("%d\t",ptr->info);
		ptr=ptr->prev;
	}
}

int count(struct node *start,struct node * end)
{
	struct node *ptr;
	int c=0;
	ptr=start;
	while(ptr!=NULL)
	{
		c++;
		ptr=ptr->link;
	}
	return c;
}

struct node * InsBeg(struct node *start,struct node * end)
{
	struct node *new1;
	new1=(struct node *)malloc(sizeof(struct node));
	if(new1==NULL)
	{
		printf("\nMemory Overflow");
		return 0;
	}
	printf("\nEnter new node value: ");
	scanf("%d",&new1->info);

	if(start==NULL)
	{
	  start=end=new1;
	  new1->link=NULL;
	  new1->prev=NULL;
	}
	else
	{
	  new1->link=start;
	  start->prev=new1;
	  new1->prev=NULL;
	  start=new1;
	}

	return start;
}

struct node * InsEnd(struct node *start,struct node * end)
{
	struct node *new1,*ptr;
	new1=(struct node *)malloc(sizeof(struct node));
	if(new1==NULL)
	{
		printf("\nMemory Overflow");
		return 0;
	}
	printf("\nEnter new node value: ");
	scanf("%d",&new1->info);

	if(end==NULL)
	{
	  start=end=new1;
	  new1->link=NULL;
	  new1->prev=NULL;
	}
	else
	{
	  new1->link=NULL;
	  end->link=new1;
	  new1->prev=end;
	  end=new1;
	}

	return end;
}

struct node * Insbetween(struct node *start,struct node * end)
{
	struct node *new1,*ptr;
	int loc,c=1;
	printf("\nEnter node number to insert: ");
	scanf("%d",&loc);

	ptr=start;
	while(c<loc-1)
	{
		ptr=ptr->link;
		c++;
	}
	if(c==1)
	  start=InsBeg(start,end);
	else if(ptr->link==NULL)
	  end=InsEnd(start,end);
	else
	{
	  new1=(struct node *)malloc(sizeof(struct node));
	  if(new1==NULL)
	  {
		 printf("\nMemory Overflow");
		 return 0;
	  }
	  printf("\nEnter new node value: ");
	  scanf("%d",&new1->info);

	  new1->link=ptr->link;
	  ptr->link->prev=new1;
	  ptr->link=new1;
	  new1->prev=ptr;
	}
	return start;
}

struct node * DelBeg(struct node *start,struct node * end)
{
	struct node *ptr;
	if(start==NULL)
	{
		printf("\nUnderflow");
		return 0;
	}

	ptr=start;

	if(start->link==NULL)
	{
	  start=NULL;
	  end=NULL;
	}
	else
	{
	  start=start->link;
	  start->prev=NULL;
	}
	free(ptr);

	return start;
}

struct node * DelEnd(struct node *start,struct node * end)
{
	struct node *prev,*ptr;
	if(start==NULL)
	{
		printf("\nUnderflow");
		return 0;
	}
	ptr=end;
	if(start->link==NULL)
	{
	  start=NULL;
	  end=NULL;
	}
	else
	{
	  end=end->prev;
	  end->link=NULL;
	}
	free(ptr);

	return end;
}

struct node * Delbetween(struct node *start,struct node * end)
{
	struct node *prev,*ptr;
	int loc,c=1;
	if(start==NULL)
	{
		printf("\nUnderflow");
		return 0;
	}
	printf("\nEnter node number to delete: ");
	scanf("%d",&loc);

	ptr=start;
	while(c<loc)
	{
		ptr=ptr->link;
		c++;
	}

	if(c==1)
	  start=DelBeg(start,end);
	else if(ptr->link==NULL)
	  end=DelEnd(start,end);
	else
	{
	  ptr->prev->link = ptr->link;
	  ptr->link->prev = ptr->prev;
	}
	free(ptr);
	return start;
}

void search(struct node *start)
{
	struct node *ptr;
	int item,c=0;
	printf("\nEnter node value you want to search: ");
	scanf("%d",&item);

	ptr=start;
	while(ptr != NULL)
	{
		c++;
		if(ptr->info == item)
			break;
		ptr=ptr->link;
	}
	if(ptr==NULL)
		printf("\nItem not found");
	else
		printf("\nItem found at node number %d",c);
}