Listas simplesmente encadeadas

O vetor é a forma mais simples de guardar vários valores: um bloco contíguo de memória, com acesso direto a qualquer posição por v[i]. Mas ele tem limitações:

• o tamanho precisa ser escolhido de antemão: grande demais desperdiça memória, pequeno demais não cabe tudo (e aumentá-lo com realloc pode exigir copiar todos os elementos);
• inserir ou remover no meio exige deslocar todos os elementos seguintes.

Uma lista encadeada resolve esses problemas alocando cada elemento separadamente, só quando ele é inserido. Como os elementos ficam espalhados pela memória, cada um guarda, junto com o seu valor, o endereço do próximo. A lista cresce e diminui um elemento por vez, e inserir ou remover um elemento não exige mover os outros, só religar ponteiros.

Uma struct que aponta para outra

Uma struct pode ter campos de qualquer tipo, inclusive ponteiros. E nada impede que o ponteiro aponte para outra struct do mesmo tipo:

typedef struct no {
    int dado;              /* a informação guardada */
    struct no *proximo;    /* o endereço do próximo nó */
} No;

Uma estrutura assim é chamada de autorreferenciada. Cada elemento da lista é um nó (node): um campo com o dado e um ponteiro para o nó seguinte. Repare que, dentro da própria struct, o tipo é escrito como struct no *: o nome No do typedef só passa a existir depois do }.

Nós encadeados à mão

Antes de qualquer função, vale montar uma lista com três nós "na mão": alocar cada nó, preencher o dado e ligar cada um ao seguinte.

Escrever primeiro->proximo->proximo->... para chegar ao centésimo nó não é prático. Precisamos de funções que façam isso, e de uma estrutura que guarde a lista: o TAD Lista.

O TAD Lista

A lista é representada por uma struct própria, que guarda o endereço do primeiro nó e o número de elementos. Quem usa a lista não mexe nos nós diretamente: usa as operações do TAD (veja Tipo Abstrato de Dados).

typedef struct lista {
    No *inicio;      /* primeiro nó; NULL se a lista está vazia */
    int tamanho;
} Lista;

Uma alternativa comum na literatura é representar a lista só pelo ponteiro para o primeiro nó (No *lista). Guardar uma struct Lista à parte deixa as funções mais simples (elas sempre recebem Lista *, mesmo quando o primeiro nó muda) e permite acrescentar campos úteis, como o tamanho e, mais adiante, o último nó.

O programa abaixo tem as operações básicas. Cada uma é explicada em seguida.

Criar

criaLista aloca a struct da lista e a deixa vazia: inicio = NULL e tamanho = 0. Toda lista precisa ser criada por essa função antes de ser usada.

Inserir no início

O jeito mais simples de inserir é colocar o novo nó antes do primeiro:

1. alocar o novo nó e guardar o valor nele;
2. fazer o novo nó apontar para o antigo primeiro (novo->proximo = lista->inicio);
3. fazer a lista começar no novo nó (lista->inicio = novo).

A ordem dos passos 2 e 3 importa. Fazendo o passo 3 primeiro, o endereço do antigo primeiro nó se perderia, e com ele o resto da lista.

Percorrer

Para visitar todos os elementos (para imprimir, somar, procurar...), um ponteiro auxiliar começa no primeiro nó e avança pelo campo proximo até chegar a NULL:

for (No *atual = lista->inicio; atual != NULL; atual = atual->proximo)
    printf("%d -> ", atual->dado);

Buscar

procuraLista percorre a lista até achar o valor e devolve o nó (não o valor), ou NULL se não achar. Devolver o nó permite, depois, alterar o dado ou remover aquele nó sem procurá-lo de novo. O mesmo pode ser escrito com while:

No *procuraLista(const Lista *lista, int valor) {
    No *atual = lista->inicio;
    while (atual != NULL && atual->dado != valor)
        atual = atual->proximo;
    return atual;           /* o nó encontrado, ou NULL */
}

A ordem dos testes no while importa: atual != NULL vem primeiro e, se for falso, o && nem avalia atual->dado. Na ordem inversa, o fim da lista causaria um acesso por ponteiro nulo.

Lista vazia

