Índice >
Lista >
Estática Encadeada
Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina
Lista Estática Encadeada
Os elementos da lista são registros com um dos componentes destinado
a guardar o endereço do registro sucessor.
Ex: L = anta, cabra, macaco, pato, rato
Cada registro é:
ou
Há duas alternativas para implementação de operações
de listas encadeadas: utilizando arrays
ou variáveis dinâmicas.
Encadeamento em arrays
Eliminando o elemento "cobra" teremos:
O registro 2 tornou-se disponível para as próximas inserções...
Implementação utilizando array
Após sucessivas inserções e eliminações
como descobrir quais registros estão disponíveis?
Juntá-los numa lista DISPO. Assim, os registros 6, 7, ... m
estariam inicialmente na lista DISPO.
Como deverá ser Dispo ? Sequencial?
Ela deve ser capaz de anexar os registros eliminados da lista principal
L. Suponha que queremos inserir algum elemento.
Isso implica que :
a eliminação de um elemento da lista principal causa a inserção
de um registro na lista Dispo
a inserção de um elemento na lista principal causa a utilização
de um dos registros da Dispo
No exemplo dado, ao eliminar "cobra" anexamos esse registro à
dispo.
A princípio podemos utilizar qualquer posição (todos
são vazios mesmos!!). A posição mais conveniente é
a do primeiro elemento do Dispo - uma vez que requer o acesso a poucos
ponteiros.
Se a próxima operação é a inserção
do elemento ovelha temos:
Com várias inserções e eliminações,
os registros da lista principal ficariam espalhados pelo vetor, intermediados
por registros disponíveis.
Vantagens:
-
não requer mais a movimentação de elementos na inserção
e eliminação (como na lista sequencial);
-
apenas os ponteiros são alterados (lembre que cada registro pode
conter elementos muito complexos);
Desvantagens:
-
necessário prever espaco máximo da lista;
-
necessário gerenciar a Dispo.
-
o acesso é não indexado, para acessar a(i) temos que percorrer
a(1) ... a(i-1) pois o endereço de a(i) está disponível
apenas em a(i-1);
-
aumento do tempo de execução, o qual é gasto obtenção
de espaço de memória;
-
reserva de espaço para a Dispo;
-
tamanho máximo pré-definido.
Quando usar:
-
quando for possível fazer uma boa previsão do espaço
utilizado (lista principal + Dispo) e quando o ganho dos movimentos sobre
a perda do acesso direto a cada elemento for compensador.
-
Veja as Operações
em Listas Encadeadas Estáticas.
Para evitar reservar espaço e gerenciar a Dispo, podemos utilizar Listas
Encadeadas Dinâmicas.
Exercícios
Lista