A lista duplamente encadeada circular é uma estrutura de dados que oferece vantagens significativas em comparação com listas simples e não circulares. Apesar de sua complexidade, ela permite operações mais eficientes e flexíveis. Este artigo apresneta a implementação dessa estrutura em C, incluindo funções para inserção, remoção, busca e impressão.

Vantagens

1. Permite navegação em ambas as direções, facilitando operações como inversão da lista.
2. A eliminação de elementos é mais eficiente, pois não requer varredura do início até o elemento desejado.
3. Oferece maior eficiência na utilização da memória em comparação com arrays, especialmente em operações frequentes de inserção e exclusão.
4. Facilita a iteração reversa, tornanod-a mais eficiente em cenários específicos.

Características da Estrutura

Quando a lista contém apenas um nó sentinela, ele aponta para si mesmo.

Passos para Implementação

1. Inicialização

// Cria e retorna o nó cabeça da lista
ListNode* ListCreate()
{
	ListNode* head = NULL;
	head = CreateNode(-1); // Atribui um valor inicial ao nó
	head->_prev = head;
	head->_next = head;
	return head;
}

2. Inserção

Inserção no início

// Insere um novo nó no início da lista
void InsertAtHead(ListNode* head, LTDataType value)
{
	assert(head);
	ListNode* nextNode = head->_next;
	ListNode* newNode = CreateNode(value);
	head->_next = newNode;
	newNode->_prev = head;
	newNode->_next = nextNode;
	nextNode->_prev = newNode;
}

Inserção no final

// Insere um novo nó no final da lista
void InsertAtTail(ListNode* head, LTDataType value)
{
	assert(head);
	ListNode* tail = head->_prev;
	ListNode* newNode = CreateNode(value);
	tail->_next = newNode;
	newNode->_prev = tail;
	newNode->_next = head;
	head->_prev = newNode;
}

Inserção antes de um nó específico

// Insere um novo nó antes do nó especificado
void InsertBefore(ListNode* node, LTDataType value)
{
	assert(node);
	ListNode* newNode = CreateNode(value);
	ListNode* prevNode = node->_prev;
	prevNode->_next = newNode;
	newNode->_prev = prevNode;
	node->_prev = newNode;
	newNode->_next = node;
}

3. Remoção

Remoção do início

// Remove o primeiro nó da lista
void RemoveFromHead(ListNode* head)
{
	assert(head);
	if (head->_next == head) {
		return;
	}
	ListNode* first = head->_next;
	ListNode* second = first->_next;
	head->_next = second;
	second->_prev = head;
	free(first);
}

Remoção do final

// Remove o último nó da lista
void RemoveFromTail(ListNode* head)
{
	assert(head);
	if (head->_next == head) {
		return;
	}
	ListNode* tail = head->_prev;
	ListNode* prev = tail->_prev;
	prev->_next = head;
	head->_prev = prev;
	free(tail);
}

Remoção de um nó específico

// Remove o nó especificado
void RemoveNode(ListNode* node)
{
	assert(node);
	ListNode* prevNode = node->_prev;
	ListNode* nextNode = node->_next;
	prevNode->_next = nextNode;
	nextNode->_prev = prevNode;
	free(node);
}

4. Busca

// Procura por um valor na lista
ListNode* FindNode(ListNode* head, LTDataType value)
{
	ListNode* current = head->_next;
	while (current->_data != value) {
		current = current->_next;
		if (current == head) {
			printf("Valor não encontrado.\n");
			return NULL;
		}
	}
	return current;
}

5. Alteração

// Altera o valor de um nó encontrado
ListNode* pos = FindNode(head, 6);
pos->_data = 60;

6. Impressão

// Imprime os valores da lista
void PrintList(ListNode* head)
{
	assert(head);
	if (head->_next == head) {
		printf("NULL\n");
		return;
	}
	ListNode* current = head->_next;
	while (current != head) {
		printf("%d", current->_data);
		if (current->_next != head) {
			printf("《==》");
		} else {
			printf("\n");
		}
		current = current->_next;
	}
}

7. Destruição

// Libera toda a memória alocada pela lista
void DestroyList(ListNode* head)
{
assert(head);
ListNode* current = head->_next;
while (current != head) {
ListNode* next = current->_next;
free(current);
current = next;
}
free(head);
}