Compreendendo Listas em C #1

 

Quando falamos de listas vários exemplos podem nos vir em mente como, por exemplo, uma lista de compras, uma lista telefônica ou até mesmo os dias da semana. Na Ciência da Computação, uma lista é uma estrutura linear utilizada para armazenar e organizar os dados em um computador. A capacidade da lista é finita, podendo possuir elementos repetidos ou não.

 

Tipos de listas

Existem inúmeras representações e implementações diferentes para uma lista na linguagem de programação escolhida. Cada representação é relativa a como os elementos são inseridos ou removidos da estrutura, qual tipo de alocação a ser usada e como os elementos da lista serão acessados.

Alguns exemplos de listas são:

• Lista convencional: pode ter os elementos inseridos ou removidos de qualquer lugar dela.

• Fila: é uma estrutura do tipo FIFO (First In First Out), ou seja, o primeiro elemento que eu adicionar ao final da lista, será removido no início dela.

• Pilha: é uma estrutura parecida com a fila, porém é uma estrutura do tipo LIFO (Last In First Out), ou seja, os elementos só podem ser inseridos, acessados ou removidos do final da lista.

Vale ressaltar que este artigo não tem como foco se aprofundar nos conceitos de filas e pilhas, futuramente outros artigos virão para complementar essa ideia.

A alocação de memória das estruturas pode ser feita de duas formas:

• Alocação estática: aloca um espaço de memória no momento da compilação do programa, sendo necessário definir um valor numérico previamente indicando o número máximo de elementos que a lista irá possuir.

• Alocação dinâmica: aloca um espaço de memória dinamicamente, ou seja, em tempo real de execução do programa. A medida que é inserido novos elementos na lista, novos espaços de memória são alocados. De maneira análoga, a medida que os elementos são removidos da lista, os espaços de memória dos elementos alocados são liberados.

Os elementos de uma lista podem ser acessados de duas formas, independente do tipo de alocação realizada, as formas são:

• Acesso sequencial: os elementos são armazenados de forma consecutiva na memória, um bom exemplo disso é o uso de arrays. Assim, a posição de um elemento pode ser obtida através do início da lista.

• Acesso encadeado: cada elemento pode estar em uma área distinta da memória, não seguindo obrigatoriamente uma ordem de onde eles estão. Mas como isso funcionaria? Bem, cada elemento da lista deve armazenar duas coisas: a primeira é a sua informação, o dado em questão que esse elemento possui, já a segunda é o endereço de memória do próximo elemento. Para acessar um elemento de uma lista encadeada, é necessário percorrer todos os elementos antecessores da lista.

Quando falamos sobre estruturas de dados em C é quase impossível deixar de fora os tão “queridos” ponteiros. O acesso as listas encadeadas é feito através deles para armazenar o endereço do próximo elemento. Neste artigo, trabalharemos especialmente com alocação dinâmica de memória na implementação das estruturas em C e do acesso encadeado da lista.

 

Operações fundamentais de uma lista

Toda lista segue um padrão, esse padrão é um conjunto de operações básicas que a lista deve ser capaz de fazer, independente do tipo de alocação utilizada. Algumas das principais operações são:

• Criação da lista;
• Inserir um elemento na lista;

Existem três tipos de inserção na lista: inserção no início, meio ou final. Sempre que a operação de inserção for utilizada é preciso verificar se é possível inserir um novo elemento na lista, em outras palavras, se ela ainda não está cheia.

• Remover um elemento da lista;

Assim como na operação de inserção, a remoção também possui três tipos: remoção do início, meio ou final. Também é preciso verificar se existem elementos dentro da lista antes de tentar removê-los, afinal, não é possível remover algo se esse algo não existe.

• Buscar por um elemento da lista;
• Imprimir a lista na tela;
• Retornar o tamanho da lista;
• Verificar se a lista está cheia ou vazia;
• Destruição da lista.

 

Listas simplesmente encadeada

Como dito anteriormente, em uma lista de acesso encadeado (ou lista encadeada) para cada novo elemento inserido na estrutura alocamos um espaço de memória dinamicamente para armazená-lo e tem sua memória liberada à medida que o elemento é removido. Esse elemento é um ponteiro para uma estrutura que contém dois campos de informação: um campo de dado (utilizado para armazenar as informações do elemento), e um campo prox, que é um ponteiro que aponta para o endereço de memória do próximo elemento da lista ou para um valor nulo (NULL) quando se trata do nó final.

O esquema abaixo ilustra uma lista encadeada:

