[C언어와 함께 자료구조를] 환형연결리스트 (Circular Linked List)

환형연결리스트(또는 원형연결리스트 Circular Linked List)는 단순연결리스트(Simple Linked List)의 Tail노드가 Head노드를 가리키고 있는 구조로 머리가 꼬리를 문 뱀모양의 둥근 모양을 하고 있습니다.  환형연결리스트의 연산은 단순연결리스트의 것과 비슷합니다. 다른 것은 환형연결리스트는 Tail이라는 개념이 없다는 것 뿐입니다.

환형 리스트 구조

해결하려는 문제에 따라 자연스럽게 환형연결리스트를 사용해야 되는 경우가 있습니다. 

예를들어, 어떤 다각형의 변은 그 자체로 하나의 루프를 형성하므로 다각형의 꼭지점을 환형리스트의 노드로 표현하는것이 적절한 방법입니다.

여기서는 환형연결리스트의 대표적인 "요셉의 문제"를 코드로 알아보도록 하겠습니다. "요셉의 문제"는 A부터 J까지의 10명의 사람이 시계 방향으로 둥글게 앉아 있다고 할때, A부터 시작하여 4명간격으로 사람을 원에서 뽑아서 순서를 출력하는 것입니다. 아래의 프로그램은 키보드로 사람의 수 n과 간격 step을 입력받아 사람의 수 만큼의 환형 연결리스트를 구성합니다. 그 다음 처음의 노드에서 step만큼 이동한 다음 그위치의 노드를 삭제하는 식으로 반복하여 리스트에 노드가 남지 않을 때까지 수행합니다.

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

typedef struct _node {
    char key;
    struct _node *next;
} node;

node *head;

/*
 * 1부터 K까지의 값을 갖는 환형연결리스트 구성
 */
void insert_nodes(int k)
{
    node *t;
    int i;

    t = (node *)malloc(sizeof(node));
    t->key = 'A';

    head = t; /* 연결리스트의 Head */

    for (i=2; i <= k; i++) {
        t->next = (node *)malloc(sizeof(node));
        t = t->next;
        t->key = 'A'+i;
    }

    t->next = head; /* 마지막을 Head에 물림 */
}

/*
 * t 다음 노드를 삭제함
 */
void delete_after (node *t)
{
    node *s;
    s = t->next;
    t->next = t->next->next;
    free(s);
}

void josephus (int n, int m)
{
    node *t;
    int i;

    insert_nodes(n);

    t = head;
    print ("\nAnswer : ");

    while (t != t->next) {
        for (i=0; i < m-1; i++)
            t = t->next;
        printf ("%c ", t->next->key);
        delete_after(t);
    }
    printf ("%c", t->key);
}

void main()
{
    int n, m;
    printf("\n If you want to quit, enter 0 value");

    while (1) {
        printf ("\n Enter Person number and step number -> ");
        scanf ("%d %d", &n, &m);
        if (n == 0 || m == 0) {
            return;
        }

        if (n < 0 || m < 0) {
            printf ("\n Invalid input number, enter plus values");
            continue;
        }

        josephus (n, m);
    }
}

* 참고자료 : C언어와 함께 자료구조를 공부하자/장덕문외3인/가남사
                 C로 배우는 알고리즘/이재규/세화