Please enable JavaScript.
Coggle requires JavaScript to display documents.
Listas - Coggle Diagram
Listas
Tipo (classe)
Abstract Data Types (ADT)
Forma lógica
Estrutura de dados
Forma física (implementação do ADT)
Coleção de valores
Listas Ligadas
(linked lists)
Possuí ponteiros que conectam ao próximo elemento da lista
Simple x Double
Enquanto o simples contém apenas
o ponteiro para o próximo
, o duplo contém um
ponteiro para o anterior
Circular
O ultimo elemento tem um ponteiro para o primeiro
Memória dinâmica (não precisa alocar um espaço determinado de memória)
Não possui tamanho máximo mas espaço da memória é consumido por ponteiros
Acesso sequencial
Ao perder um elemento se perde sua conexão à lista, perdendo a lista toda
Array
Representações de memória simples
Espaço ocupado na memória já predefinido (desses, os espaços não usados vão ficar desocupados)
Possui tamanho máximo
Guarda elementos na memória em sequência
Acesso randômico
Filas
First In First Out
(fila de banco)
Insert (no final) e Remove (o primeiro)
Usada para imprimir na ordem certa ou monitorar uma fila de produção
Pilas
Last In First Out
(pilha de pratos)
Push e Pop (ambos no final)
Usada para recursão e registras ações anteriores (Ctrl Z)
Sequência de elementos
homogêneos
Exemplo: contém apenas strings
Complexidade
Varia para cada computador, seus processadores e sua velocidade
Worst-case analysis
(mais comum)