[자료구조] 원형 연결 리스트(Circular Linked List) 구현 - C

원형 연결 리스트(Circular Linked List)

 - 마지막 노드가 처음의 노드를 가리키는 형태(마지막 노드가 NULL이 아닌 처음 노드를 가리킨다.)

 

 

 

일반적인 단일 연결 리스트(Single Linked List)와 가장 큰 차이점은 마지막 노드의 link가 NULL이 아닌 처음 노드를 가리킨다는 것이다.

대략적으로 나타낸다면 아래와 같을 것이다.

마지막노드.link = head;

 

 

이제 원형 연결 리스트의 각 함수들에 대하여 알아보겠다.

 

 

1. 원형 리스트의 앞부분에 노드를 삽입

 

위 순서대로 코드를 구현하면 된다.

여기서 신경써야 할 점은 연결 리스트를 탐색하며 마지막 노드를 찾아야 한다는 점이다.

 

void FAddNode(Node **head, int val)
{
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = val;

    Node *temp = *head;

    if (*head == NULL) // 빈 연결리스트인 경우
    {
        *head = newnode;
        newnode->link = newnode;
    }
    else
    {
        while (temp->link != *head) // 마지막 노드를 찾음
        {
            temp = temp->link;
        }
        newnode->link = *head;
        temp->link = newnode;
        *head = newnode;
    }
}

 

연결 리스트가 비어있을 경우에는 노드를 생성하여 link를 본인에게 연결하여 순환되도록 만든다.

 

 

2. 원형 리스트의 뒷부분에 노드를 삽입

 

위 순서대로 코드를 구현하면 된다.

이 경우에도 마지막 노드를 찾아서 temp에 저장해야 한다.

void LAddNode(Node **head, int val)
{
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = val;

    Node *temp = *head;
    if (*head == NULL)
    {
        *head = newnode;
        newnode->link = *head;
    }
    else
    {
        while (temp->link != *head)
        {
            temp = temp->link;
        }
        newnode->link = *head;
        temp->link = newnode;
    }
}

 

연결리스트가 비어있을 경우에는 위와 동일하게 생성하여 자신에게 연결되도록 구현한다.

 

 

3. 원형 연결리스트의 삭제

 

삭제할 위치에 맞게 cur를 이동시킨다.

bef는 cur의 바로 전 노드에 위치한다.

 

int DelNode(Node **head, int val)
{
    Node *bef = *head;
    Node *cur = *head;
    if (*head == NULL)
    {
        printf("삭제할 노드가 없습니다.\n");
        return -1;
    }

    int ret = 0;
    while (cur->data != val)
    {
        bef = cur;
        cur = cur->link;
    }

    if (bef == cur)
    {
        *head = NULL;
    }
    else
    {
        bef->link = cur->link;
        ret = cur->data;
        free(cur);
    }
    return ret;
}

 

 

4. 출력하는 함수

void printNode(Node *head)
{
    Node *temp = head;
    do
    {
        printf("%d-> ", temp->data);
        temp = temp->link;
    } while (temp != head);
    printf("\n");
}

 

 

 

 

이제 전체 실행 코드와 결과를 보여주겠다.

 

전체 코드

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

typedef struct _node
{
    int data;
    struct _node *link;
} Node;

void FAddNode(Node **head, int val)
{
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = val;

    Node *temp = *head;

    if (*head == NULL) // 빈 연결리스트인 경우
    {
        *head = newnode;
        newnode->link = newnode;
    }
    else
    {
        while (temp->link != *head) // 마지막 노드를 찾음
        {
            temp = temp->link;
        }
        newnode->link = *head;
        temp->link = newnode;
        *head = newnode;
    }
}

void LAddNode(Node **head, int val)
{
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = val;

    Node *temp = *head;
    if (*head == NULL)
    {
        *head = newnode;
        newnode->link = *head;
    }
    else
    {
        while (temp->link != *head)
        {
            temp = temp->link;
        }
        newnode->link = *head;
        temp->link = newnode;
    }
}

int DelNode(Node **head, int val)
{
    Node *bef = *head;
    Node *cur = *head;
    if (*head == NULL)
    {
        printf("삭제할 노드가 없습니다.\n");
        return -1;
    }

    int ret = 0;
    while (cur->data != val)
    {
        bef = cur;
        cur = cur->link;
    }

    if (bef == cur)
    {
        *head = NULL;
    }
    else
    {
        bef->link = cur->link;
        ret = cur->data;
        free(cur);
    }
    return ret;
}

void printNode(Node *head)
{
    Node *temp = head;
    do
    {
        printf("%d-> ", temp->data);
        temp = temp->link;
    } while (temp != head);
    printf("\n");
}

int main(void)
{
    Node *head = (Node *)malloc(sizeof(Node));
    head = NULL;
    FAddNode(&head, 3);
    FAddNode(&head, 2);
    FAddNode(&head, 4);
    FAddNode(&head, 1);
    printNode(head);
    LAddNode(&head, 9);
    LAddNode(&head, 7);
    LAddNode(&head, 10);
    printNode(head);
    DelNode(&head, 2);
    printNode(head);
    return 0;
}

 

 

실행 결과