Lista encadeada

ALGESD 06
Listas Encadeadas

Listas Encadeadas
Listas encadeadas são listas lineares em que os elementos não necessariamente encontram-se dispostos numa área continua de memória;
Como não se encontram numa área continua de memória é necessário ter alguma forma de relacioná-los entre sí;
A forma utilizada para relacioná-los é incluir em cada elemento, além do valor armazenado uma referência de onde está o próximo elemento da lista; Listas Encadeadas Simples

Referência inicial

A

D

E

Uma lista encadeada será formada então por diversos “nodos” inter relacionados por links e acessada a partir de uma referência inicial:

C

Lista encadeada

Listas Lineares
Conforme já vimos, uma lista é uma coleção de elementos do mesmo tipo dispostos linearmente que podem ou não seguir uma determinada organização.
Exemplo: [E1, E2, E3, E4, E5, ..., En], onde n deve ser > = 0;
Até aqui usamos alocação seqüencial para implementá-las mas a partir de agora usaremos a alocação encadeada.

Listas Encadeadas Simples

link

Cada elemento (nodo) da lista será formado pelo dado (data) a armazenar e uma referência (link) para o próximo:
Nodo:

data

Listas Encadeadas Simples

Nodo:

data

link

Em Java é necessário, antes de tudo, criarmos a classe Nodo composta por uma ou mais áreas de dados (data) que no exemplo é do tipo char e uma área que referencie o próximo (link):

auto referência

public class Nodo { char data;
Nodo link;
}

D

E

Nodo lista = new Nodo(); lista.data = ‘C’; lista.link = new Nodo(); lista.link.data = ‘A’;
Nodo aux = new Nodo(); aux.data = ‘D’; aux.link = new Nodo(); aux.link.data = ‘E’; aux.link.link = null; lista.link.link = aux;

Listas Encadeadas Simples

lista

A

Para criar uma lista como a abaixo poderíamos usar o seguinte conjunto de instruções em Java:

C

Listas Encadeadas Simples
Criando a referência lista... lista

Nodo lista = new Nodo();