Lista Simplesmente Encadeada

Anhanguera Educacional – Estrutura de Dados
Prof. Ms. Thiago Salhab Alves

Lista Simplesmente Encadeada
Numa lista encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Dessa forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos armazenados. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo; portanto, não temos acesso direto aos elementos da lista. Para percorrer todos os elementos da lista, devemos explicitamente guardar o seu encadeamento, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro para o próximo elemento da lista.
A Figura 1 ilustra o arranjo da memória de uma lista encadeada (inserção pelo final da lista) e a Figura 2 ilustra o arranjo da memória de uma lista encadeada
(inserção pelo início da lista).

valor1

prox

valor2

prox

valor3

prox

Figura 1 – Arranjo da memória de uma lista encadeada (inserção pelo final) valor3 prox

valor2

prox

valor1

prox

Figura 2 – Arranjo da memória de uma lista encadeada (inserção pelo início)
A estrutura consiste de uma seqüência encadeada de elementos, em geral chamados de nós da lista. Um nó da lista é representado por uma estrutura que contém, conceitualmente, dois campos: a informação armazenada e o ponteiro para o próximo elemento da lista.
A lista é representa por um ponteiro para o primeiro elemento (ou nó). Do primeiro elemento, podemos alcançar o segundo, seguindo o encadeamento, e assim por diante. O último elemento da lista armazenada, como o próximo elemento, um ponteiro inválido, com valor NULL, e sinaliza, assim, que não existe próximo elemento.

Anhanguera Educacional – Estrutura de Dados
Prof. Ms. Thiago Salhab Alves
Características das Listas Encadeadas:
• São implementadas através de variáveis dinâmicas;
• Os nós que compõem a lista devem ser agregados do tipo registro contendo, pelo menos, dois campos: um campo de