[C언어] Circular Doubly Linked List

1. 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); // 노드 카운팅 
void PrintNode(Node* _Node);//노드 출력
 
 
 
#endif

2. 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);
}
 
/*노드 추가(일부코드 추가 from DLL)*/
void CDLL_AppendNode(Node** Head,Node* NewNode){
 
    if(*Head==NULL){
        *Head=NewNode;
        (*Head)->PrevNode=*Head;
        (*Head)->NextNode=*Head;
    }
    else{
        /*테일과 헤드 사이에 노드삽입 */
        Node* Tail=(*Head)->PrevNode;
 
        Tail->NextNode->PrevNode=NewNode;
        Tail->NextNode=NewNode;
        
        NewNode->NextNode=*Head;
        NewNode->PrevNode=Tail;
    }
}
 
/*노드 삽입*/
void CDLL_InsertAfter(Node* Current,Node* NewNode){
    NewNode->PrevNode=Current;
    NewNode->NextNode=Current->NextNode;
 
    if(Current->NextNode!=NULL){
        Current->NextNode->PrevNode=NewNode;
    }
    Current->NextNode=NewNode;
}
 
 
/*노드 제거(일부코드 추가 from DLL)*/
void CDLL_RemoveNode(Node** Head,Node* Remove){
    if(*Head==Remove){
        
        (*Head)->PrevNode->NextNode=Remove->NextNode;
        (*Head)->NextNode->PrevNode=Remove->PrevNode;
 
        *Head=Remove->NextNode;
 
        Remove->NextNode=NULL;
        Remove->PrevNode=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;
}
 
/*노드 수 세기(일부코드 추가 From DLL*/
int CDLL_GetNodeCount(Node* Head){
    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);
    }
}
 
 

3. Test_CircularDoublyLinkedList.c (테스트 코드)

//테스트//
 
#include "CircularDoublyLinkedList.h"
 
int main(){
    int i=0,Count=0;
    Node* List=NULL;
    Node* Current=NULL;
    Node* NewNode=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);
    }
 
    /*리스트의 3번째칸 뒤에 노드 삽입*/
    printf("\nInserting 3000 After [2]....\n\n");
 
    Current=CDLL_GetNodeAt(List,2);
    NewNode=CDLL_CreateNode(3000);
    CDLL_InsertAfter(Current,NewNode);
 
    /*리스트 출력(일부 코드 추가 from DLL)*/
    /*노드수의 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);
    }
    //Current=CDLL_GetNodeAt(List,3);
    //PrintNode(Current);
 
    /*모든 노드를 메모리에서 제거*/
    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;
}

실행결과