A lista está vazia quando não tem nenhum nó, isto é, quando lista->inicio == NULL:

int listaVazia(const Lista *lista) {
    return lista->inicio == NULL;
}

Inserir no fim

Para inserir depois do último nó, é preciso achar o último: o nó cujo proximo é NULL. Se a lista estiver vazia, não há último, e o novo nó passa a ser o primeiro.

void insereFimLista(Lista *lista, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    novo->proximo = NULL;            /* será o último */
    if (lista->inicio == NULL) {
        lista->inicio = novo;
    } else {
        No *atual = lista->inicio;
        while (atual->proximo != NULL)
            atual = atual->proximo;
        atual->proximo = novo;
    }
    lista->tamanho++;
}

Andar até o fim custa . Na próxima seção, um campo a mais na struct deixa essa operação .

Liberar

Cada nó foi alocado com um malloc próprio, então cada um precisa do seu free, além da struct da lista. Ao liberar um nó, o endereço do próximo precisa ter sido guardado antes: depois do free, ler atual->proximo é acessar memória liberada.

void liberaLista(Lista *lista) {
    No *atual = lista->inicio;
    while (atual != NULL) {
        No *proximo = atual->proximo;   /* guarda antes de liberar */
        free(atual);
        atual = proximo;
    }
    free(lista);
}

Guardando também o fim

Com um ponteiro para o último nó na struct da lista, inserir no fim não exige mais percorrer nada:

typedef struct lista {
    No *inicio;      /* primeiro nó */
    No *fim;         /* último nó */
    int tamanho;
} Lista;

O preço é que toda operação que muda a lista precisa manter inicio, fim e tamanho corretos. Na criação, os dois ponteiros começam em NULL. Nas inserções:

void insereInicioLista(Lista *lista, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    novo->proximo = lista->inicio;
    if (lista->fim == NULL)          /* lista vazia: o novo é também o último */
        lista->fim = novo;
    lista->inicio = novo;
    lista->tamanho++;
}

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

Com o campo tamanho sempre atualizado, saber quantos elementos a lista tem também passa a ser , sem contar os nós.

Encontrando o nó anterior

Em uma lista simplesmente encadeada, cada nó conhece o próximo, mas não o anterior. Para achar o anterior de um nó p, é preciso percorrer a lista desde o início, em :

/* Devolve o nó anterior a p, ou NULL se p é o primeiro.
   Supõe que p pertence à lista. */
No *anteriorNoLista(const Lista *lista, const No *p) {
    No *anterior = NULL;
    No *atual = lista->inicio;
    while (atual != p) {
        anterior = atual;
        atual = atual->proximo;
    }
    return anterior;
}

É por causa do anterior que remover é a operação mais delicada da lista simplesmente encadeada.

Removendo um elemento

Para tirar um nó p da lista, o nó anterior a ele precisa passar a apontar para o nó seguinte a ele. Por isso a busca anda com dois ponteiros juntos: p, no nó examinado, e anterior, no nó examinado antes dele (começa em NULL, porque o primeiro nó não tem anterior).

Encontrado o nó, há quatro situações:

1. único nó (é o início e o fim): a lista fica vazia, e inicio e fim voltam a NULL;
2. primeiro nó: não há anterior para religar; inicio avança para p->proximo;
3. último nó: o anterior vira o último (anterior->proximo = NULL e fim = anterior);
4. nó do meio: anterior->proximo = p->proximo, pulando p.

/* Remove TODOS os nós com o valor dado */
void removeElementoLista(Lista *lista, int valor) {
    No *p = lista->inicio;
    No *anterior = NULL;
    while (p != NULL) {
        if (p->dado != valor) {      /* não é este: os dois avançam */
            anterior = p;
            p = p->proximo;
            continue;
        }
        if (p == lista->inicio && p == lista->fim) {    /* único nó */
            lista->inicio = lista->fim = NULL;
            free(p);
            p = NULL;
        } else if (p == lista->inicio) {                /* primeiro nó */
            lista->inicio = p->proximo;
            free(p);
            p = lista->inicio;
        } else if (p == lista->fim) {                   /* último nó */
            anterior->proximo = NULL;
            lista->fim = anterior;
            free(p);
            p = NULL;
        } else {                                        /* nó do meio */
            anterior->proximo = p->proximo;
            free(p);
            p = anterior->proximo;
        }
        lista->tamanho--;
    }
}

