[C] 이중 연결 리스트

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

typedef struct _NODE_ {
	int data;
	struct _NODE_* llink;
	struct _NODE_* rlink;
}NODE;

typedef struct _LINKED_LIST_ {
	NODE* head;
}LINKED_LIST;

LINKED_LIST* createLinkedList() {
	LINKED_LIST* CL = (LINKED_LIST*)calloc(1, sizeof(LINKED_LIST));
	assert(CL != NULL);

	return CL;
}

void insertFirstNode(LINKED_LIST* CL, int x) {
	NODE* newNode = (NODE*)calloc(1, sizeof(NODE));
	assert(newNode != NULL);
	newNode->data = x;
	if (CL->head == NULL) {
		
		CL->head = newNode;
	}
	else {
		NODE* curNode = CL->head;
		newNode->rlink = CL->head;
		curNode->llink = newNode;
		CL->head = newNode;
	
	}
}

void insertNode(LINKED_LIST* CL, NODE* pre, int x) {
	NODE* newNode = (NODE*)calloc(1, sizeof(NODE));
	assert(newNode != NULL);
	newNode->data = x;
	if (CL->head == NULL) {
		CL->head = newNode;
		
	}
	else if (pre == NULL) {
		return;
	}
	else {
		if (pre->rlink == CL->head) {
			// 맨 마지막
			pre->rlink = newNode;
			newNode->llink = pre;
			
		}
		else {
			NODE* cur = pre->rlink;
			cur->llink = newNode;
			pre->rlink = newNode;
			newNode->rlink = cur;
		}
	}
}

void deleteNode(LINKED_LIST* CL, NODE* old) {
	if (CL->head == NULL || old == NULL) {
		fprintf(stderr, "삭제할 노드가 존재하지 않습니다\n");
	}
	else {
		NODE* pre = CL->head;
		NODE* cur = CL->head;
		//첫번째 노드가 삭제할 노드인 경우
		if (pre->data == old->data) {
			pre->rlink->llink = NULL;
			CL->head = pre->rlink;
			free(old);
			old = NULL;
		}
		else {
			cur = cur->rlink;
			while (cur->data != old->data) {
				pre = cur;
				cur = cur->rlink;
			}
				pre->rlink = cur->rlink;
				free(old);
				old = NULL;
		
		}
	}
}

void printList(LINKED_LIST* CL) {
	NODE* cur = CL->head;
	printf("\n\n***********이중 연결 리스트 출력*******\n");
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->rlink;
	}
	printf("\n");
}

NODE* searchNode(LINKED_LIST* CL, int x) {
	if (CL->head == NULL) {
		return NULL;
	}
	else {
		NODE* cur = CL->head;
		if (cur->data == x) {
			return cur;
		}
		else {
			cur = cur->rlink;
			int i = 1;
			while (cur != NULL) {
				printf("\nSearch try %d\n", i++);
				if (cur->data == x) {
					return cur;
				}
				else {
					cur = cur->rlink;
				}
			}


			return NULL;
		}
	}
}

NODE* searchNode2(LINKED_LIST* CL, NODE* from, int x) {
	NODE* cur = from;
	if (CL->head == NULL) {
		return NULL;
	}
	else {
		int i = 1;
		while (cur != NULL) {
			printf("\nSearch try %d\n", i++);
			if (cur->data == x) {
				return cur;
			}
			else {
				cur = cur->rlink;
			}
		}
		return NULL;
	}
}

int main() {

	int i;
	int data;
	LINKED_LIST* CL;
	NODE* p;

	srand((unsigned int)time(NULL));

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

	

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

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

	printList(CL);
	getchar();

	printf("\n(3) 5 탐색\n");
	p = searchNode(CL, 5);
	getchar();

	printf("\n(4) 4 재탐색\n");
	p = searchNode2(CL, p, 4);
	getchar();
	

	printf("(5) 4 이후에 100 넣기\n");
	insertNode(CL, p, 100);
	printList(CL);
	getchar();


	printf("(6) 10, 100, 9 순서대로 삭제\n");
	printf("\n1) 10 찾고 삭제연산 수행\n");
	p = searchNode(CL, 10);
	deleteNode(CL, p);
	printList(CL);

	printf("\n2) 100 찾고 삭제연산 수행\n");
	p = searchNode(CL, 100);
	deleteNode(CL, p);
	printList(CL);


	printf("\n3) 9 찾고 삭제연산 수행\n");
	p = searchNode(CL, 9);
	deleteNode(CL, p);
	printList(CL);



	getchar();


	printf("Done\n");



	getchar();
	return 0;
}