Nesta aula estudamos uma variação da lista simplesmente encadeada (Aula 4): a lista duplamente encadeada, em que cada nodo conhece tanto o seu sucessor quanto o seu antecessor. Veremos como isso resolve algumas limitações da versão simples, ao custo de mais memória e mais cuidado ao manter os ponteiros consistentes.

1. Motivação: limitações da lista simplesmente encadeada

Na lista simplesmente encadeada (ListaEnc), cada nodo aponta apenas para o próximo. Isso traz algumas limitações que já sentimos na prática nas Aulas 4 e 5:

• Para percorrer a lista de trás para frente, não há como — só existe o ponteiro prox, nunca um caminho de volta;
• Para inserir no final (inserirFim), é preciso percorrer a lista inteira até encontrar o último nodo, custando O(n), mesmo sendo "só uma inserção";
• Para remover um nodo, mesmo que já tenhamos um ponteiro direto para ele, ainda precisamos percorrer a lista desde o início só para descobrir quem é o seu antecessor (o nodo ant, necessário para "religar" a lista) — como fizemos em removerPorCod.

A lista duplamente encadeada ataca exatamente esses três pontos, adicionando um segundo ponteiro a cada nodo.

2. Listas duplamente encadeadas

Em uma lista duplamente encadeada, cada nodo contém:

• Os dados propriamente ditos;
• Um ponteiro prox para o próximo nodo (como antes);
• Um ponteiro ant para o nodo anterior — a novidade desta aula.

        ini                                           fim
         |                                             |
         v                                             v
NULL <--[ant| dado |prox]<-->[ant| dado |prox]<-->[ant| dado |prox]--> NULL

O primeiro nodo tem ant == NULL, e o último tem prox == NULL — assim como na lista simples, esses valores continuam marcando as extremidades. A diferença é que agora também guardamos, na própria struct da lista, um ponteiro para o último nodo (fim), além do ponteiro para o primeiro (ini):

3. TAD Lista Duplamente Encadeada (LDE)

Dados

Reaproveitamos o mesmo Produto das aulas anteriores:

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

O nodo agora tem dois ponteiros:

typedef struct str_NodoD NodoD;

struct str_NodoD {
    NodoD *ant;
    NodoD *prox;
    Produto dado;
};

E a struct da lista guarda os dois extremos:

typedef struct {
    NodoD *ini;
    NodoD *fim;
} ListaDuplaEnc;

Operações

void    inicializar(ListaDuplaEnc *l);
void    imprimir(ListaDuplaEnc *l);
void    imprimirInverso(ListaDuplaEnc *l);
Produto acessar(ListaDuplaEnc *l, int cod);
int     inserirInicio(ListaDuplaEnc *l, Produto prod);
int     inserirFim(ListaDuplaEnc *l, Produto prod);
int     removerPorCod(ListaDuplaEnc *l, int cod);
void    destruir(ListaDuplaEnc *l);
int     tamanho(ListaDuplaEnc *l);

4. Implementação em C

inicializar

void inicializar(ListaDuplaEnc *l) {
    l->ini = NULL;
    l->fim = NULL;
}

imprimir e imprimirInverso

A grande vantagem prática do ponteiro ant aparece aqui: percorrer a lista de trás para frente é tão simples quanto percorrê-la para frente, bastando partir de l->fim e seguir por ant:

void imprimir(ListaDuplaEnc *l) {
    NodoD *aux = l->ini;

    while (aux != NULL) {
        printf("%d - %s - %.2f\n", aux->dado.cod, aux->dado.nome, aux->dado.preco);
        aux = aux->prox;
    }
}

void imprimirInverso(ListaDuplaEnc *l) {
    NodoD *aux = l->fim;

    while (aux != NULL) {
        printf("%d - %s - %.2f\n", aux->dado.cod, aux->dado.nome, aux->dado.preco);
        aux = aux->ant;
    }
}

acessar

Igual à Aula 4 — a busca por código continua sendo sequencial, o ponteiro ant não ajuda a "pular" nodos:

Produto acessar(ListaDuplaEnc *l, int cod) {
    NodoD *aux = l->ini;
    Produto prod = {-1, "", 0.0f};

    while (aux != NULL) {
        if (aux->dado.cod == cod)
            return aux->dado;
        aux = aux->prox;
    }

    return prod;
}

inserirInicio

Além de encaixar o novo nodo antes do início, é preciso lembrar de duas atualizações que não existiam na lista simples: o ant do antigo início precisa passar a apontar para o novo nodo, e, se a lista estava vazia, o novo nodo também é o fim:

int inserirInicio(ListaDuplaEnc *l, Produto prod) {
    NodoD *novo = (NodoD*) malloc(sizeof(NodoD));
    if (novo == NULL)
        return 0;

    novo->dado = prod;
    novo->ant = NULL;
    novo->prox = l->ini;

    if (l->ini != NULL)
        l->ini->ant = novo; // o antigo início passa a ter um antecessor
    else
        l->fim = novo;      // lista estava vazia: novo nodo também é o fim

    l->ini = novo;
    return 1;
}

inserirFim

