ATPS

4.0 Listas com Vetores: Desvantagens
 Tamanho máximo fixo
 Mesmo vazias ocupam espaço grande de memória
 Mesmo que utilizemos um vetor de ponteiros, se quisermos prever uma lista de 10.000 elementos, teremos 40.000 bytes desperdiçados.
 Operações podem involver muitos deslocamentos de dados:
 Inclusão em uma posição ou no início
 Exclusão em uma posição ou no início
4.1 Listas Encadeadas
 São listas onde cada elemento contido em uma lista está armazenado em um TAD chamado elemento de lista.
 Cada elemento de lista referencia o próximo e só é alocado dinamicamente quando é necessário
 Para referenciar o primeiro elemento utilizamos um TAD cabeça de lista. 4.1.1 Modelagem de Dados
Cabeça de Lista
 Necessitamos:
 Um ponteiro para o primeiro elemento da lista.
 Um inteiro para indicar quantos elementos a lista possue.
 Pseudo-código: tipo Lista { Elemento *dados; inteiro tamanho;
};
Elemento de Lista
• Necessitamos:
 Um ponteiro para o próximo elemento da lista.
 Um campo do tipo da informação que vamos armazenar.
• Pseudo-código: tipo Elemento { Elemento *próximo; tipo-que-eu-vou-usar-nesta-aplicação info;
};
4.1.2 Listas Encadeadas: Modelagem de Dados Genérica
 Para tornar todos os algoritmos da lista mais genéricos, fazemos o campo info ser um ponteiro para um elemento de informação. Modelagem: Elemento de Lista II
 Pseudo-código II: tipo Elemento { Elemento *próximo; TipoInfo *info;
};
tipo TipoInfo { tipo-do-campo1 campo1; tipo-do-campo2 campo2; ? tipo-do-campoN campoN;
}
 Razões para a modelagem do TipoInfo:
 Vamos na maioria dos algoritmos trabalhar com algum elemento de infomação.
 Se este elemento é somente um ponteiro para um TipoInfo, não importando o que este seja, teremos algoritmos totalmente genéricos.
 Posso usar o mesmo código de lista para muitas aplicações diferentes simplesmente recompilando.
 Desvantagens:
 O