#include <iostream>

using namespace std;

struct single_list
{
	int data;
	single_list *next;
};

void make_single_list(int n, single_list** head)
{
	if (n > 0)
	{
		(*head) = new single_list();
		cout << "Enter the value ";
		cin >> (*head)->data;
		(*head)->next = NULL;
		make_single_list(n - 1, &((*head)->next));
	}
}

void print_single_list(single_list *head)
{
	if (head != NULL)
	{
		cout << head->data << " ";
		print_single_list(head->next);
	}
	else
		cout << "\n";
}

single_list* insert_item_single_list(single_list* head, int number, int dataItem)
{//add item with certain number in single_list
	number--;
	single_list* newItem = new(single_list);
	newItem->data = dataItem;
	newItem->next = NULL;
	if(head == NULL)//list is empty
		head = newItem;
	else
	{
		single_list* current = head;
		for(int i=1; i < number && current->next != NULL; i++)
			current = current->next;
		if(number == 0)//add item at the first place
		{
			newItem->next = head;
			head = newItem;
		}
		else
		{
			if(current->next != NULL)//add item not at the first place
				newItem->next = current->next;
			current->next = newItem;
		}
	}
	return head;
}

single_list* delete_item_single_list(single_list* head, int number)
{//delete item with certain number from single_list
	single_list* ptr;
	single_list *current = head;
	for(int i = 1; i < number && current != NULL; i++)
		current = current->next;
	if(current != NULL)
	{
		if(current == head)//delete item == first
		{
			head = head->next;
			delete(current);
			current = head;
		}
		else
		{
			ptr = head;
			while(ptr->next != current)
				ptr = ptr->next;
			ptr->next = current->next;
			delete(current);
			current = ptr;
		}
	}
	return head;
}

bool find_item_single_list(single_list* head, int dataItem)
{
	single_list* ptr;
	ptr = head;
	while(ptr != NULL)
	{
		if(dataItem == ptr->data)
			return true;
		else
			ptr = ptr->next;
	}
	return false;
}


void delete_single_list(single_list* head)
{
	if(head != NULL)
	{
		delete_single_list(head->next);
		delete head;
	}
}


int main()
{
	single_list *head;
	int n;
	cout << "How many elements would be? ";
	cin >> n;
	make_single_list(n, &head);
	print_single_list(head);
	cout << "Enter the number for addition(1-indexation) ";
	int number, dataItem;
	cin >> number;
	cout << "Enter the dataItem for addition ";
	cin >> dataItem;
	head = insert_item_single_list(head, number, dataItem);
	print_single_list(head);
	cout << "Enter the number for deleting ";
	cin >> number;
	head = delete_item_single_list(head, number);
	print_single_list(head);
	cout << "What do you want to find? ";
	cin >> dataItem;
	cout << find_item_single_list(head, dataItem) << endl;
	delete_single_list(head);
	return 0;
}