[C] 원형 연결리스트 Circular Linked List

1. 원형 연결 리스트란?

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 구조를 가진 리스트예요.
즉, 리스트의 끝이 다시 처음으로 연결되어 순환 구조를 이루고 있어요.

원형 연결 리스트의 종류
1. 단일 원형 연결 리스트 (Singly Circular Linked List) → 마지막 노드의 next가 첫 번째 노드를 가리켜요.
2. 이중 원형 연결 리스트 (Doubly Circular Linked List) → next뿐만 아니라 prev도 원형으로 연결되어 있어요.

원형 연결 리스트는 큐(Queue) 구현, 프로세스 스케줄링, 버퍼 관리 같은 곳에서 많이 사용돼요.

⸻

2. 단일 원형 연결 리스트(Singly Circular Linked List) 구조

기본적인 단일 원형 연결 리스트의 노드 구조를 먼저 만들어볼게요.

#include <stdio.h>
#include <stdlib.h>

// 원형 연결 리스트의 노드 구조
typedef struct Node {
    int data;
    struct Node* next;
} Node;

이제 새로운 노드를 생성하는 함수를 만들어볼게요.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // 원형 구조를 유지하기 위해 자기 자신을 가리킴
    return newNode;
}

⸻

3. 원형 연결 리스트에 노드 추가하기

원형 연결 리스트에서 노드를 추가하는 방법을 알아볼게요.

void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);

    if (*head == NULL) { // 리스트가 비어 있다면
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != *head) { // 마지막 노드 찾기
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->next = *head; // 마지막 노드가 다시 첫 번째 노드를 가리킴
}

⸻

4. 원형 연결 리스트 출력하기

원형 연결 리스트는 NULL이 없기 때문에, 첫 번째 노드로 돌아오면 순회가 끝난 것을 알 수 있어요.

void printList(Node* head) {
    if (head == NULL) return;

    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head); // 다시 첫 번째 노드로 돌아오면 종료

    printf("(head)\n"); // 리스트가 원형임을 표시
}

테스트 코드

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);

    printf("원형 연결 리스트 출력: ");
    printList(head); // 출력: 10 -> 20 -> 30 -> (head)

    return 0;
}

⸻

5. 특정 노드 삭제하기

원형 연결 리스트에서 특정 노드를 삭제하는 함수도 만들어볼게요.

void deleteNode(Node** head, int key) {
    if (*head == NULL) return;

    Node *temp = *head, *prev = NULL;

    // 첫 번째 노드를 삭제하는 경우
    if (temp->data == key && temp->next == *head) {
        free(temp);
        *head = NULL;
        return;
    }

    // 삭제할 노드 찾기
    while (temp->data != key) {
        prev = temp;
        temp = temp->next;

        // 노드를 못 찾았을 경우
        if (temp == *head) return;
    }

    // 중간 노드 삭제
    prev->next = temp->next;

    // 첫 번째 노드를 삭제하는 경우, 헤드를 변경
    if (*head == temp) {
        *head = temp->next;
    }

    free(temp);
}

테스트 코드

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);
    printList(head);  // 출력: 10 -> 20 -> 30 -> (head)

    deleteNode(&head, 20);
    printList(head);  // 출력: 10 -> 30 -> (head)

    return 0;
}

⸻

6. 이중 원형 연결 리스트(Doubly Circular Linked List) 구현

이제 이중 원형 연결 리스트도 만들어볼게요.
이중 원형 연결 리스트는 prev 포인터가 추가되어 양방향으로 이동할 수 있어요.

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

이중 원형 연결 리스트에서 노드 추가 함수는 이렇게 만들 수 있어요.

void appendNode(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    if (*head == NULL) {
        newNode->next = newNode;
        newNode->prev = newNode;
        *head = newNode;
        return;
    }

    Node* last = (*head)->prev;

    newNode->next = *head;
    (*head)->prev = newNode;

    newNode->prev = last;
    last->next = newNode;
}

⸻

7. 원형 연결 리스트의 활용과 한계

✅ 장점:
• 리스트의 끝과 처음이 연결되어 있어서 순환 구조를 구현하기 좋아요.
• NULL이 없어서 리스트의 처음과 끝을 구분할 필요가 없어요.
• 버퍼(Queue), 게임 캐릭터 순환, 프로세스 스케줄링 등에 활용돼요.

❌ 단점:
• NULL이 없어서 종료 조건을 잘 처리해야 해요.
• 삽입/삭제 시 포인터를 조작하는 과정이 더 까다로울 수 있어요.

⸻

정리
1. 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 순환 구조예요.
2. 단일 원형 리스트는 next 포인터만 사용하지만, 이중 원형 리스트는 prev도 사용해요.
3. 일반 연결 리스트보다 버퍼, 프로세스 스케줄링, 라운드 로빈 방식 등에 적합해요.
4. NULL이 없기 때문에 처음과 끝을 구분하는 로직을 신경 써야 해요.

⸻

이제 원형 연결 리스트도 완벽하게 정리했어요!
다음으로 스택(Stack)과 큐(Queue) 를 다뤄볼까요?