Implementacaodinenc 1

5. Implementação de Listas Lineares usando Alocação Dinâmica Encadeada

Numa lista encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Desta forma o espaço de memória gasto pela estrutura é proporcional ao número de elementos nela armazenados. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contiguo, portanto não temos acesso direto aos elementos da lista. Para que possamos percorrer todos os elementos da lista, devemos explicitamente guardar o encadeamento dos elementos o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro para o próximo elemento da lista. Como exemplo, veja o arranjo de memória de uma lista dinâmica encadeada na figura abaixo:

inicio da lista A lista ´r representada por um ponteiro para o primeiro elemento (ou nó). Do primeiro elemento podemos alcançar o segundo seguindo o encadeamento, e assim sucessivamente. O último elemento da lista aponta para NULL, sinalizando que nao existe um próximo elemento.

Vantagens: melhor utilização dos recursos de memória não requer movimentação de dados nas operações de inserção e remoção não requer gerenciamento de espaço livre

Desvantagens: acesso não indexado aos elementos da lista

Quando usar: quando não houver necessidade de garantir um espaço mínimo para a execução do aplicativo

5.1. Implementação do TDA lista_não_ordenada

Nesta seção implementaremos o TDA lista_não_ordenada, definida na seção 3.1.1 usando alocação de memória dinâmica encadeada.

a) estrutura da lista: é necessário definir explicitamente um ponteiro para o inicio da lista e um nó que contenha um campo para a informação e um campo para um ponteiro que aponte para um nó.

define estrutura NO como um inteiro que representa o elemento da lista chamado info um ponteiro que aponta para uma estrutura NO chamado prox fim

define estrutura LISTA como um ponteiro para NO fim