#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct node
{
	int data;
	struct node *next;
}node;

int count(node *start)
{
	node *temp=start;
	int count=0;
	while(temp!=NULL)
	{
		temp=temp->next;
		count++;
	}
	return count;
}
node * createnode()
{
	node *ptr;
	ptr=(node *)malloc(sizeof(node));
	if(ptr==NULL)
	{
		printf("Cannot Allocate Memory!");
		exit(1);
	}

	ptr->next=NULL;
	printf("Enter an element: ");
	scanf("%d",&ptr->data);

	return ptr;
}
node * insert_at_end(node *start)
{
	int item;
	node *ptr,*temp;
	ptr=createnode();

	if(start==NULL)
		start=ptr;
	else
		{
			temp=start;
			while(temp->next!=NULL)
				temp=temp->next;
			temp->next=ptr;
		}
	return start;
}


node * insert_at_beg(node *start)
{
	int item;
	node *ptr,*temp;
	ptr=createnode();
	
	if(start==NULL)
		start=ptr;
	else
		{
			ptr->next=start;
			start=ptr;
		}
	return start;
}


node * delete_from_beg(node *start)
{
	int item;
	node *temp;

	if(start==NULL)
		printf("List Empty. Can not delete");
	else
		{
			temp=start;
			start=start->next;
			item=temp->data;
			printf("\nThe deleted item is: %d\n",item);
			free(temp);
		}
	return start;
}


node * delete_from_end(node *start)
{
	int item;
	node *temp,*t2;

	if(start==NULL)
		printf("List Empty. Can not delete");
	else if(start->next==NULL)
		start=delete_from_beg(start);
	else
		{
			temp=start;
			while(temp->next->next!=NULL)
				temp=temp->next;
			t2=temp->next;
			temp->next=NULL;	

			item=t2->data;
			printf("\nThe deleted item is: %d\n",item);
			free(t2);
		}
	return start;
}


void display(node *start)
{
	node *temp=start;
	if(start==NULL)
	{
		printf("\nList Empty\n");
		return;
	}
	printf("\nThe List of Elements: \n");
	while(temp!=NULL)
	{
		printf("%d ",temp->data);
		if(temp->next!=NULL)
				printf("-> ");
		temp=temp->next;
	}
}

int main()
{
	node *start=NULL;
	int ch;
	while(1)
	{
		printf("\n****MENU****\n1. Insert at Begin\n2. Insert at End\n3. Insert at Kth\n4. Delete From Begin\n5. Delete From End\n6. Delete From kth\n7. Display\n8. Count\n9. Exit\n");
  printf("Enter Your Choice:");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1: 
				start=insert_at_beg(start);
				display(start);
				break;
			case 2:
				start=insert_at_end(start);
				display(start);
				break;
			case 3:
			
				break;
			case 4:
				start=delete_from_beg(start);
				display(start);
				break;
			case 5:
				start=delete_from_end(start);
				display(start);
				break;
			case 6:
			
				display(start);
				break;
			case 7:
			
				display(start);
				break;
			case 8:
				printf("\nThe number of nodes: %d",count(start));
				break;
			case 9:
				exit(0);
			default:
				printf("WRONG INPUT");
		}
	}
	
	display(start);
}