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

typedef struct node{				// create the user defined data type
	int data;
	struct node *next;
};

/* In this linked list I've defined two types of data such as Interger 'data' and a
 pointer variable to store user defined data type memory addresses. The 'next' variable
 holds address of the next node of the linked list  */


struct node *head = NULL;			// here I create the 'head' to catch the begining of the linked list


/* This function print the all data elements in the linked list */
void display(){
	struct node *p;
	p = head;
	printf("Values in the linked list: ");
	while(p != NULL){								// begin from the 'head' and iterate until the end
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

/* The below function get the user input value and attach the newly created node
	to the linked list */
void append(){

	struct node* temp;
	temp = (struct node*)malloc(sizeof(struct node));			// create a memory location and converts its address
	printf("Enter the data: ");
	scanf("%d", &temp->data);
	temp -> next = NULL;					// The newly created node is attached to the end, therefor last node 'next' must be NULL

	if(head == NULL){			//means linked list is empty
		head = temp;
	}else{
		struct node* p;
		p = head;
		while( p->next != NULL){		//find the end of the list, logic: last node has no connection to another
			p = p->next;
		}
		p->next = temp;
	}
}

void appendAtBegin(){
	struct node* temp;
	temp = (struct node*)malloc(sizeof(struct node));
	printf("Enter the data: ");
	scanf("%d", &temp->data);
	temp->next = NULL;
	if(head == NULL){
		head = temp;
	}else{
		temp->next = head;
		head = temp;
	}

}

int length(){
	int count;
	struct node* temp;
	temp = head;
	while(temp != NULL){
		count++;
		temp = temp->next;
	}
	return count;
}

void delete(){
	int location;
	printf("Enter the location to delete: ");
	scanf("%d", &location);
	struct node* temp;
	if(location > length()){
		printf("Invalid location entered\n");
	}else if(location == 1){
		temp = head;
		head = temp->next;
		temp->next = NULL;
		free(temp);
	}else{
		struct node* p = head;
		int i=1;
		while(i < location-1){
			p = p->next;
			i++;
		}
		struct node* q = p->next;
		p->next = q->next;
		q->next = NULL;
		free(q);
	}
}

void sortLinkedList(){
	struct node *pp;
	pp = head;
	while(pp != NULL){
		struct node* q;
		q = pp;
		while(q->next != NULL){
			printf("%d \n", pp->data);
			if(pp->data > q->next->data){
				int temp = q->next->data;
				q->next->data = pp->data;
				pp->data = temp;
			}
			q = q->next;
		}
		pp = pp->next;
	}
}

int main(){

	char choice;
	do{
		printf("Enter the choice: a: append, b: appent at begining, d: display, r: delete, s: sort, e: exit: ");
		scanf("%s", &choice);
		switch(choice){
			case 'a':
				append();
				break;
			case 'b':
				appendAtBegin();
				break;
			case 'd':
				display();
				break;
			case 'r':
				delete();
				break;
			case 's':
				sortLinkedList();
				break;
			case 'e':
				printf("\nThank You!\n");
				exit(0);
				break;
			default:
				printf("Invalide choice! please try again!\n");
				break;
		}

	}while(choice != 'e');


	return 0;
}