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

리스트의 끝이 다시 Head를 가리키게 하여 Tail을 사용하지 않는 환형 연결 리스트

typedef struct _Node Node;
struct _Node {
	int data;
	Node * next;
};

void init(Node ** Head) {
	*Head = (Node *)malloc(sizeof(Node));
	(*Head)->next = *Head;
}

void insert_front(Node* front, Node* data) {
	data->next = front->next;
	front->next = data;
}

Node* delete_front(Node* front) {
	Node* node = front->next;
	front->next = node->next;
	return node;
}

Node* alloc_list(Node * anl) {
	if(anl->next == anl) {
		printf("alloc\n");
		return (Node*)malloc(sizeof(Node));
	}

	else {
		return delete_front(anl);
	}
}

void free_list(Node *anl, Node *temp) {
	insert_front(anl, temp);
}

void print_list(Node* Head) {
	Node * node = Head->next;

	while(node != Head) {
		printf("%d -> ", node->data);
		node = node->next;
	}

	printf("Head\n");
}

int main() {
	Node* Head;
	Node* Anl;
	int i;
	
	init(&Head);
	init(&Anl);

	for(i = 0; i<10; i++)
	{
		Node* node = alloc_list(Anl);
		node->data = i;

		insert_front(Head, node);
		print_list(Head);
	}

	for(i = 0; i<10; i++)
	{
		Node* node = delete_front(Head);
		free_list(Anl, node);
		print_list(Head);
	}

	for(i=0; i<10; i++)
	{
		Node* node = alloc_list(Anl);
		node->data = i;

		insert_front(Head, node);
		print_list(Head);
	}
}

[결과]

[문제점]

- 역방향으로는 검색을 하지 못함.

[해결책]

- 이중 연결 리스트(Double Linked List)를 사용하면 됨.