환형 연결 리스트(Circular Linked List) - C언어 구현

환형 연결 리스트

• 노드 추가 시 tail 찾기 위해 순환할 필요 없음(head->prevNode == tail)
• 단일 연결 리스트로 구현 시 tail의 다음 노드 포인터가 head를 가리킴
• 이중 연결 리스트로 구현 시
  • tail의 다음 노드 포인터가 head를 가리킴
  • head의 이전 노드 포인터가 tail을 가리킴

이중 연결 리스트로 구현함

---

0. 노드 구조체

typedef struct Node {
    int data;
    struct Node* prevNode;
    struct Node* nextNode;
} Node;

---

1. 노드 생성

Node* CreateNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prevNode = newNode;
    newNode->nextNode = newNode;
    return newNode;
}

---

2. 리스트 검사

int IsEmpty(Node* head) {
    if(head == NULL) return 1;
    return 0;
}

---

3. 노드 추가

void AppendNode(Node** head, Node* node) {
    if(IsEmpty(*head)) *head = node;
    node->prevNode = (*head)->prevNode;
    (*head)->prevNode->nextNode = node;
    (*head)->prevNode = node;
    node->nextNode = *head;
}

---

4. 노드 검색

Node* SearchNode(Node* head, int data) {
    if(!IsEmpty(head)){
	Node* current = head;
	do {
	    if(current->data == data) return current;
	    current = current->nextNode;
	} while(current != head);
    }
    return NULL;
}

---

5. 노드 삭제

Node* RemoveNode(Node** head, int data) {
    Node* target = SearchNode(*head, data);
    if(!IsEmpty(target)){
	if(target->nextNode == target) *head = NULL;
	else {
	    if(target == *head) *head = target->nextNode;
	    target->nextNode->prevNode = target->prevNode;
	    target->prevNode->nextNode = target->nextNode;
        }
        target->nextNode = target;
        target->prevNode = target;
        return target;
    }
    return NULL;
}

void DestroyNode(Node* node) {
    free(node);
}

---

6. 리스트 출력

void PrintList(Node* head) {
    if(!IsEmpty(head)){
	Node* curr = head;
	do {
	    printf("[%p] %p %d %p\n", curr, curr->prevNode, curr->data, curr->nextNode);
	    curr = curr->nextNode;
	} while(curr != head);
    }
}

---

7. 리스트 삭제

void DestroyList(Node** head) {
    if(!IsEmpty(*head)){
	Node* remove = (*head)->nextNode;
	Node* next = remove;
	while(remove != *head) {
	    next = next->nextNode;
	    free(remove);
	    remove = next;
	}
	free(remove);
	*head = NULL;
    }
}

---

8. 예시

int main(void)
{
    Node* head = NULL;
    Node* newNode = NULL;

    newNode = CreateNode(10);
    AppendNode(&head, newNode);
    newNode = CreateNode(20);
    AppendNode(&head, newNode);
    newNode = CreateNode(30);
    AppendNode(&head, newNode);
    PrintList(head);
    printf("\n");

    DestroyNode(RemoveNode(&head, 10));
    PrintList(head);
    printf("\n");
    DestroyNode(RemoveNode(&head, 30));
    PrintList(head);
    printf("\n");
    DestroyNode(RemoveNode(&head, 20));
    PrintList(head);
    printf("\n");

    newNode = CreateNode(10);
    AppendNode(&head, newNode);
    DestroyList(&head);
    return 0;
}