Variantes de Listas Encadeadas

As listas encadeadas podem ser categorizadas por três características:

• Nó cabeça: Presença de um nó sentinela que não armazena dados
• Direcionalidade: Unidirecional (acesso sequencial) ou bidirecional (navegação reversa)
• Ciclicidade: Linear (fim aponta para NULL) ou circular (fim conectado ao início)

Combinações destas características geram oito tipos distintos. Duas configurações são comuns:

• Listas unidirecionais: Sem nó sentinela e não circulares
• Listas bidirecionais: Com nó santinela e circulares

Características de Listas Bidirecionais

Uma lista duplamente encadeada possui:

• Nó sentinela permanente como ponto de partida
• Ponteiros proximo (avanço) e anterior (retrocesso)
• Estrutura circular onde o último nó referencia o sentinela

Estado vazio: Apenas o nó sentinela existe, com seus ponteiros autorreferenciados.

Considerações de Implementação

1. O nó sentinela é permanente e imutável
2. Funções de destruição recebem ponteiro simples (não duplo) por consistência de API
3. Após destruição, o ponteiro original deve ser explicitamente definido como NULL para evitar referências inválidas

Código de Referência

Cabeçalho (Lista.h)

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int TipoDado;

typedef struct NoLista {
    TipoDado valor;
    struct NoLista* proximo;
    struct NoLista* anterior;
} NoDL;

NoDL* CriarLista();
void DestruirLista(NoDL* cabeca);
void ExibirLista(NoDL* cabeca);
bool ListaVazia(NoDL* cabeca);
void InserirFim(NoDL* cabeca, TipoDado x);
void RemoverFim(NoDL* cabeca);
void InserirInicio(NoDL* cabeca, TipoDado x);
void RemoverInicio(NoDL* cabeca);
void InserirAntes(NoDL* posicao, TipoDado x);
void RemoverNo(NoDL* posicao);
NoDL* LocalizarNo(NoDL* cabeca, TipoDado x);

Implementação (Lista.c)

#include "Lista.h"

NoDL* NovoNo(TipoDado x) {
    NoDL* novo = (NoDL*)malloc(sizeof(NoDL));
    if (!novo) exit(EXIT_FAILURE);
    
    novo->valor = x;
    novo->proximo = novo;
    novo->anterior = novo;
    return novo;
}

NoDL* CriarLista() {
    NoDL* sentinela = NovoNo(-1);
    return sentinela;
}

void DestruirLista(NoDL* cabeca) {
    assert(cabeca);
    NoDL* atual = cabeca->proximo;
    
    while (atual != cabeca) {
        NoDL* temp = atual;
        atual = atual->proximo;
        free(temp);
    }
    free(cabeca);
}

void ExibirLista(NoDL* cabeca) {
    assert(cabeca);
    NoDL* atual = cabeca->proximo;
    printf("Sentinela <=> ");
    
    while (atual != cabeca) {
        printf("%d <=> ", atual->valor);
        atual = atual->proximo;
    }
    printf("\n");
}

bool ListaVazia(NoDL* cabeca) {
    assert(cabeca);
    return cabeca->proximo == cabeca;
}

void InserirFim(NoDL* cabeca, TipoDado x) {
    assert(cabeca);
    NoDL* novo = NovoNo(x);
    NoDL* cauda = cabeca->anterior;
    
    cauda->proximo = novo;
    novo->anterior = cauda;
    novo->proximo = cabeca;
    cabeca->anterior = novo;
}

void RemoverFim(NoDL* cabeca) {
    assert(cabeca && !ListaVazia(cabeca));
    NoDL* cauda = cabeca->anterior;
    NoDL* anterior = cauda->anterior;
    
    anterior->proximo = cabeca;
    cabeca->anterior = anterior;
    free(cauda);
}

void InserirInicio(NoDL* cabeca, TipoDado x) {
    assert(cabeca);
    NoDL* novo = NovoNo(x);
    
    novo->proximo = cabeca->proximo;
    novo->anterior = cabeca;
    cabeca->proximo->anterior = novo;
    cabeca->proximo = novo;
}

void RemoverInicio(NoDL* cabeca) {
    assert(cabeca && !ListaVazia(cabeca));
    NoDL* primeiro = cabeca->proximo;
    
    cabeca->proximo = primeiro->proximo;
    primeiro->proximo->anterior = cabeca;
    free(primeiro);
}

void InserirAntes(NoDL* posicao, TipoDado x) {
    assert(posicao);
    NoDL* novo = NovoNo(x);
    NoDL* antecessor = posicao->anterior;
    
    antecessor->proximo = novo;
    novo->anterior = antecessor;
    novo->proximo = posicao;
    posicao->anterior = novo;
}

void RemoverNo(NoDL* posicao) {
    assert(posicao);
    NoDL* antecessor = posicao->anterior;
    NoDL* sucessor = posicao->proximo;
    
    antecessor->proximo = sucessor;
    sucessor->anterior = antecessor;
    free(posicao);
}

NoDL* LocalizarNo(NoDL* cabeca, TipoDado x) {
    assert(cabeca);
    NoDL* atual = cabeca->proximo;
    
    while (atual != cabeca) {
        if (atual->valor == x) 
            return atual;
        atual = atual->proximo;
    }
    return NULL;
}