A estrutura de uma lista consiste em uma sequência encadeada de elementos, comumente chamados de nós. A lista é representada por um ponteiro para o primeiro elemento (ou nó). Partindo do primeiro elemento, podemos acessar o segundo, o terceiro, o quarto e assim sucessivamente seguindo o encadeamento.

Para exemplificar a implementação e noção de listas encadeadas em C, podemos ter como exemplo uma lista encadeada que armazena valores inteiros. A estrutura de um nó pode ser feita da seguinte forma:

Perceba que é uma estrutura auto-referenciada, ou seja, além do campo que armazena o dado, que neste caso é um número inteiro, há um outro campo que é um ponteiro para uma próxima estrutura do mesmo tipo. Como não alocamos nenhum nó, a estrutura ficará sem nenhum dado na memória.

Podemos então criar 3 variáveis ponteiro para o tipo No da seguinte forma:

A figura abaixo ilustra o processo de alocação, onde cada um dos ponteiros aponta para cada um dos nós alocados na memória.

Até agora não incluímos nenhuma informação nos nós. Podemos incluir alguns valores nos campos de dado de cada nó de uma maneira simples:

Internamente, na memória, temos:

Note que temos três nós, mas eles são independentes entre si, porém o nosso objetivo é percorrer todos elementos da lista dado um nó inicial. Por exemplo, em um array podemos acessar qualquer um dos elementos das i-posições fazendo operações aritméticas com o índice como: i+1, i+2 e assim por diante. Como os nós não estão em posições contíguas da memória, é necessário guardar o endereço do próximo nó. Esse encadeamento pode ser feito da seguinte forma:

A figura abaixo ilustra o processo:

Estando no nó primeiro, podemos acessar as informações armazenadas no nó segundo e terceiro usando o encadeamento dado pelo ponteiro prox. Em outras palavras, primeiro->prox->dado nos dá acesso a informação armazenada no segundo nó, de forma análoga: primeiro->prox->prox->dado nos da a informação do terceiro nó. O código abaixo exemplifica isso:

Note que, como mostrado no código acima, sempre partimos do primeiro ponteiro para chegarmos nos seguintes. Ou seja, tendo o primeiro nó, conseguimos percorrer todos outros nós. Sabendo disso, podemos alocar o nó inicial:

Seguindo a mesma lógica, podemos alocar o próximo nó. Como foi exemplificado nos códigos acima, esse nó deve ser atribuído ao campo próximo do primeiro nó, ou seja:

Como alocamos um espaço de memória para o próximo nó, podemos inserir um dado nele:

Por fim, falta alocar o terceiro e último nó do nosso exemplo e atribuir uma informação a ele. Seguindo o encadeamento, a partir do nó primeiro, temos que o terceiro nó deve ser alocado da seguinte forma: primeiro->prox->prox. Assim,

Note que no último nó, o campo prox recebeu o valor NULL, indicando o fim da lista.

O código final é o seguinte:

Perceba que se precisarmos adicionar mais nós, basta seguir o encadeamento e ir adicionando novos nós. Mas isso não é nada prático, a medida que adicionamos mais nós, mais alocações e acessos teremos no encadeamento. Para resolvermos esse problema utilizaremos um TAD Lista para nos auxiliar nas operações básicas e fundamentais de uma lista encadeada.

 

Criando uma lista

Antes de criarmos a função de criação da lista propriamente dita, precisamos definir a estrutura que irá conter o ponteiro inicio do tipo No que representará o nosso nó inicial da lista. O código pode ser implementado da seguinte forma:

A definição do tipo No ficará na interface (lista.h) do TAD Lista

Para utilizar uma lista em seu programa, a primeira coisa a se fazer é criar uma lista vazia atribuindo NULL ao ponteiro de início, indicando, assim, que não existem elementos na lista. O valor de retorno da função é um ponteiro para a estrutura de lista criada dinamicamente. Segue abaixo uma das formas de implementar a função:

 

Inserindo um elemento na lista

Com a função Lista criarLista() já implementada, podemos iniciar a criação da função de inserção. Para cada elemento inserido na lista, devemos alocar dinamicamente um espaço na memória para o novo nó e encadeá-lo na lista existente. Uma forma simples de criarmos essa função é inserir o novo elemento no início da lista. Uma possível implementação dessa operação é a seguinte:

Note que o ponteiro do tipo Lista deve ser passado como parâmetro, além, claro, da informação (conteúdo) do novo elemento que será inserido.

