[DS/자료구조] 연결 리스트 - 원형 연결 리스트(Circular Linked List)

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

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. 원형 연결 리스트에서 head는 마지막 노드를 가리키게 된다. 이렇게 되면 head의 첫 노드와 마지막 노드에 접근이 쉬워진다.

위키백과 원형 연결 리스트

 

특징

• 헤드 노드의 link는 마지막 노드를 가리킨다.
• 헤드 노드의 link의 link는 첫 번째 노드가 된다.
• 리스트의 마지막에 노드를 삽입, 삭제가 용이해진다.
• 현재 노드에서 이전 노드를 접근하려면 첫 번째 노드부터 다시 접근해야 한다.

 

장점과 단점

장점

• 한 노드에서 다른 모든 노드로의 접근이 가능해 노드의 삽입, 실제가 단순해진다.
• 반복적인 순회에서 연결 리스트의 끝을 체크해야 할 필요가 없다.
• 구조상 끝이 존재하지 않으며 HEAD와 TAIL의 구분이 없다. (TAIL을 사용하는 원형 연결 리스트를 변형된 원형 연결 리스트라고 한다.)

단점

• 노드의 삽입, 삭제 시 선행 노드의 포인터가 필요하다.
• 노드 검색 시 결과가 없다면 무한 Loop가 발생할 수 있다.

 

변형 원형 연결 리스트 구현

구조체

typedef struct CircularListNodeType
{
	int data;
	struct CircularListNodeType	*pRLink;
} CircularListNode;

typedef struct CircularListType
{
	int	currentElementCount;	
	CircularListNode	headerNode;
}	CircularList;

 

구성 함수

CircularList        *createCircularList();
int	                addCLElement(CircularList *pList, int position, CircularListNode element);

CircularListNode    *getCLElement(CircularList *pList, int position);
int                 getCircularListLength(CircularList *pList);

int                 removeCLElement(CircularList *pList, int position);
void                clearCircularList(CircularList *pList);
void                deleteCircularList(CircularList *pList);

void                displayCircularList(CircularList *pList);

 

생성

CircularList	*createCircularList() 
{
	CircularList	*lst;

	lst = calloc(1, sizeof(CircularList)); // list 초기화
	return (lst);
}

 

추가

int	addCLElement(CircularList *pList, int position, CircularListNode element) // node 추가
{
	CircularListNode	*buf;
	CircularListNode	*new;

	if (!pList || !(position >= 0 && position <= pList->currentElementCount))
		return (FALSE);
	
	new = calloc(1, sizeof(CircularListNode));
	new->data = element.data;
    // node가 없는 경우
	if ((pList->currentElementCount) == 0) {
		pList->headerNode.pRLink = new;         	// header 지정
		new->pRLink = pList->headerNode.pRLink; 	// pRlink를 자기 자신으로 하여 순회할 수 있게 한다.
	}
    // node가 있는 경우
	else {
		buf = getCLElement(pList, position - 1);    // 삽입할 포지션 전의 것을 지정한다.
		new->pRLink = buf->pRLink;                  // node 간 연결
		buf->pRLink = new;
		if (position == pList->currentElementCount) // 만약 position이 맨 끝일 경우 header 로 지정한다.
			pList->headerNode.pRLink = new;
	}
	pList->currentElementCount += 1;                // node 개수를 늘려준다.
	return (TRUE);
}

 

출력

void    displayCircularList(CircularList *pList) 
{
	CircularListNode	*head;
	int					idx;

	head = pList->headerNode.pRLink->pRLink; // 0번째 node는 header 다음 node이다.
	idx = 0;
	while (idx < pList->currentElementCount)
	{
		printf("pList[%d] = %d\n", idx++, head->data);
		head = head->pRLink;
	}
}