Repare que a função remove todas as ocorrências do valor: depois de remover um nó, o laço continua a partir do seguinte. Para remover só a primeira, bastaria sair do laço depois da remoção.

Inserindo em ordem

Às vezes a lista precisa ficar sempre ordenada. Para inserir um valor no lugar certo, procura-se o primeiro nó com dado maior ou igual ao novo valor, de novo com dois ponteiros, e o novo nó entra entre anterior e p. As pontas reaproveitam as funções que já existem:

void insereOrdenadoLista(Lista *lista, int valor) {
    No *p = lista->inicio;
    No *anterior = NULL;
    while (p != NULL && p->dado < valor) {
        anterior = p;
        p = p->proximo;
    }
    if (anterior == NULL) {                  /* entra no início */
        insereInicioLista(lista, valor);
        return;
    }
    if (p == NULL) {                         /* entra no fim */
        insereFimLista(lista, valor);
        return;
    }
    No *novo = malloc(sizeof(No));           /* entra entre anterior e p */
    novo->dado = valor;
    novo->proximo = p;
    anterior->proximo = novo;
    lista->tamanho++;
}

A inserção ordenada custa no pior caso, porque pode percorrer a lista inteira.

Copiando uma lista

Para ter uma segunda lista com os mesmos valores, não basta criar outra struct Lista e copiar o ponteiro inicio: as duas compartilhariam os mesmos nós, e alterar ou liberar uma estragaria a outra (liberar as duas seria liberar cada nó duas vezes). Uma cópia independente cria nós novos, um para cada valor:

Lista *copiaLista(const Lista *lista) {
    Lista *copia = criaLista();
    for (No *atual = lista->inicio; atual != NULL; atual = atual->proximo)
        insereFimLista(copia, atual->dado);
    return copia;
}

Com insereFimLista em , a cópia custa . Com a versão antiga, que percorre a lista a cada inserção, custaria .

Tudo junto

O programa abaixo reúne a lista com inicio, fim e tamanho e todas as operações desta página. Experimente remover outros valores, inserir em ordem valores repetidos, ou alterar a cópia e imprimir as duas listas.

Lista ou vetor?

Além disso:

• a lista cresce e diminui à vontade, enquanto houver memória; o vetor tem capacidade fixa (ou precisa ser realocado);
• cada nó da lista gasta memória extra com o ponteiro, além do dado;
• com elementos grandes, religar ponteiros é muito mais barato que mover os elementos de lugar;
• os elementos do vetor ficam lado a lado na memória, o que aproveita melhor a cache do processador; percorrer um vetor costuma ser bem mais rápido que percorrer uma lista com o mesmo número de elementos.

Remover o último nó continua , mesmo com o ponteiro fim: é preciso achar o anterior a ele. É isso que a lista duplamente encadeada resolve.

Exercícios

Encontre e corrija o erro

Cada programa tem um erro. Execute, leia a saída e as mensagens, corrija e execute de novo.

Programa 1

Deveria inserir os valores mantendo a lista em ordem crescente.

if (anterior == NULL)
    lista->inicio = novo;
else
    anterior->proximo = novo;

Programa 2

No *proximo = atual->proximo;
free(atual);
atual = proximo;

Programa 3

Implemente

Nos dois exercícios, Lista.h é a interface e ListaInterno.h define os campos (inicio, fim e tamanho); as funções básicas já estão prontas em Lista.c. Os testes conferem, além dos valores, se inicio, fim e tamanho continuam corretos.

Inverter a lista. Inverta a ordem dos elementos religando os próprios nós, sem criar nem liberar nenhum.

Intercalar listas ordenadas. Dadas duas listas em ordem crescente, construa uma terceira, também em ordem crescente, com os elementos das duas. Os testes usam listas com até 150 mil nós: inserir um a um em ordem, como insereOrdenadoLista, custaria e 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.
• P. Feofiloff. O que é uma lista encadeada e como implementá-la. IME-USP.