Linked List(3) - Circular Linked List

Circular Linked List는 양쪽 방향으로 엮어 있고, head와 tail또한 엮여 있는 Linked List이다.

주요 연산:

-노드 생성/소멸

-노드 추가

-노드 탐색

-노드 삭제

-노드 삽입

// gcc -o Test_CircularDoublyLinkedList.exe Test_CircularDoublyLinkedList.c CircularDoublyLinkedList.c; ./Test_CircularDoublyLinkedList.exe

#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)
{
    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->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Remove->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);
}

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;
}