Anahnguera Trabalhio

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

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

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.

valor1 prox valor2 prox valor3 prox

valor3 prox valor2 prox valor1 prox

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 tipo simples ou construído para

abrigar as informações armazenadas na lista e um campo do tipo ponteiro

para abrigar o endereço do nó subseqüente da lista;

• O acesso aos nós componentes da lista é seqüencial (para se acessar o 4

o

elemento, é necessário passar antes pelo 3

o

, para se acessar o 3

o

elemento,

é necessário passar antes pelo 2

o

e assim sucessivamente);

• As estruturas de representação de Listas Ligadas devem obrigatoriamente

suportar conceitos como ponteiros e alocação dinâmica;

• As Listas Ligadas podem ser simplesmente encadeadas (um único ponteiro

por nó) ou duplamente encadeadas (dois ponteiros por nó).

Vantagens e Desvantagens:

• Maior complexidade inerente à manipulação de ponteiros (desvantagem);

• O fato de nem todas as linguagens de programação permitirem a construção

de estruturas para a representação de Listas Ligadas (desvantagem);

• A possibilidade de se trabalhar com listas de tamanhos indefinidos, que

podem crescer e decrescer conforme a necessidade (vantagem);

• Maior facilidade para a realização de operações de inserção e remoção, que

consistem basicamente no rearranjo de alguns ponteiros (vantagem).

Principais Operações:

• Inserção de elementos em qualquer posição da lista (início ou final);

• Retirar elemento de qualquer posição lista;

• Impressão da lista;

• Busca de elementos na lista;

Implementação em C – inserção pelo início da lista

Para exemplificar a implementação de listas encadeadas em C, vamos

considerar um exemplo simples em que queremos armazenar valores inteiros

Anhanguera Educacional – Estrutura de Dados

Prof. Ms. Thiago Salhab Alves

em uma lista encadeada. O nó da lista pode então ser representado pela

estrutura a seguir:

struct no

{

int valor;

struct no* prox;

};

typedef struct no lista;

Devemos notar que