#include <stdio.h>
#include <malloc.h>

struct node{
	int data;
	struct node *left, *right;
};
int x,choice,loop=1;
struct node *head, *temp, *prev, *next, *newnode;

void insert()
{
	int a,b;
	newnode=(struct node *)malloc(sizeof(struct node));
	printf("Input an integer data: ");
	scanf("%d",&a);
	printf("After: ");
	scanf("%d",&b);
    newnode->data=a;
    temp=head;
    while(temp!=NULL && temp->data!=b)
    {
        temp=temp->right;
    }
    newnode->right=temp->right;
    newnode->left=temp;
	if(temp->right!=NULL)
	{
		next=temp->right;
		next->left=newnode;
	}
    temp->right=newnode;
}

void delete()
{
	int c;
	if(head->right==NULL)
	{
		printf("ERROR: Cannot delete any nodes! The linked list only has 1 node left!\n");
	}
	else
	{
		printf("Delete: ");
		scanf("%d",&c);
		if(c==head->data)
		{
			head->data=head->right->data;
			head->right=head->right->right;
		}
		else
		{
			temp=head;
			while(temp!=NULL && temp->data!=c)
			{
				prev=temp;
				temp=temp->right;
			}
			if(temp->right!=NULL)
			{
				temp=temp->right;
				prev->right=temp;
				temp->left=prev;
			}
			else
			{
				prev->right=NULL;
			}
		}
	}
}

void print(struct node *h)
{
    while(h!=NULL)
    {
        printf("Left:%d  Data:%d  Right:%d\n",h->left,h->data,h->right);
        h=h->right;
    }
}

void main()
{
	head=(struct node*)malloc(sizeof(struct node));
	printf("Please input integer data to the new linked list: (0 = Exit)\n");
	scanf("%d",&x);
	if(x!=0)
	{
		head->data=x;
		head->left=NULL;
		head->right=NULL;

		while(x!=0)
		{
			scanf("%d",&x);
			if(x!=0)
			{
				newnode=(struct node*)malloc(sizeof(struct node));
				newnode->data=x;newnode->left=NULL;newnode->right=NULL;
				temp=head;	
				while(temp!=NULL)
				{
					prev=temp;
					temp=temp->right;
				}
				prev->right=newnode;
				newnode->left=prev;
			}	
		}
		while(loop==1)
		{
			printf("\nPlease select what you want to do:\n\n");
			printf("1) Insert a new node\n2) Delete a node\n3) Print data\n4) Exit\n\n");
			printf("Choice: ");
			scanf("%d",&choice);
			switch(choice)
			{
			case 1:insert();break;
			case 2:delete();break;
			case 3:print(head);break;
			case 4:loop=0;break;
			default:printf("Invalid choice!\n");
			}
		}
	}
	printf("Good bye!\n");
}