A função void inserir() aloca dinamicamente o espaço para armazenar o novo nó da lista, atribui a esse nó o elemento que deverá ser inserido, faz este nó apontar para o nó que era o primeiro da lista e, por fim, o primeiro nó da lista é atualizado.

 

Passo 1:

Cria o novo nó.

 

Passo 2:

Atualiza o ponteiro ‘prox’ do novo nó do qual deve apontar para o primeiro elemento da lista.

 

Passo 3:

Atualiza o ponteiro ‘prox’ do nó ‘início’ do qual deve apontar para o novo nó.

 

Buscando os elementos da lista

A operação de busca consiste em recuperar as informações contidas em determinado elemento da lista, podendo, assim como as outras operações, ser feita de diferentes maneiras, dependendo do propósito da aplicação.

A princípio, criaremos uma função que recebe o ponteiro do tipo Lista e a informação referente ao elemento que queremos buscar. O retorno da função será o ponteiro do nó da lista que representa o elemento em questão. Caso o elemento não seja encontrado, o valor retornado é NULL.

Note que o tipo de retorno da função busca é No, ou seja, como já foi dito, retornaremos um ponteiro referente ao nó onde o elemento se encontra.

 

Imprimindo a lista

Muita das vezes é necessário termos uma função para visualizarmos os elementos da lista. Uma possível implementação é a seguinte:

Para percorrer os elementos de um array, usamos uma variável auxiliar inteira para armazenar o índice de cada elemento. No caso de uma lista encadeada, a variável auxiliar tem que ser um ponteiro, que é usado para armazenar o endereço de cada elemento. No código acima, a variável atual aponta para cada um dos elementos da lista, do início ao fim (ou seja, enquanto atual for diferente de NULL). Note que, como dito anteriormente, para acessarmos um determinado elemento da lista, devemos percorrer ela desde o início, até que o elemento em questão seja alcançado.

 

Verificando se a lista está vazia

Assim como muita das vezes é necessário termos uma função para exibir a lista, também ocorre muito de precisarmos de uma função para verificar se ela está vazia ou não. Como sabemos, uma lista está vazia se seu primeiro elemento é NULL. Uma das implementações para essa função é mostrada a seguir:

o código acima pode ser simplificado, resultando na seguinte forma:

 

Liberando a lista da memória

Por fim, a última função e não menos importante do nosso TAD Lista é a função que libera a memória de todos elementos alocados dinamicamente. A função inicialmente irá liberar o encadeamento dos primeiros elementos e, em seguida, libera a estrutura da lista. Para realizar o processo de liberação do encadeamento, a função percorre cada um dos elementos, os liberando consecutivamente. Uma implementação dessa função é mostrada logo abaixo:

É importante notar que devemos guardar a referência para o próximo elemento antes de liberar o elemento atual em si, caso não fizéssemos esse procedimento, estaríamos acessando um espaço de memória que não estaria mais reservado para uso. Na linha 4 do código acima estamos guardando a referência para o próximo nó, em seguida, na linha 5, é liberada a memória apontada pelo nó atual, e por fim na linha 6 fazemos o nó atual apontar para o próximo.

 

Código final do TAD Lista

Lista.h

Lista.c

Cliente.c

 

Lista vs. Array

As vantagens da lista sobre o array são:

• Tamanho dinâmico: a capacidade da lista só será excedida quando a memória estiver realmente cheia, ou seja, não é preciso definir previamente o tamanho da lista;
• Melhor utilização dos recursos de memória;
• Não se precisa movimentar os elementos nas posições de inserção e remoção.

Enquanto as do array incluem:

• Listas encadeadas requerem espaço extra para armazenar os ponteiros junto com cada elemento da lista;
• Listas encadeadas não permitem um acesso aleatório dos itens. É necessário acessar os elementos sequencialmente a partir do primeiro nó. Por esse motivo, não é viável implementar uma busca binária em listas;
• Arrays têm melhor localidade de cache, o que pode fazer uma diferença considerável no desempenho.

 

Conclusão

Neste artigo foi abordado sobre as listas simplesmente encadeadas dinâmicas e suas vantagens e desvantagens em relação ao uso de arrays. Nos artigos seguintes, darei continuação a esse assunto, falando sobre algumas outras operações que não foram implementadas ainda em nosso TAD e que requerem uma abordagem mais minuciosa.

 

Referências

Estrutura de Dados Descomplicada - Em Linguagem C , por André Backes

Listas Encadeadas - W. Celes e J. L. Rangel

Criando uma lista encadeada em C - Israel Junior

Obrigado pela leitura!