Graças ao ponteiro l->fim, esta operação deixa de percorrer a lista inteira — vira uma inserção direta, assim como inserirInicio:

int inserirFim(ListaDuplaEnc *l, Produto prod) {
    NodoD *novo = (NodoD*) malloc(sizeof(NodoD));
    if (novo == NULL)
        return 0;

    novo->dado = prod;
    novo->prox = NULL;
    novo->ant = l->fim;

    if (l->fim != NULL)
        l->fim->prox = novo; // o antigo fim passa a apontar para o novo nodo
    else
        l->ini = novo;       // lista estava vazia: novo nodo também é o início

    l->fim = novo;
    return 1;
}

removerPorCod

Aqui está o segundo grande ganho da lista duplamente encadeada: uma vez localizado o nodo a remover, não precisamos mais de um ponteiro auxiliar ant obtido durante a busca — o próprio nodo já sabe quem é o seu antecessor, através de aux->ant:

int removerPorCod(ListaDuplaEnc *l, int cod) {
    NodoD *aux = l->ini;

    while (aux != NULL && aux->dado.cod != cod)
        aux = aux->prox;

    if (aux == NULL) // não encontrado
        return 0;

    if (aux->ant != NULL) // existe antecessor: religa por ele
        aux->ant->prox = aux->prox;
    else                  // removendo o próprio início
        l->ini = aux->prox;

    if (aux->prox != NULL) // existe sucessor: religa por ele
        aux->prox->ant = aux->ant;
    else                   // removendo o próprio fim
        l->fim = aux->ant;

    free(aux);
    return 1;
}

destruir

void destruir(ListaDuplaEnc *l) {
    NodoD *ant;
    NodoD *aux = l->ini;

    while (aux != NULL) {
        ant = aux;
        aux = aux->prox;
        free(ant);
    }

    l->ini = NULL;
    l->fim = NULL;
}

tamanho

Assim como decidimos na Aula 4, não guardamos um contador na struct — tamanho continua sendo O(n):

int tamanho(ListaDuplaEnc *l) {
    NodoD *aux = l->ini;
    int contador = 0;

    while (aux != NULL) {
        contador++;
        aux = aux->prox;
    }

    return contador;
}

5. Vantagens, desvantagens e complexidade

Resumo

Exercícios

1. Por que a lista duplamente encadeada precisa de duas atualizações extras em inserirInicio (o ant do antigo início, e possivelmente l->fim), que não existiam na versão simplesmente encadeada?
2. Explique por que inserirFim passa a ser O(1) na lista duplamente encadeada, mesmo sem alterar em nada a forma como acessar ou removerPorCod localizam um nodo pelo código.
3. Na função removerPorCod, por que é necessário tratar separadamente os casos em que o nodo removido é o início (aux->ant == NULL) ou o fim (aux->prox == NULL) da lista?
4. Se um nodo estiver "sozinho" na lista (é ao mesmo tempo o início e o fim), o que deve acontecer com l->ini e l->fim ao removê-lo? Verifique se o código de removerPorCod apresentado trata esse caso corretamente.
5. Cite uma situação prática em que ser capaz de percorrer uma lista "de trás para frente" (com imprimirInverso) é útil.
6. Implemente uma função int inserirAntes(ListaDuplaEnc *l, int cod, Produto prod) que insira prod imediatamente antes do nodo cujo código é cod, retornando 1 em caso de sucesso ou 0 caso o código não seja encontrado. Dica: use o ponteiro ant do nodo encontrado para "encaixar" o novo nodo entre os dois.
7. Implemente uma função Produto ultimoAcimaDe(ListaDuplaEnc *l, float valor) que percorra a lista de trás para frente (usando imprimirInverso como inspiração) e retorne o primeiro produto encontrado, nesse sentido, com preço maior que valor. Caso nenhum seja encontrado, retorne um produto com cod = -1.

Sugestões de Respostas dos Exercícios

int inserirAntes(ListaDuplaEnc *l, int cod, Produto prod) {
    NodoD *aux = l->ini;
    NodoD *novo;

    while (aux != NULL && aux->dado.cod != cod)
        aux = aux->prox;

    if (aux == NULL) // código não encontrado
        return 0;

    novo = (NodoD*) malloc(sizeof(NodoD));
    if (novo == NULL)
        return 0;

    novo->dado = prod;
    novo->prox = aux;
    novo->ant = aux->ant;

    if (aux->ant != NULL)
        aux->ant->prox = novo;
    else
        l->ini = novo; // aux era o início: novo nodo passa a ser o início

    aux->ant = novo;

    return 1;
}

Produto ultimoAcimaDe(ListaDuplaEnc *l, float valor) {
    NodoD *aux = l->fim;
    Produto prod = {-1, "", 0.0f};

    while (aux != NULL) {
        if (aux->dado.preco > valor)
            return aux->dado;
        aux = aux->ant;
    }

    return prod;
}

Código para Download

O TAD ListaDuplaEnc completo, exatamente como visto nesta aula, dividido em interface (listaDuplaEnc.h) e implementação (listaDuplaEnc.c), junto com um main.c de exemplo: