Estrutura de dados 1 - Lista encadeada

Inicio aqui uma nova série de posts, desta vez voltada aos interessados na OBI e programação em geral: estruturas de dados (as básicas, pelo menos). Vamos começar pelas listas encadeadas, depois filas, pilhas e árvores. Em cada uma veremos as definições, implementação na linguagem C e situações nas quais as utilizamos. Mas antes, o que diabos são estruturas de dados?

Índice - Estruturas de dados

1 - Lista encadeada
2 - Pilha
3 - Fila
4 - Árvore binária

Estruturas de dados e sua utilidade

Como você organizaria ou organiza um numeroso conjunto de coisas, como seus CDs? Deixa jogados por aí, enfileira, coloca um em cima do outro? Cada método tem suas vantagens e desvantagens, dependendo de como você lida com os CDs. É muito fácil jogar por aí, mas quando você quer porque quer ouvir aquela música gravada em sua cabeça, começa a complicação. Não é, portanto, muito eficiente.

Em computação, eficiência é algo bastante relevante. A análise de algoritmos trata justamente disso, para estudar a exatidão e eficiência de um algoritmo. Entretanto, em nenhum momento nos preocupamos com o acesso dos dados. Jogamos os dados em um vetor e que os outros se virem para acessá-los.

Mas arrays, sejam vetores ou matrizes, são apenas uma forma de organizar os dados. Você já deve ter se deparado com uma situação na qual seria bom ter um array "turbinado", que simplesmente adicionasse elementos sem a necessidade de especificar um índice ou armazenasse quantas coisas quiséssemos sem especificar um tamanho.

Chamamos essas formas de organizar os dados estruturas de dados, que incorporam conceitos como filas, pilhas e árvores de maneira abstrata. O objetivo é aumentar a eficiência do armazenamento e retirada de dados, bem como oferecer operações adequadas a uma determinada situação, cada qual com suas utilidades próprias.

Definição e operações de uma lista encadeada

A ideia básica da lista encadeada é verdadeiramente encadear, ou ligar, uma coleção de elementos. Por exemplo:

A -> B -> C -> D

Os 4 elementos não estão realmente agrupados em um único bloco de memória, como em um array, mas o primeiro elemento aponta para o segundo; este aponta para o terceiro, que por fim aponta para o quarto. O que está acontecendo é o seguinte: cada uma das células da lista contém um valor e o endereço da célula seguinte.

Há vários tipos de implementação de listas encadeadas (este link dá uma boa geral), mas aqui estamos lidando com a mais simples: um conjunto de células ligados que permitem a inserção e remoção de células. A célula é um tipo de dado composto por um dado e um ponteiro. Também é comum utilizar listas "com cabeça", de modo que a primeira célula apenas marque o início da lista. Tal implementação mostra-se útil em várias situações, então nos focaremos nela.

Nossa implementação básica de lista encadeada precisa dos seguintes métodos:

- Inicializar lista
- Verificar se a lista está vazia
- Adicionar célula
- Remover célula

Implementação de lista encadeada em C

Em primeiro lugar, é assumido um conhecimento básico de ponteiros, que são a chave para a implementação de uma lista encadeada. Leia também sobre alocação dinâmica de memória em C (em especial as funções malloc e free). Antes de tudo vamos definir uma célula:

typedef int tipoElem;

typedef struct cel { 
  tipoElem dado; 
  struct cel *prox; 
}Celula;

Primeiro criamos um tipo de dado tipoElem para podermos alterar o código facilmente no futuro. Se quisermos lidar com char ao invés de int, por exemplo, basta mudar para typedef char tipoElem. Quanto à estrutura, sem problemas: temos um dado, o conteúdo da célula, e um ponteiro para a próxima célula. Vamos inicializar uma lista:



Celula * inicializaLista() {
       Celula *head;
       head = malloc(sizeof(Celula));
       head->prox = NULL;
       return head;
}

Utilizando a função malloc, da biblioteca stdlib.h, alocamos os bits necessários para a primeira célula. Como estamos tratando de uma célula com cabeça, a primeira célula é nula. Agora retornamos a cabeça (head) para ser utilizada em outra parte do programa. Com isso determinado, é fácil verificar se uma lista está ou não vazia:


