/**********************************************************
*		Titile		:	Single Linked List
*		Author		:	Jang Young-bin
*		Date		:	2014-04-07
*		Modified	:	Singly Linked List 잘못된 구조 수정
***********************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int data;
	struct _node *link;
}node;

typedef struct _headNode {
	node* link;
}headNode;

void InsertNode(headNode* head, int val);
void DeleteNode(headNode* head, int val);
void PrintNode(headNode* head);
int RetreiveNode(headNode* head, int val);


int main(void)
{
	headNode* head;
	head = (headNode*)malloc(sizeof(headNode));
	head->link = NULL;
	

	char menu;
	int val;

	while(1) {
		printf("Insert menu(I/D/P/X) : ");
		scanf("%c", &menu); getchar();

		switch(menu) {
		case 'i':
		case 'I':
			printf("삽입할 값 : ");
			scanf("%d", &val); getchar();
			InsertNode(head, val);
			break;

		case 'd':
		case 'D':
			printf("삭제할 값 : ");
			scanf("%d", &val); getchar();
			DeleteNode(head, val);
			break;

		case 'p':
		case 'P':
			PrintNode(head);
			break;

		case 'x':
		case 'X':
			exit(0);

		default :
			printf("잘못입력하셨습니다.\n");
		}
	}
	return 0;
}

void InsertNode(headNode* head, int val)
{
	node *newNode = (node*)malloc(sizeof(node));
	node *tmp, *prev;
	int flag;

	if(flag = RetreiveNode(head, val)) {
		fprintf(stderr, "Value is alerady Exist!\n");
		return;	
	};

	newNode->data = val;

	if(head->link == NULL) {					// head가 비어있을 때
		head->link = newNode;
		newNode->link = NULL;
	} else {
		tmp = head->link;
		prev = NULL;

		if(newNode->data < tmp->data) {		// newNode 가장 앞에 삽입될 때
			head->link = newNode;
			newNode->link = tmp;
		} else {
			while(tmp->data < newNode->data) {
				if(tmp->link == NULL) {		// newNode가 마지막일 때
					tmp ->link = newNode;
					newNode->link = NULL;
					return;
				}
				prev = tmp;
				tmp = tmp->link;
			}		
			newNode->link = prev->link;		// newNode가 중간에 삽입될 때
			prev->link = newNode;

		}			
	}
}

void DeleteNode(headNode* head, int val)
{
	node *tmp, *prev;
	int flag;

	if(flag = RetreiveNode(head, val) != 1) {
		fprintf(stderr, "Values is Not exist!\n");
		return;
	}	

	tmp = head->link;
	prev = NULL;

	while(tmp != NULL) {

		if(tmp->data == val) {
			if(prev == NULL) {		// head 다음 노드 삭제시
				head->link = tmp->link;
				free(tmp);
				return;
			}
			prev->link = tmp->link;
			free(tmp);
			return;
		}

		prev = tmp;
		tmp = tmp->link;
	}
}

void PrintNode(headNode* head)
{
	node* tmp;

	for(tmp = head->link; tmp != NULL; tmp = tmp->link) {
		printf("%5d", tmp->data);
	}
	printf("\n");
}

int RetreiveNode(headNode* head, int val)
{
	node* tmp;

	for(tmp = head->link; tmp != NULL; tmp = tmp->link) {
		if(tmp->data == val)
			return 1;	// 존재하면 1을 반환
	}

	return 0;			// 존재하지 않으면 0을 반환
}