환형 링크드 리스트

 

 

환형 연결 리스트 (Circular Linked List)

이번 글에서는 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키는 환형 연결 리스트(Circular Linked List)를 다룹니다.

일반적인 단일 연결 리스트(Singly Linked List)는 마지막 노드의 NextNode가 NULL을 가리키지만, 환형 연결 리스트는 마지막 노드가 다시 첫 노드를 가리킴으로써 끊김 없이 순환하는 구조가 됩니다.

---

환형 연결 리스트란?

모든 노드가 원처럼 연결되어 있으며, 리스트의 끝이 존재하지 않습니다. 일반 단일 연결 리스트와 달리 어디서든 시작해도 모든 노드를 순회할 수 있다는 점이 특징입니다.

• Tail → Head로 연결됨
• NULL이 없기 때문에 순환 구조를 가짐
• 삽입/삭제 시 마지막 노드 처리에 주의 필요

---

구조체 정의

typedef int ElementType;

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

환형 리스트는 단일 연결 리스트처럼 NextNode만을 사용합니다.

---

노드 생성 및 소멸

노드 생성

Node* CLL_CreateNode( ElementType NewData) {
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->Data = NewData;
    NewNode->PrevNode = NULL;
    NewNode->NextNode = NULL;
    
    return NewNode;
}

노드 소멸

void CLL_DestroyNode(Node* Node) {
    free(Node);
}

---

노드 추가 (Append)

void CLL_AppendNode(Node** Head, Node* NewNode){
    // 헤드 노드가 NULL이면 새로운 노드가 head가 됨
    if((*Head)== NULL) {
        *Head = NewNode;
        (*Head)->NextNode = *Head;
        (*Head)->PrevNode = *Head;
    }
    else {
        // Tail->NextNode는 항상 Head
        Node* Tail = (*Head)->PrevNode;
        
        Tail->NextNode = NewNode;
        NewNode->PrevNode = Tail;
        
        NewNode->NextNode = (*Head);
        (*Head)->PrevNode = NewNode;
    }
}

환형 리스트 핵심은 마지막 노드가 Head를 가리키도록 유지하는 것입니다.

---

노드 탐색 (GetNodeAt)

Node* CLL_GetNodeAt(Node* Head, int Location) {
    if (Head == NULL || Location < 0)
        return NULL;

    int Count = 0;
    Node* Current = Head;

    // 전체 노드 수 계산 (환형 구조 고려)
    do {
        Count++;
        Current = Current->NextNode;
    } while (Current != Head);

    // 실제 순환 인덱스 만들기
    Location = Location % Count;

    // 다시 시작해서 이동
    Current = Head;
    while (Location-- > 0) {
        Current = Current->NextNode;
    }

    return Current;
}

NULL이 존재하지 않으므로 Location만큼 반복하면 됩니다. 단, 무한 루프가 나기 쉬우니 인덱스 검증은 사용자가 따로 해야 합니다. 

의미 없는 루프를 방지하기 위해 노드 수를 카운트하여 효율적으로 개수를 셉니다.

---

노드 삭제 (Remove)

void CLL_RemoveNode(Node** Head, Node* Remove) {
    if(Remove->NextNode == Remove) {
        *Head = NULL;
    }
    else if(*Head == Remove) {
        Node* Tail = Remove->PrevNode;
        Tail->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Tail;
        
        *Head = Remove->NextNode;
 
    }
    else {
        Remove->PrevNode->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Remove->PrevNode;
    }
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
}

핵심 처리:

• 삭제하는 노드가 Head인지 아닌지 구분
• 마지막 노드(Tail)의 NextNode가 여전히 Head를 가리키도록 유지

---

노드 삽입 (InsertAfter)

void CLL_InsertAfter(Node* Current, Node* NewNode) {
    Node* Next = Current->NextNode;

    Current->NextNode = NewNode;
    NewNode->PrevNode = Current;

    NewNode->NextNode = Next;
    Next->PrevNode = NewNode;
}

환형 리스트는 단일 리스트의 삽입과 동일하며, 단지 마지막 노드의 NextNode가 Head를 가리키는 구조가 유지되기만 하면 됩니다.

---

노드 개수 세기

int CLL_GetNodeCount(Node* Head) {
    int Count = 0;
    Node* Current = Head;
    /* 환형구조에서는 Current!=NULL이 영원히 트루
    while(Current != NULL) {
        Current = Current->NextNode;
        Count++;
    }
    */
    do {
        Count++;
        Current = Current->NextNode;
    } while(Current != Head);
    return Count;
}

환형이므로 do-while을 사용하는 게 자연스럽습니다.

---

정리

• 환형 연결 리스트는 마지막 노드가 다시 Head를 가리킴
• NULL이 없기 때문에 순환하며 무한 루프 위험 존재
• 삽입은 쉬움
• 삭제 시 Tail 처리 주의

---

전체코드

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

typedef int ElementType;

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


Node* CLL_CreateNode( ElementType NewData) {
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->Data = NewData;
    NewNode->PrevNode = NULL;
    NewNode->NextNode = NULL;
    
    return NewNode;
}

void CLL_DestroyNode(Node* Node){
    free(Node);
}


void CLL_AppendNode(Node** Head, Node* NewNode){
    // 헤드 노드가 NULL이면 새로운 노드가 head가 됨
    if((*Head)== NULL) {
        *Head = NewNode;
        (*Head)->NextNode = *Head;
        (*Head)->PrevNode = *Head;
    }
    else {
        // Tail->NextNode는 항상 Head
        Node* Tail = (*Head)->PrevNode;
        
        Tail->NextNode = NewNode;
        NewNode->PrevNode = Tail;
        
        NewNode->NextNode = (*Head);
        (*Head)->PrevNode = NewNode;
    }
}

Node* CLL_GetNodeAt(Node* Head, int Location) {
    if (Head == NULL || Location < 0)
        return NULL;

    int Count = 0;
    Node* Current = Head;

    // 전체 노드 수 계산 (환형 구조 고려)
    do {
        Count++;
        Current = Current->NextNode;
    } while (Current != Head);

    // 실제 순환 인덱스 만들기
    Location = Location % Count;

    // 다시 시작해서 이동
    Current = Head;
    while (Location-- > 0) {
        Current = Current->NextNode;
    }

    return Current;
}





void CLL_RemoveNode(Node** Head, Node* Remove) {
    if(Remove->NextNode == Remove) {
        *Head = NULL;
    }
    else if(*Head == Remove) {
        Node* Tail = Remove->PrevNode;
        Tail->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Tail;
        
        *Head = Remove->NextNode;
 
    }
    else {
        Remove->PrevNode->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Remove->PrevNode;
    }
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
}



void CLL_InsertAfter(Node* Current, Node* NewNode) {
    Node* Next = Current->NextNode;

    Current->NextNode = NewNode;
    NewNode->PrevNode = Current;

    NewNode->NextNode = Next;
    Next->PrevNode = NewNode;
}


int CLL_GetNodeCount(Node* Head) {
    int Count = 0;
    Node* Current = Head;
    /* 환형구조에서는 Current!=NULL이 영원히 트루
    while(Current != NULL) {
        Current = Current->NextNode;
        Count++;
    }
    */
    do {
        Count++;
        Current = Current->NextNode;
    } while(Current != Head);
    return Count;
}