자료구조 - 환형 더블 링크드 리스트(Circle Doubly Linked List)

환형 더블 링크드 리스트의 노드는 더블 링크드 리스트의 노드와 같다.

단지 노드가 구성하고 있는 리스트의 구성이 다를 뿐이다.

더블 링크드 리스트에서 추가 된 점은

1.헤드노드의 앞 노드는 테일노드

2.테일노드의 뒷 노도는 헤드노드 

 

 

typedef struct tagNode{ int Data; struct tagNode* PrevNode; //이전 노드를 가리키는 포인터 struct tagNode* NextNode; //다음 노드를 가리키는 포인터 }Node;

 

 

Node* CDLL_CreatNode(int 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 = *Head; (*Head)->PrevNode = *Head; } else{ Node* Tail = (*Head)->PrevNode; Tail->NextNode->PrevNode = NewNode; Tail->NextNode = NewNode; NewNode->NextNode = (*Head); NewNode->PrevNode = Tail; } }

 

  

 

void CDLL_GetNodeAt(Node* Head, int Location){ Node* Current = Head; while(Location--) Current = Current->NextNode; return Current; }

  

 

void CDLL_RemoveNode(Node** Head, Node* Remove){ if(*Head == Remove){ (*Head)->PrevNode->NextNode = Remove->NextNode; (*Head)->NextNode->PrevNode = Remove->PrevNode; *Head = Remove->NextNode; } else{ Node* Temp = Remove; Remove->PrevNode->NextNode = Temp->NextNode; Remove->NextNode->PrevNode = Temp->PrevNode; } }

이 함수는 약간 문제가 있다.

환형 더블 링크 리스트에서는 노드가 하나일 때 그 노드의 테일과 헤드포인터는 자기자신을 가리키기 때문에

 

리스트에 노드가 하나밖에 없고 그 노드가 제거될때

특히 첫번째 if문에서 *Head는 마지막에도 제거할 노드의 주소(Remove)를 가리킨다.

 

그럼 나중에 노드를 제거(CDD_DestroyNode())하더라도

리스트는 NULL이 되지 않고 제거된 자리(빈 공간)를 가리키게 된다.

 

내가 보는 책이 입문자를 배려한 책이라서 그런지 예외부분에서는 허술한 것 같다.

 

 

void CDLL_InsertAfter(Node* Current, Node* NewNode){ NewNode->NextNode = Current->NextNode; NewNode->PrevNode = Current; Current->NextNode->PrevNode = NewNode; Current->NextNode = NewNode; /* 더블 링크 리스트    if(Current->NextNode != NULL){       Current->NextNode->PrevNode = NewNode;       Current->NextNode = NewNode;    }    */ }

환형 더블 링크 리스트는 포인터가 NULL인 노드가 없으므로

더블 링크 리스트 처럼 따로 테일노드인지(NULL) 확인할 필요 없다.

  

 

int CDLL_GetNodeCount(Node *Head){ unsigned int Count = 0; Node* Current = Head->NextNode; while(Current != Head){ Current = Current->NextNode; Count++; if(Current == Head) break; } return Count; }

환형 더블 링크드 리스트는 개수를 셀 때

헤드에서 루프를 돌려 헤드가 나오면 break 하는 것으로 한다.