환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List)

환형 링크드 리스트 (Circular Linked List)

환형 링크드리스트(Circular Linked List)는 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트입니다. 이를 제외하고는 링크드 리스트나 더블 링크드 리스트와 다른 것이 없습니다. 더블링크드 리스트, 혹은 링크드 리스트를 이용하여 아래와 같이 환형 링크드 리스트를 만들 수 있습니다. 테일의 다음 노드 포인터가 헤드를 가리키게 하면 됩니다.

환형 링크드 리스트

헤드와 테일을 연결하여 얻을 수 있는 장점은 무엇일까요? "시작을 알면 끝을 알고 끝을 알면 시작을 알 수 있다"는 점입니다. 예를 들어 더블 링크드 리스트를 환형으로 구현하면 헤드의 앞 노드가LL_AppendNode() 함수의 성능을 획기적으로 개선시킬 수도 있고, 뒤에서부터 노드를 찾아나가는 노드 탐색 루틴을 구현할 수도 있습니다.

환형 더블 링크드 리스트의 주요 연산

환형 더블 링크드 리스트를 처리하는 코드를 설계할 때에는 다음 두 가지 사항을 염두해야 합니다.

• 테일은 헤드의 '앞 노드' 이다.
• 헤드는 테일의 '뒷 노드' 이다.

환형 더블 링크드 리스트와 더블 링크드 리스트의 차이는 위 두 가지 사항이 사실 상 전부라고 할 수 있습니다.

환형 더블 링크드 리스트에서 살펴볼 주요 연산은 다음 두 가지 입니다.

• 노드 추가
• 노드 삭제

노드 추가

비어있는 리스트에 새 노드를 추가하는 과정을 생각해봅시다. 새로운 노드는 헤드가 되고, 헤드의 앞 노드는 헤드가 되며, 헤드의 뒷 노드 역시 헤드 자신이 됩니다.

그리고 리스트가 비어있지 않은 경우의 추가 연산 과정은 "테일 노드 뒤에 새 노드를 붙인다"라기 보다는 "테일과 헤드 사이에 새 노드를 삽입한다"라고 생각하는 것이 이해하기 쉽습니다.

/* 노드 추가 */
void CDLL_AppendNode(Node** Head, Node* NewNode)
{
    /* 헤드 노드가 NULL이라면 새로운 노드가 Head */
    if ( (*Head) == NULL ) 
    {
        *Head = NewNode;
        (*Head)->NextNode = *Head;
        (*Head)->PrevNode = *Head;
    } 
    else
    {
        /* 테일과 헤드 사이에 NewNode를 삽입한다. */
        Node* Tail = (*Head)->PrevNode;

        Tail->NextNode->PrevNode = NewNode;
        Tail->NextNode = NewNode;

        NewNode->NextNode = (*Head);
        NewNode->PrevNode = Tail; /* 기존의 테일을 새로운 */
                                  /* 테일의 PrevNode가 가리킨다.*/
    }
}

노드 삭제

노드 삭제 연산 역시 테일의 헤드가 연결되어 있는 점에 주의해야 하지만 더블 링크드 리스트 버전과 비교해서 크게 달라질 것은 없습니다.

/* 노드 제거 */
void CDLL_RemoveNode(Node** Head, Node* Remove)
{
    if ( *Head == Remove )
    {
        (*Head)->PrevNode->NextNode = Remove->NextNode;
        (*Head)->NextNode->PrevNode = Remove->PrevNode;

        *Head = Remove->NextNode;

        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }
    else
    {
        Node* Temp = Remove;

        Remove->PrevNode->NextNode = Temp->NextNode;
        Remove->NextNode->PrevNode = Temp->PrevNode;

        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }    
}

환형 더블 링크드 리스트 예제 프로그램

쉽게 느껴질 수 있지만 이를 쉽게 받아들일 수 있는 것은 링크드 리스트와 더블 링크드 리스트를 공부하면서 지식을 쌓아왔기 때문입니다. 환형 더블 링크드 리스트 예제 프로그램은 3개의 파일로 이루어져 있습니다. 그 중에 두 개는 환형 더블 링크드 리스트의 기본 연산 함수를 정의하는 CircularDoublyLinkedList.h와 CircularDoublyLinkedList.c이고, 나머지 하나는 이들 함수를 테스트하는 Test_CircularDoublyLinkedList.c 입니다.

/******************************/
/* CircularDoublyLinkedList.h */
/******************************/

#ifndef CIRCULAR_DOUBLY_LINKEDLIST_H
#define CIRCULAR_DOUBLY_LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
    struct tagNode* PrevNode;
    struct tagNode* NextNode;
} Node;

/* 함수 원형 선언 */
Node* CDLL_CreateNode(ElementType NewData);
void  CDLL_DestroyNode(Node* Node);
void  CDLL_AppendNode(Node** Head, Node* NewNode);
void  CDLL_InsertAfter(Node* Current, Node* NewNode);
void  CDLL_RemoveNode(Node** Head, Node* Remove);
Node* CDLL_GetNodeAt(Node* Head, int Location);
int   CDLL_GetNodeCount(Node* Head);

#endif CIRCULAR_DOUBLY_LINKEDLIST_H

