struct node{ //structure to create node
	int data;
	struct node *next;
};

node *newnode,*temp;
struct node *head=NULL;
void create(){
newnode=new (struct node);
cout<<"\n Enter data";
cin>>newnode->data;
newnode->next=NULL;
if(head==0){
	head=newnode;
	temp=newnode;
}
else{
	temp->next=newnode;
	temp=newnode;
}
}

node *new_n,*temp;
insertion(){
	int ci;
insertion_choice:
	cout<<"\n Enter the type you prefer:";
	cout<<"\n Insertion at";
	cout<<"\n 1.Beginning	2.End	3.Specific Position	4.Exit";
	cin>>ci;
	if(ci==1){
		insertBegin();
		goto insertion_choice;
	}
	else if(ci==2){
		insertEnd();
		goto insertion_choice;
	}
	else if(ci==3){
		insertPos();
		goto insertion_choice;
	}
	else if(ci==4)	return;
	else{
		cout<<"\n Invalid Choice";
		goto insertion_choice;
	}
}
insertBegin(){ //Insertion at beginning of the list
	new_n=new(struct node);
	cout<<"\n Enter the data to be inserted:";
	cin>>new_n->data;
	new_n->next=head;
	head=new_n;
}
insertEnd(){ //Insertion at the end of the list
	new_n=new(struct node);
	cout<<"\n Enter the data to be inserted:";
	cin>>new_n->data;
	new_n->next=NULL;
	temp=head;
	while(temp->next!=NULL)
		temp=temp->next;
	temp->next=new_n;
}
insertPos(){ #insert at specific position
	cout<<"\n Enter the position where the data has to be inserted:";
	cin>>pos;
	if(pos>ct)
		cout<<"\n Invalid position";
	else{
		new_n=new(struct node);
		temp=head;
		while(i<pos-1){
			temp=temp->next;
			i++;
		}
	cout<<"\n Enter data to be inserted";
	cin>>new_n->data;
	new_n->next=temp->next;
	temp->next=new_n;
	}
}

deletion(){
	int ci;
deletion_choice:
	cout<<"\n Enter the type you prefer:";
	cout<<"\n Deletion";
	cout<<"\n 1.At Beginning	2.At End	3.At Specific Position	  4.Of Specific Value	 5.Exit";
	cin>>ci;
	if(ci==1){
		deleteBegin();
		goto deletion_choice;
	}
	else if(ci==2){
		deleteEnd();
		goto deletion_choice;
	}
	else if(ci==3){
		deletePos();
		goto deletion_choice;
	}
	else if(ci==4){
		deleteValue();
		goto deletion_choice;
	}
	else if(ci==5)	return;
	else{
		cout<<"\n Invalid Choice";
		goto deletion_choice;
	}
}
deleteBegin(){ //Delete at the beginning of the list
	if(head==NULL)
		printf("\n List is Empty");
	else{
		temp=head;
		head=head->next;
		free(temp);
	}
}
deleteEnd(){ //Delete at the end of the list
	node *prevnode;
	temp=head;
	while(temp->next!=NULL){
		prevnode=temp;
		temp=temp->next;
	}
	if(temp==head)
		head=NULL;
	else
		prevnode->next=NULL;
	free(temp);
}
deletePos(){ //Delete by position
	node *nextnode;
	int pos,i=1;
	temp=head;
	cout<<"\n Enter the position where the node has to be deleted:";
	cin>>pos;
	while(i<pos-1){
		temp=temp->next;
		i++;
	}
	nextnode=temp->next;
	temp->next=nextnode->next;
	free(nextnode);
}
deleteValue(){ //Delete by value
	int value;
	cout<<"Enter the value you wish to delete:";
	cin>>value;
	temp=head;
	node *temp1;
	if(temp->data==value)
	{
		head=head->next;
		free(temp);
	}
	else
	   while(temp)
		{
			if(temp->next->data==value)
			{
				temp1=temp->next;
				temp->next=temp1->next;
				free(temp1);
				return;
			}
		temp=temp->next;
		}
	cout<<"Number not found in the list";
}

reverse(){
	struct node *prevnode,*cnode,*nnode;
	prevnode=NULL;
	cnode=nnode=head;
	while(nnode!=NULL){
		nnode=nnode->next;
		cnode->next=prevnode;
		prevnode=cnode;
		cnode=nnode;
	}
	head=prevnode;
}

//a and b are heads of two linked lists created
concatenate(node *a,node *b)
    {
        if( a != NULL && b!= NULL )
        {
            if (a->next == NULL)
                a->next = b;
            else
                concatenate(a->next,b);
        }
        else
        {
            cout << "Either a or b is NULL\n";
        }
    }

search(){
	int ct=0,s,cs=0;
	temps=head;
	cout<<"\n Enter the element to search for:";
	cin>>s;
	if(head==NULL){
		cout<<"\n List is Empty";
		return;
	}
	while(temps!=NULL){
		ct=0;
		if(temps->data==s){
			ct++;
			break;			
		}
		temps=temps->next;
		cs++;
	}
	if(ct==0)
		cout<<"\n Element is not found";
	else{
		cout<<"\n Element is found at position  "<<cs+1;
		return;
	}
}