원형 연결 리스트

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

typedef struct _listNode_ {
	int data;
	struct _listNode_* link;
}listNode;

typedef struct _linkedList_h_ {
	listNode* head;
}linkedList_h;

linkedList_h* createLinkedList_h() {
	linkedList_h* CL = (linkedList_h*)calloc(1, sizeof(linkedList_h));
	assert(CL != NULL);

	return CL;
}

void orderedInsert(linkedList_h* CL, int item) {
	listNode* newNode = (listNode*)calloc(1, sizeof(listNode));
	assert(newNode != NULL);
	newNode->data = item;
	newNode->link = NULL;

	//1. 첫번째로 삽입되는 경우
	if (CL->head == NULL) {
		CL->head = newNode;
		newNode->link = newNode;
		return;
	}
	//2. 가장 작은 값 삽입
	listNode* curNode = CL->head;
	if (curNode->data > item) {
		while (curNode->link != CL->head) {
			curNode = curNode->link;
		}
		newNode->link = CL->head;
		CL->head = newNode;
		curNode->link = newNode;
		return;
	}
	else {
		//3. 일반적인 경우
		listNode* preNode = CL->head;
		curNode = curNode->link;
		while (curNode != CL->head) {
			if (curNode->data > item) {
				newNode->link = preNode->link;
				preNode->link = newNode;
				return;
			}
			else {
				preNode = curNode;
				curNode = curNode->link;
			}
		}
		//4. 가장 큰 값을 삽입하는 경우
		if (curNode == CL->head) {
			preNode->link = newNode;
			newNode->link = CL->head;
			return;
		}
	}
}

void printList(linkedList_h* CL) {
	if (CL->head == NULL) {
		printf("공백 리스트입니다\n");
		return;
	}
	else {
		listNode* curNode = CL->head;
		printf("\n연결리스트 출력 : ");
		while (curNode->link != CL->head) {
			printf("%d ", curNode->data);
			curNode = curNode->link;
		}
		printf("\n");
	}
}

void insertFirstNode(linkedList_h* CL, int item) {
	listNode* newNode = (listNode*)calloc(1, sizeof(listNode));
	assert(newNode != NULL);
	newNode->data = item;
	newNode->link = NULL;
	listNode* curNode = CL->head;
	if (CL->head == NULL) {
		CL->head = newNode;
	}
	else {
		while (curNode->link != CL->head) {
			curNode = curNode->link;
		}

		newNode->link = CL->head;
		CL->head = newNode;
		curNode->link = newNode;
	}
}

listNode* searchNode(linkedList_h* CL, int item) {
	if (CL->head == NULL) {
		printf("공백리스트입니다\n");
		return;
	}
	else {
		int i = 0;
		listNode* curNode = CL->head;
		while (curNode->link != CL->head) {
			printf("Search try: %d\n", i++);
			if (curNode->data == item) {
				return curNode;
			}
			else {
				curNode = curNode->link;
			}
		}
	}
}

listNode* searchNode2(listNode * p, int item) {
	if (p == NULL) {
		return;
	}
	else {
		int i = 0;
		listNode* curNode = p;
		while (curNode->link!= p) {
			if (curNode->data == item) {
				printf("Search try: %d\n", i++);
				return curNode;
			}
			else {
				curNode = curNode->link;
			}
		}

		return;
	}
}

void insertMiddleNode(linkedList_h* CL, listNode* pre, int item) {
	if (pre == NULL) {
		return;
	}
	else {
		listNode* newNode = (listNode*)calloc(1, sizeof(listNode));
		assert(newNode != NULL);
		newNode->data = item;
		newNode->link = NULL;
		if (CL->head == NULL) {
			CL->head = newNode;
			newNode->link = newNode;
			return;
		}
		else {
			newNode->link = pre->link;
			pre->link = newNode;
		}
	}
}

void deleteNode(linkedList_h* CL, listNode* p) {
	if (CL->head == NULL) {
		printf("공백 리스트입니다\n");
		return;
	}
	else {
		if (p == NULL) {
			printf("삭제할 노드가 존재하지 않습니다\n");
			return;
		}
		else {
			listNode* pre = CL->head;
			if (p == CL->head) {
				//첫번째 노드를 삭제하는 경우
				while (pre->link != CL->head) {
					pre = pre->link;
				}

				//pre는 맨마지막 노드를 가리킴 
				pre->link = CL->head->link;
				CL->head = CL->head->link;
				free(p);
				p = NULL;
			}
			else {
				while (pre->link != p) {
					pre = pre->link;
				}
				pre->link = p->link;

				free(p);
				p = NULL;
			}
			
		}
	}
}

void freeLinkedList_h(linkedList_h * CL) {
	listNode* curNode = CL->head;
	listNode* preNode = curNode;
	while (preNode != NULL) {
		free(preNode);
		preNode = NULL;
		
		curNode = curNode->link;
		preNode = curNode;
	}
}

int main() {
	int i;
	int data;

	linkedList_h* CL;
	listNode* p;

	srand(time(NULL));

	CL = createLinkedList_h();
	printf("(1) 원형 연결 리스트 생성하기 ! \n");

	printf("(2) orderedInsert()를 이용하여 원형 연결 리스트에 데이터 노드 삽입\n");

	for (i = 0; i < 10; i++) {
		orderedInsert(CL, rand() % 100);
		printList(CL);
	}

	printf("\n(3) insertFirstNode를 이용하여 원형 연결 리스트에 데이터 노드 삽입\n");

	for (i = 1; i < 11; i++) {
		insertFirstNode(CL, i);
	}

	printList(CL);
	

	printf("(4) 5 탐색\n");
	p = searchNode(CL, 5);
	
	printf("(5) 4 재탐색\n");
	p = searchNode2(p, 4);
	
	printf("(6) 4 이후에 100넣기\n");
	insertMiddleNode(CL, p, 100);
	printList(CL);

	printf("(7) 10,100,9 순서대로 삭제\n");
	p = searchNode(CL, 10);
	deleteNode(CL, p);
	printList(CL);

	p = searchNode(CL, 100);
	deleteNode(CL, p);
	printList(CL);

	p = searchNode(CL, 9);
	deleteNode(CL, p);
	printList(CL);

	freeLinkedList_h(CL);
	if (CL != NULL) {
		free(CL);
	}

	printf("Done\n");
	return 0;
}