include <iostream>
using namespace std;


// One Way Linked List
// Insert and Delete Operation

struct node
{
	int num;
	struct node *next;
};

struct node *head,*tail,*temp,*prev;


void insert_Item()
{
	int val,key;
	cout<<"\n\n";
	cout<<"Enter the value to insert:";
	// take input
	cin>>val;

	// insert after which element?
	cout<<"\n After which value to insert:";
	cin>>key;


	// construct new node
	temp = new struct node;
	temp->num  = val;
	temp->next = NULL;

	// insert the newly created node in the list

	if(head==NULL)
	{
		// List is empty
		head = temp;
		tail = temp;
	}
	else
	{
		struct node *t;
		t = head;

		while(t!=NULL)
		{
			// search for the item after which we need to insert new item,
                        // if not found data will be inserted after tail
			if(t->num==key)
			   break;

			t = t->next;
		}

		// searched item not found, insert after tail

		if(t==NULL)
		{
			tail->next = temp;
			tail = tail->next;
		}
		else
		{
			// searched item found and it is now pointed to by 't' after the while loop ends,
                        //we need to insert the new item after that
			prev = t->next;
			temp->next = prev;
			t->next = temp;
		}

	}
	cout<<"\n";

}

void delete_Item()
{
	int key;
	cout<<"\n\n";
	cout<<"Enter the element to delete:";
	cin>>key;

	struct node *t;
	t = head;
	prev = head; // 'prev' is the pointer to hold the element just before the item we want to delete

	if(head==NULL)
		cout<<"\n List Empty..\n\n";
	else
	{
		while(t!=NULL){
			// search for the item to delete
			if(t->num==key)
			   break;

			prev = t;
			t = t->next;
		}


		if(t == NULL)
		{
			cout<<"\n Item Not Found..\n\n";
			return;
		}
		else{

		// searched item found and it is now pointed to by 't' after the while loop ends
		// We need to delete the node pointed to by 't'
		// prev no points to the node before 't'

			prev->next = t->next;
			delete t;
		}

	}

}

void print_List()
{

	temp = head;
	cout<<"\n";

	if(head==NULL)
		cout<<"\n List Empty..\n\n";
	else
	{
		while(temp!=NULL)
		{
			cout<<temp->num<<" -->";
			temp = temp->next;
		}
	}
	cout<<"\n";
	cout<<"\n";
}


int main()
{
	int n;
	while(true)
	{

		cout<<"Enter operation: (1) Insert (2) Delete (3) Print (0) Exit ():";
		cin>>n;

		if(n==1)
			insert_Item();
		else if(n==2)
			delete_Item();
		else if(n==3)
			print_List();
                else
			break;


	}

	return 0;
}