/* Linked List Implementation using Self-Referrential Structures */

#include<stdio.h>
#include<stdlib.h>

/* Structure Declaration:
	Structure for a Linked List (Self-Referrential Structure)
	requires two elements.
	
	One Element member, holding the value that the list is to be made of
	One Self-Referring Pointer member for making it a Linked List. */

	typedef struct listlink

		{
			int element;
			struct listlink *next;
		} node ;

/* Create Linked List:
	Creates a Linked List by allocating adequate memory space for each block.
	Requires a value of '-99' to stop constructing the list. */

	void create(node *list)

		{
			int item;
			
			printf("\nEnter an element: ");
			scanf("%d",&item);
			
			if (item==-99)
				{
					list->next = NULL;
				}
			else
				{
					list->element=item;
					list->next = (node *)malloc(sizeof(node));
					create(list->next);
				}
		}
	
/* Find an Element:
	Finds an element in the constructed list and returns an Integer equivalent to the Boolean True or Boolean False. */

	int find(node *list, int x)

		{
			node *p=list;
			
			if(p->element == x)
				{
					return 1;
				}
				
			else
				{
					if (p->next!=NULL)
						return find(p->next,x);
					else
						return 0;
				}
		}

/* Find Previous:
	Finds an element and returns the memory location of the previous pointer referring to it. 
	This should'nt be used if the List contains just ONE element.
	Changing the function to start from 'list' than 'list->next' would lead to a Segmentation Fault at times,
	and is thus avoided. */

	node *findprev(node *list, int x)

		{
			node *p=list->next;
			
			while(p->next!=NULL&&p->next->element!=x)
				{
					p=p->next;
				}
				
			return p;
		}

/* Insert:
	Inserts a node into the Linked List, using a new node.
	It inserts the node after the Key value. If the Key value isn't found, it displays an error. */

	node *insert(node *list)
		{
			int a=0,key=0;
			node *temp, *pos;
			
			printf("\nEnter the element to insert: ");
			scanf("%d",&a);
			
			printf("\nTo be inserted after the element: ");
			scanf("%d",&key);
			
			temp = (node *)malloc(sizeof(node));
			
			if(list->element == key)
				{
					temp->element = a;
					temp->next = list->next;
					list->next=temp;
				}
			else
				{
					pos = findprev(list,key);
					if(pos!=NULL)
						{
							temp->element=a;
							temp->next=pos->next;
							pos->next=temp;
						}
					else
						{
							printf("\nElement not found, retry ..");
						}
				}
			return list;
		}

/* Delete:
	Deletes a node based on a Key value request. The node before the Key node is linked to the node after it.
	The temporary value holding the Key node is then freed from the memory. */

	node *delete(node *list)

		{
			int key;
			node *temp, *p;
			
			printf("\nEnter the element to delete: ");
			scanf("%d",&key);
			
			temp = (node *)malloc(sizeof(node));
			
			if(list->element==key)
				{
					temp = list->next;
					free(list);
					list = temp;
				}
			
			else
				{
			
				p = findprev(list,key);
				
				if(p==NULL)
					{
					
						printf("\nElement not found ...");
						
					}
				else
					{
					
						temp = p->next;
						p->next=temp->next;
						free(temp);
						
					}
				}
				
			return list;
		}

/* Display:
	Displays the Linked List in a pictorial fashion.
	A sample output of the list via this would look like:
		The List is:
		4 -> 5 -> 6 -> NULL
	Where, NULL represents the END of list. For an empty list too, it shows NULL. */
	
	void display(node *list)

		{	
			if(list->next==NULL)	
					printf("NULL\n");

			else
				{
					printf("%d -> ",list->element);
					
					display(list->next);
				}
		}
	
/* Count:
	Counts the number of elements in the node until its end. */

	int count(node *list)

		{
			if(list==NULL)
				return 0;
			else
			return(1+count(list->next));
		}

/* Main Menu:
	Displays a menu-based access system for various operations on the linked list.
	The menu looks like:
		1. Create
		2. Insert
		3. Delete
		4. Display
		5. Find
		6. Exit
	Each item in the menu calls the appropriate functions of the Linked List. */

	int main()

		{
			int choice, key, loc;
			node *temp;
			
			while(1)
				{
					printf("\nLinked Lists\n------------\n1. Create\n2. Insert\n3. Delete\n4. Display\n5. Find\n6. Exit\nEnter your choice: ");
					scanf("%d",&choice);
					
					switch(choice)
						{
							case 1:
							
								temp=(node *)malloc(sizeof(node));
								
								create(temp);
								
								printf("\nThe List is: \n");
								display(temp);
								
								break;
								
							case 2:
							
								temp=insert(temp);
								
								printf("\nThe List is: \n");
								display(temp);
								
								break;
								
							case 3:
							
								temp=delete(temp);
								
								printf("\nThe List is: \n");
								display(temp);
								
								break;
								
							case 4:
							
								printf("\nThe List is: \n");
								display(temp);
								
								break;
								
							case 5:
							
								printf("\nEnter the value to find: ");
								scanf("%d",&key);
								
								loc = find(temp,key);
								
								if(loc)
									printf("Element in the list ...");
								
								else
									printf("Element not in list ...");
								
								printf("\nThe List is: \n");
								display(temp);
								
								break;
								
							case 6:
							
								return 0;
								
							default:
							
								printf("Invalid choice ...");
								
						}
				}
		}