이중 연결 리스트(Double Linked List)

이중 연결 리스트로 구성함으로써, 순방향뿐만 아니라 역방향으로도 검색이 가능함.

[insert_front 과정]

0123456

[delete_front 과정]

0123

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

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

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

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

Node* alloc_list(Node * anl) {
	if(anl->next == anl) {
		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;

	printf("[Sequence]\n", node->data);

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

	printf("%d -> Head\n", node->data);
	printf("[Reverse]\n", node->data);

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

	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<9; i++)
	{
		Node* node = delete_front(Head);
		free_list(Anl, node);
		print_list(Head);
	}
}

[결과]