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 GetNodeCount(Node* Head);

#endif

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) {
    if (*Head == NULL) {
        *Head = NewNode; //(*Head)->NextNode = NewNode 가 아닌 (*Head) = NewNode
        (*Head)->PrevNode = *Head;
        (*Head)->NextNode = *Head;
    }
    else {
        //테일과 헤드 사이에 NewNode를 삽입한다.
        Node* Tail = (*Head)->PrevNode;

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

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

    }
}

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

    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->NextNode = NULL;
        Remove->PrevNode = NULL;
    }
    else {
        Node* Temp = Remove;

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

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

//노드 탐색
Node* CDLL_GetNodeAt(Node* Head, int Location) {
    Node* Current = Head;
    while (Current != NULL && (--Location) >= 0) {
        Current = Current->NextNode;
    }
    return Current;

}

//노드 수 세기
int GetNodeCount(Node* Head) {
    int Count = 0;
    Node* Current = Head;
    Node* Tail = Head->PrevNode;
    while (Current != Tail) {
        Current = Current->NextNode;
        Count++;
    }
    Count++;
    return Count;
}

Test_CircularDoublyLinkedList.c

#include "CircularDoublyLinkedList.h"

void printList(Node* List,int* Circle) {
    Node* Current;
    int Count = GetNodeCount(List);
    for (int i = 0; i < Count*(*Circle); i++) {
        Current = CDLL_GetNodeAt(List, i);
        printf("List[%d] : %d\n", i%6, Current->Data);
    }
}

int main(void) {
    int i = 0;
    int Count = 0;
    int Circle = 1; //print시 loop할 횟수
    Node* List = NULL;
    Node* NewNode = NULL;
    Node* Current = NULL;

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

    //리스트 출력
    printList(List, &Circle);

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

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

    //리스트 출력
    //노드 수의 2배만큼 루프를 돌며 환형임을 확인한다.
    Circle = 2;
    printList(List,&Circle);

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

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

실행 결과

728x90