[C로 쓴 자료구조] 가용 노드 리스트

가용 노드 리스트

 

malloc과 free() 함수는 운영체제에 요청하는 함수이므로 실행시간이 길다.

따라서 malloc과 free()를 사용하지 않고 쓰지 않는 노드들을 내가 가지고 있다가 재활용하는 방법을 사용해서 운영체제에 요청하는 함수들의 호출 빈도수를 줄여보자!

 

리스트의 모든 노드 삭제

 

리스트의 모든 노드를 삭제 Time complexity : O(노드의 수)

 

void erase(struct poly** ptr) { //ptr이 가리키는 다항식 리스트를 삭제

	struct poly* temp;
	while (*ptr != NULL) {
		temp = *ptr;
		*ptr = (*ptr)->link;
		free(temp);
	}
}

 

 

get_node()

 

만약 aviail이 사용 가능한 노드를 가지고 있다면 그 노드를 반환해주고 avail이 NULL이라면 malloc을 통해 노드를 반환해준다 

 

struct poly* avail; // 안쓰는 노드들을 가지고있는 전역변수

struct poly* get_node() { //사용가능한 하나의 노드를 가용 리스트나 malloc()을 이용하여 반환

	struct poly* node;

	if (avail != NULL) { //사용가능한 node가 있다면 
		node = avail;
		avail = avail->link;
	}
	else { //사용가능한 노드가 없다면
		node = (struct poly*)malloc(sizeof(struct poly));

		if (IS_FULL(node)) {
			fprintf(stderr, "Ther memory if full\n");
			exit(1);
		}
	}
	return node;
}

 

 

ret_node()

 

free() 함수를 쓰지 않고 ret_node(*ptr)를 사용하여 ptr이 가리키는 노드를 가용 리스트 avail에 연결해준다

 

void ret_node(struct poly* ptr) { //ptr이 가리키는 노드를 가용 리스트에 반환
//free() 함수를 쓰지말고 ret_node를 상뇽해 avail에 연결
	ptr->link = avail;
	avail = ptr;
}