Please enable JavaScript.
Coggle requires JavaScript to display documents.
Abstract Data Types and Data Structures, Linked Lists, Lists, Array-Based…
Abstract Data Types and Data Structures
Definição de termos
Coleção de valores (ex.: tipo Booleano, inteiros).
DATA TYPE
Implementações de tipos de dados
Implementações tradicionais para tipos de dados (ex.: lista encadeada, lista baseada em array).
Array como estrutura física (bloco contíguo de memória com itens de tamanho fixo).
Array como tipo lógico de dados (coleção homogênea com índices).
Implementações alternativas (ex.: matriz esparsa).
data structure
Implementação de um ADT.
Em linguagens orientadas a objetos, ADT e implementação formam uma classe.
Operações do ADT implementadas como métodos.
Variáveis necessárias para um item de dado: membros de dados.
Objeto: Instância de uma classe.
Linked Lists
Nós de lista
A lista é composta por nós.
Cada nó é um objeto distinto (não apenas uma célula em um array).
Criação de uma classe de nós (Link) para reuso em outras estruturas de dados.
mplementação da classe Link:
Campos: element (valor do elemento) e next (ponteiro para o próximo nó).
Construtores com e sem valor inicial para o elemento.
singly linked list
Cada nó tem um ponteiro para o próximo nó.
Representação gráfica
Exemplo de lista encadeada com quatro inteiros.
Uso de ponteiro NULL para indicar fim da lista.
Uso de ponteiros para implementar a lista.
Alocação dinâmica de memória conforme necessário.
Lists
Características
Lista vazia não contém elementos.
Cabeça (início) e cauda (final).
Comprimento da lista.
Operações com listas
Inserir, remover e acessar elementos.
Crescer e diminuir a lista.
Relações entre elementos:
Listas ordenadas têm elementos em ordem de valor.
Listas não ordenadas não têm relação entre posições e valores.
Sequência finita e ordenada de elementos (posições).
Cada elemento tem um tipo de dado.
Array-Based List Implementation
Lista baseada em array (AList)
Implementação de classe AList que herda de List.
Usa array listArray para armazenar elementos.
Atributos privados da AList
listArray: Array para armazenar elementos da lista.
maxSize: Tamanho máximo permitido para a lista.
listSize: Quantidade atual de elementos na lista.
curr: Posição atual.
Representação da lista
Operações eficientes:
Acesso aleatório a qualquer elemento em tempo Θ(1).
Operação de anexar elementos (append) em Θ(1).