원형 연결 리스트-자료구조<4>

hans·2022년 4월 14일

자료구조 공부 정리

목록 보기

4/14

원형 연결 리시트의 형태

원형 연결 리스트의 형태의 특징은 연결리스트의 꼬리가 헤드를 가리키고 있다는 점이다
원형 연결 리스트에서 어떻게 새로운 노드가 추가되는지 확인해 보자

원형 연결 리스트의 노드 추가

그림을 보면 꼬리 쪽에 새로운 노드가 생성된것을 확인할수 있다
여기서 중요하게 살펴볼 점은 먼저
꼬리노드가 헤드를 가리키고 있고 꼬리는 새로운 노드를 가리키고 있다는 점이다 이걸 기억하면서
원형 연결 리스트가 하나하나 만들어 지는 원리를 살펴보자

원형 연결 리스트 구현

1.연결 리스트의 멤버 초기화

코드

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

그림

2.새로운 노드 추가

코드

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); 
	newNode->data = data; 

	//2.첫 번째 노드 추가 참고
	if(plist->tail == NULL)  // ==> 생성된 노드가 첫 번쨰 노드면
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
    // 두 번쨰 이후 부터
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}

	(plist->numOfData)++;
}

그림

원형 연결 리스트의 노드 관계를 살펴보자
4번 그림에 data1은 data3을 가리킨다 (data 생략)
1->3->2->1 형식인데 tail이 3을 가리킨다 즉 tail 아닌 head라고 생각해보면
3->2->1->3 형식으로 tail로 추가하나 head 추가하나 노드의 관계는 일정함을 알수있다
즉 헤드 꼬리는 원형 연결리스트에서 구분의 의미를 가지지 않는다

그러면 지금부터는 연결 리시트의 조회를 살펴보자

연결 리스트 조회

코드


int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->tail;
	plist->cur = plist->tail->next;

	*pdata = plist->cur->data;
	return TRUE;
}

그림

여기서 cur before 포인터만 이동시켜 주면 된다

코드

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

코드를 보면 결국 원형 연결 리스트의 조회는 계속 순환하면서 진행된다는 것을 알수있다
원형 리시트의 순환의 특징을 알수있다

연결 리스트 삭제

삭제는 크게 2경우로 나눠보면
1.tail 이전 까지의 삭제
2.tail 에서 삭제

1번은 단순 연결리스트의 삭제와 같다
2번을 살펴보자

코드


Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;
    
    //중요 포인트

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}