Lista Simplesmente Encadeada

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.