/******************************/
/* CircularDoublyLinkedList.c */
/******************************/

#include "CircularDoublyLinkedList.h"

/* 노드 생성 */
Node* CDLL_CreateNode(ElementType NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = NewData;
    NewNode->PrevNode = NULL;
    NewNode->NextNode = NULL;

    return NewNode;
}

/* 노드 소멸 */
void CDLL_DestroyNode(Node* Node)
{
    free(Node);
}

/* 노드 추가 */
void CDLL_AppendNode(Node** Head, Node* NewNode)
{
    /* 헤드 노드가 NULL이라면 새로운 노드가 Head */
    if ( (*Head) == NULL ) 
    {
        *Head = NewNode;
        (*Head)->NextNode = *Head;
        (*Head)->PrevNode = *Head;
    } 
    else
    {
        /* 테일과 헤드 사이에 NewNode를 삽입한다. */
        Node* Tail = (*Head)->PrevNode;

        Tail->NextNode->PrevNode = NewNode;
        Tail->NextNode = NewNode;

        NewNode->NextNode = (*Head);
        NewNode->PrevNode = Tail; /* 기존의 테일을 새로운 */
                                  /* 테일의 PrevNode가 가리킨다. */
    }
}

/* 노드 삽입 */
void CDLL_InsertAfter(Node* Current, Node* NewNode)
{
    NewNode->NextNode = Current->NextNode;
    NewNode->PrevNode = Current;

    if ( Current->NextNode != NULL )
    {
        Current->NextNode->PrevNode = NewNode;
        Current->NextNode = NewNode;
    }
}

/* 노드 제거 */
void CDLL_RemoveNode(Node** Head, Node* Remove)
{
    if ( *Head == Remove )
    {
        (*Head)->PrevNode->NextNode = Remove->NextNode;
        (*Head)->NextNode->PrevNode = Remove->PrevNode;

        *Head = Remove->NextNode;

        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }
    else
    {
        Node* Temp = Remove;

        Remove->PrevNode->NextNode = Temp->NextNode;
        Remove->NextNode->PrevNode = Temp->PrevNode;

        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }    
}

/* 노드 탐색 */
Node* CDLL_GetNodeAt(Node* Head, int Location)
{
    Node* Current = Head;

    while ( Current != NULL && (--Location) >= 0)
    {
        Current = Current->NextNode;
    }

    return Current;
}

/* 노드 수 세기*/
int CDLL_GetNodeCount(Node* Head)
{
    unsigned int  Count = 0;
    Node*         Current = Head;

    while ( Current != NULL )
    {
        Current = Current->NextNode;
        Count++;

        if ( Current == Head )
            break;
    }

    return Count;
}

void PrintNode(Node* _Node)
{
    if ( _Node->PrevNode == NULL )
        printf("Prev: NULL");
    else
        printf("Prev: %d", _Node->PrevNode->Data);

    printf(" Current: %d ", _Node->Data);

    if ( _Node->NextNode == NULL )
        printf("Next: NULL\n");
    else
        printf("Next: %d\n", _Node->NextNode->Data);
}

/***********************************/
/* Test_CircularDoublyLinkedList.c */
/***********************************/

#include "CircularDoublyLinkedList.h"

int main( void )
{
    int   i       = 0;
    int   Count   = 0;
    Node* List    = NULL;
    Node* NewNode = NULL;
    Node* Current = NULL;

    /* 노드 5개 추ㅏㄱ*/
    for ( i = 0; i<5; i++ )
    {
        NewNode = CDLL_CreateNode( i );
        CDLL_AppendNode( &List,NewNode );
    }

    /* 리스트 출력 */
    Count = CDLL_GetNodeCount( List );
    for ( i = 0; i<Count; i++ )
    {
        Current = CDLL_GetNodeAt( List, i );
        printf( "List[%d] : %d\n", i, Current->Data );
    }

    /* 리스트의 세 번째 칸 뒤에 노드 삽입*/
    printf( "\nInserting 3000 After [2]...\n\n" );

    Current = CDLL_GetNodeAt( List, 2 );
    NewNode = CDLL_CreateNode( 3000 );
    CDLL_InsertAfter( Current, NewNode );

    printf( "\nRemoving Node at 2...\n" );
    Current = CDLL_GetNodeAt( List, 2 );
    CDLL_RemoveNode( &List, Current );
    CDLL_DestroyNode( Current );

    /* 리스트 출력 */
    /* (노드 수의 2배 만큼 루프를 돌며 환형임을 확인한다.) */
    Count = CDLL_GetNodeCount( List );
    for ( i = 0; i<Count*2; i++ )
    {
        if ( i == 0 )
            Current = List;
        else
            Current = Current->NextNode;

        printf( "List[%d] : %d\n", i, Current->Data );
    }

    /* 모든 노드를 메모리로 제거 */
    printf( "\nDestroying List...\n" );

    Count = CDLL_GetNodeCount( List );

    for ( i = 0; i<Count; i++ )
    {
        Current = CDLL_GetNodeAt( List, 0 );

        if ( Current != NULL ) 
        {
            CDLL_RemoveNode( &List, Current );
            CDLL_DestroyNode( Current );
        }
    }

    return 0;
}