[자료구조] 환형 링크드 리스트(Circular Linked List/CLL) - 코딩밥상

환형 링크드 리스트란?

Head노드가 Tail노드와 연결되어있는 형태의 링크드 리스트입니다. 이 외에는 더블 링크드 리스트와 동일합니다.

 

 

이렇게되면 시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있습니다. 즉 끝에서 끝으로의 접근의 비용이 대폭 감소합니다.

특히 추가 연산 함수의 성능을 획기적으로 개선할 수 있습니다.

두 가지만 기억합시다.

• Tail노드는 Head노드의 '이전 노드'입니다.
• Head노드는 Tail노드의 '다음 노드'입니다.

사실상 이 두 가지가 더블 링크드 리스트와의 차이점입니다.

---

 

주요 연산(ADT)

DLL와 함수 구현이 다른 부분만 적어보겠습니다. 이 외의 함수들은 구현이 정말 비슷하거나 심지어 동일합니다.

 

• 노드 추가 연산

void CDLL_AppendNode(Node** Head, Node* NewNode){    //노드 추가
    if((*Head) == NULL){    //헤드 노드가 NULL이면(기존 노드가 없으면), 새로운 노드가 Head
        *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;
    }
}

 

추가되는 노드가 Tail이 되기때문에 앞서 기억해야할 두가지 특성을 새로 관리해줍니다.

---

• 노드 삭제 연산

void CDLL_RemoveNode(Node** Head, Node* Remove){     //노드 삭제
    if (*Head == Remove){   //Head를 삭제할 경우
        if((*Head) != NULL){
            (*Head)->PrevNode->NextNode = Remove->NextNode;
            (*Head)->NextNode->PrevNode = Remove->PrevNode;
            
            *Head = Remove->NextNode;
            
            Remove->NextNode = NULL;
            Remove->PrevNode = NULL;
        }
    }
    else{
        Remove->PrevNode->NextNode = Remove->NextNode;
        Remove->NextNode->PrevNode = Remove->PrevNode;
        
        Remove->PrevNode = NULL;
        Remove->NextNode = NULL;
    }
}

 

이미 추가연산을 통해 Tail과 Head를 연결해주었기때문에 DLL와 크게 다른점은 없습니다.

---

• 노드 개수 세기 연산(번외)

int CDLL_GetNodeCount(Node* Head){    //노드 갯수 세기
    int count = 0;
    Node* Current = Head;
    
    while(Current != NULL){ //Head부터 Tail까지 카운트 업
        Current = Current->NextNode;
        count++;
        
        if(Current == Head) break;
    }
    return count;
}

 

DLL과 다르게 종료조건을 써주지 않으면 계속해서 순환하기때문에 꼭 써줘야합니다.

 

---

 

DLL복습하기

2022.12.24 - [자료구조/리스트(List)] - [자료구조] 더블 링크드 리스트(DoublyLinkedList/DLL) - 코딩밥상

[자료구조] 더블 링크드 리스트(DoublyLinkedList/DLL) - 코딩밥상