Please enable JavaScript.
Coggle requires JavaScript to display documents.
C++ - Coggle Diagram
C++
Linked Lists
Definição
Lista encadeada com alocação dinâmica de memória
Estrutura
Nós (Link) contendo:
Dado (element)
Ponteiro para o próximo nó (next)
Vantagens
Crescimento dinâmico
Inserção/remoção eficientes (O(1) quando posição é conhecida)
Operações
Inserção: O(1)
Remoção: O(1)
Acesso por posição: O(n) (precisa percorrer a lista)
Array-Based List Implementation
Definição
Lista como uma sequência ordenada de elementos
Implementação baseada em array
Estrutura da Classe AList
Array listArray para armazenar elementos
Tamanho máximo maxSize
Tamanho atual listSize
Posição atual curr
Operações
Inserção
No final: O(1)
No início/meio: O(n) (requer deslocamento dos elementos)
Remoção
No final: O(1)
No início/meio: O(n) (requer deslocamento dos elementos)
Acesso direto a elementos: O(1)
Comparação entre Implementações
Array-Based List
Vantagens: Acesso direto eficiente (O(1))
Desvantagens: Inserção e remoção caras (O(n))
Linked List
Vantagens: Inserção e remoção rápidas (O(1))
Desvantagens: Acesso a elementos lento (O(n))
Critérios de Escolha
Tamanho variável → Lista Encadeada
Acesso frequente por índice → Array-Based List
Element Implementations
Armazenamento de elementos
Cópia direta do elemento
Uso de ponteiros para elementos complexos
Homogeneidade
Listas homogêneas (mesmo tipo de dado)
Listas heterogêneas (diferentes tipos de dados)
Gerenciamento de Memória
Uso de ponteiros pode exigir limpeza manual de memória
Cuidado com vazamento de memória ao remover elementos