[C언어] 원형 연결 리스트 노드 삽입 탐색 삭제를 구현해보자

오늘은 원형 연결 리스트를 구현해보겠습니다

원형 연결 리스트는 연결 리스트가 한쪽으로만 연결 되어있다는 단점을 개선시킨 자료구조이지만

이중연결 리스트와 달리 한쪽으로만 순환할수있기때문에 완벽한 해결책을 제시했다고는 할 수 없습니다.

 

그렇지만, 중요한 자료구조 중 하나이기때문에 코드로 구현해보고 넘어가기는 안성맞춤이라고 생각합니다.

실행 결과

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

typedef struct ListNode {
	char data[4];
	struct ListNode* link;
}listNode;

typedef struct {
	listNode* head;
}linkedList_h;

//공백 원형 연결 리스트를 만드는 함수
linkedList_h* createLinkedList_h(void) {
	linkedList_h* CL;
	CL = (linkedList_h*)malloc(sizeof(linkedList_h));
	CL->head = NULL;
	return CL;
}

void printList(linkedList_h* CL) {
	listNode* temp;
	printf(" CL = (");
	temp = CL->head;
	do {
		printf("%s", temp->data);
		temp = temp->link;
		if (temp != CL->head)printf(" -> ");
	} while (temp != CL->head);

	printf("-> NULL )\n");
}

//원형 리스트의 첫번째 노드로 삽입하는 함수
void insertFirstNode(linkedList_h* CL, char* x) {
	listNode* newNode;
	listNode* temp;
	temp = CL->head;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);
	if (CL->head == NULL) { //공백 리스트인 경우
		CL->head = newNode;
		newNode->link = CL->head;
	}
	else { //공백 리스트가 아닌 경우
		while (temp!= CL->head){
			if (temp->link == CL->head) {
				break;
			}
			else {
				temp = temp->link;
			}
		}
		newNode->link = CL->head; //newNode->link에 CL->head를 가르키고 있던값 넣기
		temp->link = newNode; //제일 마지막 노드 newNode 가르키기
		CL->head = newNode; //제일 앞 노드에 newNode 연결
	}
}

void insertMiddleNode(linkedList_h* CL, listNode* pre, char* x) {
	listNode* newNode;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	newNode->link = pre->link;
	pre->link = newNode;
}

void insertLastNode(linkedList_h* CL, char* x) {
	listNode* newNode;
	listNode* temp; //가장 마지막 노드를 찾을 예정
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);
	
	if (CL->head == NULL) { //공백 리스트인 경우
		newNode->link = CL->head;
		CL->head = newNode;
	}
	else { //공백 리스트가 아닌 경우 - > 가장 마지막 노드를 찾기
		temp = CL->head;
		while (temp->link != CL->head) {
			temp = temp->link;
		}
		newNode->link = temp->link;
		temp->link = newNode;	
	}
}

void deleteNode(linkedList_h* CL, listNode*item) {
	listNode* pre;

	pre = CL->head;
	do {
		pre = pre->link;
		if (pre->link == item) {
			break;
		}
	} while (pre != CL->head);
	
	if (CL->head == NULL) {
		return;
	}
	else if (item == CL->head) { //제거하는 노드가 제일 앞 노드인 경우
		CL->head = item->link;
		pre->link = item->link;
	}
	else { //제거하는 노드가 중간 혹은 가장 마지막에 있는 경우
		pre->link = item->link;
	}
	free(item);
}



listNode* searchNode(linkedList_h* CL, char* x) {
	listNode* temp;
	temp = CL->head;
	do {
		if (!strcmp(temp->data, x)) { //값을 발견한 경우
			return temp;
		}
		temp = temp->link;
	} while (temp != CL->head);
}

 
void main() {
	linkedList_h* CL;
	listNode* p; //탐색후 연산할때 사용할 노드

	CL = createLinkedList_h();
	printf("(1) 원형 연결 리스트 생성하기 ! \n");
	
	printf("\n(2) [목] 노드 삽입하기\n");
	insertFirstNode(CL, "목");
	printList(CL);

	printf("\n(3) 제일 앞 노드에 [월] 노드 삽입하기\n");
	insertFirstNode(CL, "월");
	printList(CL);

	printf("\n(4) 제일 마지막에 [금] 삽입하기\n");
	insertLastNode(CL, "금"); 
	printList(CL);

	printf("\n(5) [월] 노드뒤에 [화] 노드 삽입하기\n");
	p = searchNode(CL, "월");
	insertMiddleNode(CL, p, "화"); //p가 가르키고있는 노드 뒤에 화 노드 삽입하기(일반적 함수의 pre 변수 역할) 
	printList(CL);

	printf("\n(6) [화] 노드뒤에 [수] 노드 삽입하기\n");
	p = searchNode(CL, "화");
	insertMiddleNode(CL, p, "수");
	printList(CL);

	printf("\n(7) 제일 마지막에 [일] 삽입하기\n");
	insertLastNode(CL, "일");
	printList(CL);

	printf("\n(8) [금] 노드뒤에 [토] 노드 삽입하기\n");
	p = searchNode(CL, "금");
	insertMiddleNode(CL, p, "토");
	printList(CL);

	printf("\n(9) [월] 노드 지우기\n");
	p = searchNode(CL, "월");
	deleteNode(CL, p);
	printList(CL);

	printf("\n(10) [수] 노드 지우기\n");
	p = searchNode(CL, "수");
	deleteNode(CL, p);
	printList(CL);

	printf("\n(11) [일] 노드 지우기\n");
	p = searchNode(CL, "일");
	deleteNode(CL, p);
	printList(CL);
}