Fila Dinamica

LISTAS
(estruturas lineares dinâmicas)

INCONVENIENTES NA UTILIZAÇÃO DE VECTORES
1.

Tamanho do vector é fixo. Não existe a possibilidade de se aumentar durante a execução.

2.

As operações de inserção/remoção dispendiosas (em termos de processamento)

LISTAS
Estruturas de armazenamento de dados linear e dinâmica

?

LISTAS
Simplesmente ligadas (simples)

Inicio, Cabeça

Fim, Cauda

Duplamente ligadas (duplas)

Acesso às listas é efectuado através de referência externa

IMPLEMENTAÇÃO DE LISTAS SIMPLES

referência

elemento da lista

1. Definição do tipo ELEM (elemento da lista) e do referência para a lista class ELEM{ char info;
ELEM prox=null; // ????
ELEM(char a){
// construtor da classe ELEM info=a; }
}

2. Armazenamento / Inserção (Início da lista)
a) Cria novo elemento da lista:
ELEM aux= new ELEM(‘D’);

b) Liga novo elemento ao elemento referenciado por Lista: aux.prox=Lista; c) Aponta ponteiro lista para último nó da lista (novo_no):
Lista=aux;

3. Recuperação / Remoção (Início da lista)
a) Cria referencia para o elemento a ser removido:
ELEM rem; rem=Lista; b) Altera ponteiro acesso à lista :
Lista=rem.prox;

c) Guarda informação do elemento a remover da Lista : x=rem.info; Não há necessidade de libertar-se a memória ocupada pelo objecto devido à existência do ‘Garbage Colector’

Função (método) armazenamento em listas simples
a) No início, cabeça da lista void ColocaElementoCabecaLista(char a){
ELEM aux = new ELEM(a); aux.next=Lista; Lista=aux;
}
b) No fim, cauda da lista void ColocaElementoCaudaLista(char a){
ELEM aux = new ELEM(a);
ELEM w=Lista; while(w.next!=null){ w=w.next;
}
w.next=aux;
}
Inicio, Cabeça

Fim, Cauda

Função (método) remoção em listas simples
a) No início, cabeça da lista char RetiraElementoCabecaLista(){ char tmp = Lista.info;
Lista=Lista.next;
return (tmp);
}
b) No fim, cauda da lista char RetiraElementoCaudaLista(){
char