[자료구조] 리스트 - 03 . 환형 링크드 리스트

[환형 링크드 리스트]

[환형 링크드 리스트]

=>환형 링크드 리스트는 헤드의 앞 노드는 테일이며 테일의 뒷노드는 헤드이다.

=>장점은 테일에 접근하는 비용이 거의 없는 것이 되어 , 노드를 추가할때 성능의 향상이 가능하다.

 

[환형 링크드 리스트 주요 연산]

=>환형 링크드 리스트의 주요 연산시 가장 신경 쓸 부분은 다음과 같다.

• 테일은 헤드의 "앞노드"이다 .
• 헤드는 테일의 "뒷노드"이다.

주요한 연산 추가 ,삭제를 살펴보겠다.이외의 연산은 DLL에서 본 것과 동일하여 생략하려 한다.

 

[노드 추가]

 

void CDLL_AppendNode(Node** Head,Node* NewNode)
{

    if((*Head)==NULL)	//헤드노드가 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_RemoveNode(Node**Head,Node*Remove)
{
	if((*Head)==Remove)
    {
    	(*Head)->PrevNode->NexNode=Remove->NextNode;
    	(*Head)->NextNode->PrevNode=Remove->PrevNode;
        (*Head)=Remove->NextNode;
        
        Remove->NextNode=NULL;
        Remove->PrevNode=NULL;        
    }
    else
    {
    	Node* Temp=Remove;
        
        Remove->NextNode->PrevNode=Temp->PrevNode;
        Remove->PrevNode->NextNode=Temp->NextNode;
        
        Remove->NextNode=NULL;
        Remove->PrevNode=NULL;   
    }
}