Listas duplamente encadeadas

Na lista simplesmente encadeada, cada nó só conhece o seguinte. Isso traz duas limitações:

• não dá para percorrer a lista de trás para frente de forma eficiente;
• para remover um nó, mesmo tendo um ponteiro para ele, é preciso percorrer a lista desde o início para achar o anterior, em . Pelo mesmo motivo, remover o último nó custa , mesmo com o ponteiro fim.

Em uma lista duplamente encadeada, cada nó guarda dois ponteiros: um para o próximo e outro para o anterior. Dado um nó, os dois vizinhos estão a um passo.

Estrutura

typedef struct no {
    int dado;
    struct no *proximo;
    struct no *anterior;
} No;

typedef struct lista {
    No *inicio;
    No *fim;
    int tamanho;
} Lista;

A struct da lista é a mesma da lista simplesmente encadeada, com inicio, fim e tamanho. No primeiro nó, anterior é NULL; no último, proximo é NULL.

Inserindo

Na inserção no início, o novo nó não tem anterior, e o seu próximo é o antigo primeiro. Se a lista não estava vazia, o antigo primeiro passa a ter o novo nó como anterior; se estava, o novo nó é também o último.

void insereInicioLista(Lista *lista, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    novo->proximo = lista->inicio;
    novo->anterior = NULL;               /* malloc não zera a memória */
    if (lista->fim == NULL)              /* lista vazia */
        lista->fim = novo;
    else
        lista->inicio->anterior = novo;  /* o antigo primeiro aponta de volta */
    lista->inicio = novo;
    lista->tamanho++;
}

A inserção no fim é simétrica: o novo nó não tem próximo, e o seu anterior é o antigo último.

void insereFimLista(Lista *lista, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    novo->proximo = NULL;
    novo->anterior = lista->fim;
    if (lista->fim == NULL)              /* lista vazia */
        lista->inicio = novo;
    else
        lista->fim->proximo = novo;
    lista->fim = novo;
    lista->tamanho++;
}

Removendo

Com o ponteiro para o nó p, os dois vizinhos são p->anterior e p->proximo. Para tirar p da lista, cada vizinho passa a apontar para o outro:

p->anterior->proximo = p->proximo;
p->proximo->anterior = p->anterior;

Nas pontas, um dos vizinhos não existe. Se p é o primeiro, quem muda é lista->inicio; se é o último, lista->fim. Cada sentido é tratado separadamente:

/* Remove a primeira ocorrência do valor */
void removeElementoLista(Lista *lista, int valor) {
    No *p = procuraLista(lista, valor);
    if (p == NULL)
        return;

    if (p == lista->inicio)              /* quem vem antes de p? */
        lista->inicio = p->proximo;
    else
        p->anterior->proximo = p->proximo;

    if (p == lista->fim)                 /* quem vem depois de p? */
        lista->fim = p->anterior;
    else
        p->proximo->anterior = p->anterior;

    free(p);
    lista->tamanho--;
}

Compare com a remoção na lista simplesmente encadeada: não há mais um ponteiro anterior acompanhando a busca, nem quatro casos. Os dois if cobrem também o nó único (que é início e fim), deixando a lista vazia. Depois de procuraLista, a remoção em si é .

Percorrendo nos dois sentidos

Do início para o fim, o percurso é igual ao da lista simplesmente encadeada. Do fim para o início, basta começar em lista->fim e seguir os ponteiros anterior:

void imprimeReversoLista(const Lista *lista) {
    printf("NULL <-> ");
    for (No *p = lista->fim; p != NULL; p = p->anterior)
        printf("%d <-> ", p->dado);
    printf("NULL\n");
}

O programa abaixo reúne as operações. Imprimir a lista nos dois sentidos depois de cada alteração é uma boa forma de conferir se os dois encadeamentos continuam consistentes.

Quanto custa o ponteiro extra?

O custo é um ponteiro a mais por nó (8 bytes em sistemas de 64 bits) e mais um campo para manter correto em cada operação. Em troca, as operações nas duas pontas e a remoção de um nó conhecido ficam todas .

Exercícios

Encontre e corrija o erro

Programa 1

else
    p->proximo->anterior = p->anterior;

Programa 2

Implemente

Nos dois exercícios, os campos estão em ListaInterno.h e as funções básicas (criar, inserir no fim, imprimir nos dois sentidos, procurar, liberar) já estão prontas em Lista.c.

Lista palíndromo. Verifique se a sequência de valores é a mesma lida nos dois sentidos, andando ao mesmo tempo a partir das duas pontas, sem copiar a lista para um vetor.

Remover um nó em O(1). Dado um ponteiro para um nó da lista, remova-o sem percorrer a lista. Os testes fazem 100 mil remoções seguidas: procurar o nó ou o anterior a cada uma não termina a tempo.

Referências

• W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.