Compreendendo Listas em C #1

Birds


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:

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:

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

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:

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.

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.


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:

img

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.

img

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:

img

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:

img

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:

img

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:

img

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,

img

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ó.

img

Passo 2:

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

img

Passo 3:

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

img


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:

Enquanto as do array incluem:


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.


Obrigado pela leitura!

Share on: