[C로 쓴 자료구조] 원형 리스트 (Circular List)

원형 리스트

 

마지막 노드의 link가 처음 노드를 가리키는 연결 리스트

리스트의 모든 노드를 효율적으로 반환할 수 있다

 

 

 

원형 리스트와 단일 연결 리스트의 연결

 

 

void cerase(struct poly** ptr) { //ptr이 가리키는 원형 리스트를 반환 (ptr이 가리키는 원형 리스트와 가용노드 avail을 합침 )

	struct poly* temp;

	if (*ptr) {
		temp = (*ptr)->link;
		(*ptr)->link = avail;
		avail = temp;
		*ptr = NULL;
	}
}

 

 

원형 리스트로 구현한 다항식 더하기

 

struct poly* cpadd(struct poly* a, struct poly* b) //원형 리스트로 구현한 다항식의 더하기
{
	/* 다항식 a와 b: singly linked circular lists with a head node.
	d = a + b를 계산한 후, d를 반환 */

	struct poly* starta, * d, * lastd;
	int sum, done = FALSE;
	starta = a; // a의 시작 노드를 기록
	a = a->link;
	b = b->link; // a와 b의 head node를 skip
	d = get_node(); // 합을 위한 head node 할당
	d->expon = -1; 
	lastd = d; //lastd는 rear와 같다

	do {
		switch (COMPARE(a->expon, b->expon)) {
			case -1: // a->expon < b->expon
				attach(b->coef, b->expon, &lastd);
				b = b->link; 
				break;
			case 0: // a->expon == b->expon
				if (starta == a) 
					done = TRUE;

				else {
					sum = a->coef + b->coef;
					if (sum) 
						attach(sum, a->expon, &lastd);
					a = a->link;
					b = b->link;
				}
				break;
			case 1:  // a->expon > b->expon
				attach(a->coef, a->expon, &lastd);
				a = a->link;
		}
	} 
	while (!done);
	lastd->link = d;
	return d;
}

 

 

원형 리스트의 선두에 노드 추가

 

리스트를 가리키는 포인터 ptr이 리스트의 마지막 노드를 pointing 할 경우에

리스트의 첫 번째 위치에 새로운 노드 추가,

리스트의 마지막 위치에 새로운 노드 추가의 Time complexity는 O(1)이다

즉 원형 리스트에서는 마지막 노드를 pointing 하는 게 유리하다

 

 

void insert_front(struct node** last, struct node* node) //원형 리스트에서 선두에 노드 추가
/* last가 가리키는 원형 리스트의 선두에 node 추가.
last는 원형 리스트의 마지막 노드를 가리키고 있음. */
{
	if (*last == NULL) {
		// 리스트가 비었음: last가 새로운 노드를 가리키도록 변경
		*last = node;
		node->link = node;
	}
	else {
		// 리스트에 노드가 존재: 선두에 노드 추가
		node->link = (*last)->link;
		(*last)->link = node;
	}
}

 

 

원형 리스트의 순회

 

A가 NULL일 때도 고려해야 하므로 오류에 빠지기 쉽다

 

struct node *ptr = A;
sum = ptr->data; // 처음 데이터는 별도로 처리
for (ptr = A->link; ptr != A; ptr = ptr->link)
	sum += ptr->data;

 

 

원형 리스트의 길이 계산

 

int length(struct node* ptr) //원형 리스트의 길이
{
	// ptr이 가리키는 원형 리스트의 노드 수를 return
	struct node* t;
	int count = 0;
	if (ptr != NULL) {
		t = ptr;
		do {
			count++;
			t = t->link;
		} while (t != ptr);
	}
	return count;
}