[자료구조] 환형 링크드 리스트 구현

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

• a.k.a 원형 연결 리스트
• 싱글 링크드 리스트나 더블 링크드 리스트와 노드 구성은 동일하지만, 헤드와 테일이 연결되어 있음
• 테일의 nextNode는 헤드를 가리키고, 헤드의 prevNode는 테일을 가리킴
• 리스트의 시작과 끝을 미리 알 수 있다 (시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있다)
  • DLL의 삽입 함수와 같은 부분의 성능을 많이 개선할 수 있다. (테일에 접근하는 비용이 거의 없으므로)
  • 노드를 뒤에서 역순으로 찾아나갈 수 있는 탐색도 구현할 수 있다.

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

• 추가 / 삭제 연산 이외 함수들은 링크드 리스트와 더블 링크드 리스트 함수와 동일함

노드 추가 연산

• 비어있는 리스트에 새 노드를 추가하면 이 노드는 헤드가 되고, 헤드의 이전 노드는 헤드, 다음 노드 역시 헤드 자신이 됨
• 리스트가 비어 있지 않은 경우 테일과 헤드 사이에 새 노드를 삽입한다 라고 볼 수 있다

void CDLL_AppendNode(Node** head, Node* newNode)
{
    // 헤드 노드가 NULL이라면 새로운 노드가 헤드가 됨
    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가 기존의 테일을 가리킴
    }
}

노드 삭제 연산

• 테일과 헤드가 연결되어 있다는 사실만 주의하면 DLL과 거의 동일하다

void CDLL_RemoveNode(Node** head, Node* removeNode)
{
    if(*head == removeNode) {
        (*head)->prevNode->nextNode = removeNode->nextNode;
        (*head)->nextNode->prevNode = removeNOde->prevNode;

        *head = removeNode->nextNode;

        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
    else {
        removeNode->prevNode->nextNode = removeNode->nextNode;
        removeNode->nextNode->prevNode = removeNode->prevNode;

        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
}

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

#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* newHead);    // 노드 추가
void CDLL_InsertAfter(Node* current, Node* newNode); // 노드 삽입
void CDLL_InsertNewHead(Node** head, Node* newHead); // 헤드 삽입
void CDLL_RemoveNode(Node** head, Node* removeNode);     // 노드 삭제
Node* CDLL_GetNodeAt(Node* head, int location);      // 노드 탐색
int CDLL_GetNodeCount(Node* head);                   // 노드 개수

int main()
{
    int i = 0;
    int count = 0;
    Node* list = NULL;
    Node* newNode = NULL;
    Node* current = NULL;

    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("Removeing Node at 2...\n");

    current = CDLL_GetNodeAt(list, 2);
    CDLL_RemoveNode(&list, current);
    CDLL_DestroyNode(current);

    count = CDLL_GetNodeCount(list);

    for(i = 0; i < count; i++) {
        if(i == 0) {
            current = list;
        }
        else {
            current = current->nextNode;
        }

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

    // 모든 노드 소멸
    printf("Destroying List\n\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;
}

// 노드 생성
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이라면 새로운 노드가 헤드가 됨
    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가 기존의 테일을 가리킴
    }
}

// 노드 탐색
Node* CDLL_GetNodeAt(Node* head, int location)
{
    Node* current = head;

    while(current != NULL && (--location) >= 0) {
        current = current->nextNode;
    }

    return current;

}

// 노드Node
void CDLL_RemoveNode(Node** head, Node* removeNode)
{
    if(*head == removeNode) {
        *head = removeNode->nextNode;

        if((*head) != NULL) {
            (*head)->prevNode = NULL;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
    else {
        Node* temp = removeNode;

        // 삭제할 노드의 prevNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->prevNode != NULL) {
            removeNode->prevNode->nextNode = temp->nextNode;
        }

        // 삭제할 노드의 nextNode 포인터가 가리키던 노드를 이전 노드의 nextNode 포인터가 가리키게 변경
        if(removeNode->nextNode != NULL) {
            removeNode->nextNode->prevNode = temp->prevNode;
        }

        // 삭제할 노드의 가리키고 있는 값 초기화
        removeNode->prevNode = NULL;
        removeNode->nextNode = NULL;
    }
}

// 노드 삽입
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;
    }
}

// 노드 개수
int CDLL_GetNodeCount(Node* head)
{
    int count = 0;
    Node* current = head;

    while(current != NULL) {  
        current = current->nextNode;
        count++;
    }

    return count++;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)