환형 링크드 리스트

개요

헤드가 테일을 물고 있는 형태의 링크드 리스트이다. 그것을 제외한 나머지는 링크드 리스트나 더블 링크드 리스트와 다른 것이 없다.

<그림 추가하기>

환형 링크드 리스트의 장점으로는 시작을 알면 끝을 알고, 끝을 알면 시작을 알 수 있다. 이렇게 되면 테일에 접근하는 비용이 거의 없는 것이나 다름 없을정도로 작아져서 DLL_AppendNode() 함수의 성능을 획기적으로 개선시킬 수도 있고, 뒤에서부터 노드를 찾아나가는 노드 탐색 루틴을 구현할 수도 있다.

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

환형 더블 링크드 리스트를 처리하는 코드를 설계할 때는 다음 두 가지 사항을 염두해야한다.
1. 테일은 헤드의 '앞 노드'이다.
2. 헤드는 테일의 '뒷 노드'이다.

노드 추가

비어있는 리스트에 새 노드를 추가할때, 새로운 노드는 헤드가 되고, 헤드의 앞 노드는 헤드가 되며, 헤드의 뒷 노드 역시 헤드 자신이 된다.

/*노드 추가*/
void CDLL_AppendNode (Node** Head, Node* NewNode)
{ 
	/* 헤드 노드가 NULL이라면 새로운 노드가 Head*/
    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가 가리킨다.*/
    }
 }

노드 삭제

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