Listas 2 Encadeada

Listas

Prof. Rodrigo Brasileiro [e-mail] Lista


Uma lista (ou sequência) é uma estrutura na qual os elementos Seguem uma ordem
 1º elemento, 2º elemento, ...N-ésimo elemento



Podem se repetir



A lista cresce / diminui dinamicamente



Exemplo: uma lista de números inteiros

Lista Dinâmica Encadeada




É um tipo de “Lista” onde cada elemento aponta para o seu sucessor na “Lista”
Usa um objeto para o próximo elemento da lista e uma indicação de final de lista

Lista Dinâmica Encadeada




Cada elemento da lista é tratado como um objeto que é alocado dinamicamente, a medida que os dados são inseridos Assim, fica fácil mudar quem está no início da lista mudando a referência do objeto

Vantagens



Melhor utilização dos recursos de memória
Não precisa movimentar os elementos nas operações de inserção e remoção

Desvantagens



Acesso indireto aos elementos
Necessidade de percorrer a lista para acessar um elemento (não é um vetor!!!)
 É preciso pegar referência do próximo objeto até chegar no nó desejado

Quando utilizar essa “Lista”




Não há necessidade de garantir um espaço mínimo para a execução do aplicativo
Inserção / remoção em lista ordenada são as operações mais frequente

Exemplo – Lista encadeada

Exemplo – Lista duplamente encadeada

Exemplo – Lista duplamente encadeada




Não há necessidade de garantir um espaço mínimo para a execução do aplicativo
Inserção / remoção em lista ordenada são as operações mais frequente

Exemplo – Código

Exemplo – Código


ListaInt listaInt = new ListaInt(1);

Exemplo – Código



ListaInt listaInt = new ListaInt(1); listaInt.inserir(3); Exemplo – Código


listaInt.remover(5);

Exemplo – Código






ListaInt listaInt = new ListaInt(1); listaInt.inserir(3); listaInt.inserir(9); listaInt.inserir(5); listaInt.inserir(9);

Exemplo – Código


listaInt.remover(3);

Exemplo – Código


listaInt.remover(3);

9

9

Exemplo – Código


listaInt.remover(3);

Lista de