int listaVazia(Celula *head) {
    return(head->prox == NULL);
}

Ora, se a próxima célula é nula, então a lista tem apenas a cabeça (claro que não seria o caso se passássemos como argumento a última célula de uma lista não-vazia). Portanto, a lista está vazia. Agora vamos adicionar células à lista, depois da célula p:


void adicionarCelula(Celula *p, tipoElem elem) {
     Celula *c;
     c = malloc(sizeof(Celula));
     c->dado = elem;
     c->prox = p->prox;
     p->prox = c;
}

Talvez pareça complicado, mas o processo é bem simples. Primeiro criamos um ponteiro que aponta para uma nova célula, alocamos a quantidade de memória necessária e inserimos o elemento passado como argumento no campo 'dado'. Agora suponha que a lista é formada por 3 células e o ponteiro passado como parâmetro foi head:

Queremos inserir a célula c, com o valor 3, ao início da lista, depois de head. Claro, o mais natural é fazer head apontar para c:

Mas espera... para quem c aponta mesmo? Como vemos, é um ponteiro vazio. Se apenas fizermos isso, destruímos as ligações e nossa lista fica esquartejada, pobrezinha. Precisamos, portanto, da instrução

c->prox = p->prox

Que nada mais é do que dizer: "Ei, c, aponte para a próxima célula da lista que virá depois de você". Portanto, a lista fica

Por último, remover uma célula. Uma coisa interessante a se notar é que não passamos como parâmetro a célula a ser removida, mas a célula anterior. Faz mais sentido utilizar listas com cabeça agora, não?

void removerCelula(Celula *p) {
     Celula *morta;
     morta = p->prox;
     p->prox = morta->prox;
     free(morta);
}

Nada de muito complicado aqui. Vamos demonstrar o que a função faz ilustrando com o exemplo anterior:

Queremos remover a primeira célula depois de head, ou seja, c. Passando head como argumento, identificamos a célula a ser morta e executamos a instrução

p->prox = morta->prox;

A próxima célula depois de c é a que contém o valor 2. Logo:

Simples, não? Apenas tiramos a ligação entre a head e a célula c, sem a necessidade de realocar elementos às suas posições adequadas como faríamos em um vetor. Por último, liberamos a memória utilizada pela célula.

Aplicações das listas encadeadas e exercícios

As listas encadeadas são a base para a implementação dinâmica de outras estruturas de dados, como veremos nos próximos posts. Representam uma alternativa aos vetores quando é necessário alterar o tamanho do conjunto de dados dinamicamente. Como vimos, adicionar e remover elementos envolve apenas manipulação de ponteiros, ao passo que em vetores precisaríamos mover elemento por elemento.

Cabe ao programador implementar a estrutura de lista encadeada da maneira mais adequada ao problema em questão. Algumas das situações nas quais você pode se deparar são as seguintes — aproveite e resolva-as agora!

• Travessia de uma lista encadeada: Como imprimir os dados das células de uma lista encadeada, contar o número de células ou remover todas de uma vez, liberando a memória utilizada por cada uma? Para tal precisaremos percorrer por toda a lista em algum loop.

• Inserção de elemento ao final da lista: Já sabemos adicionar elementos ao início da lista, mas e quanto ao final? Dica: você provavelmente vai utilizar uma travessia pela lista.

• Busca: Como buscar por um elemento em uma lista encadeada? É possível utilizar algum algoritmo de busca como a busca binária ou apenas busca linear?

• Lista sem cabeça: Tratamos apenas das listas com a "dummy head", mas é plenamente possível implementar listas sem utilizar essa técnica. A questão é: como realizar essa implementação de listas sem cabeça? Reescreva (ou não) as funções, acrescentando o que achar necessário.

• Cabeça e cauda: E se for necessário lidar com a "cauda" da lista? Pense no caso em que a última célula aponta para a primeira, como ilustrado abaixo. Nestas circunstâncias, você precisará lidar com listas com uma head e uma tail. Implemente-a.

Fontes

Linked list basics
linked list - Dictionary of Algorithms and Data Structures
Linked list - Wikipedia