Estruturas de Dados

1. Vetores (Arrays)

Vetores Não Ordenados

  • Elementos armazenados sem ordem específica
  • Inserção sempre no final
  • Busca linear O(n)
  • Remoção requer deslocamento de elementos

Vetores Ordenados

  • Elementos mantidos em ordem crescente/decrescente
  • Inserção requer encontrar posição correta e deslocar elementos
  • Busca binária possível O(log n)
  • Vantagens: busca rápida, facilita operações como união e interseção

Alocação de Memória

Tipo Descrição Exemplo
Estática Tamanho fixo definido em tempo de compilação int vetor[10];
Dinâmica Tamanho definido em tempo de execução (malloc) int *v = malloc(10 * sizeof(int));

2. Estruturas (Structs)

Agrupamento de variáveis de tipos diferentes sob um único nome. Permite criar tipos de dados personalizados.

Exemplo:

struct Aluno {
    char nome[50];
    int idade;
    float nota;
};

Ponteiros para structs permitem passagem por referência e alocação dinâmica.

3. Listas Encadeadas

Lista Simplesmente Encadeada

  • Cada nó contém dados e ponteiro para próximo nó
  • Vantagens: tamanho dinâmico, inserções/remoções eficientes
  • Desvantagens: acesso sequencial, maior uso de memória
5
→
10
→
15
→
NULL

Lista Duplamente Encadeada

  • Cada nó contém ponteiros para anterior e próximo
  • Permite navegação bidirecional
  • Mais eficiente para remoções em posições arbitrárias
NULL
⇄
5
⇄
10
⇄
15
⇄
NULL

Operações Básicas

Operação Complexidade
Inserir no início O(1)
Inserir no fim O(n)
Buscar elemento O(n)
Remover elemento O(n)

4. Pilhas e Filas

Pilhas (LIFO)

  • Último a entrar é o primeiro a sair
  • Operações básicas: push (empilhar) e pop (desempilhar)
  • Complexidade: O(1) para ambas operações
  • Aplicações: chamadas de função, undo/redo, avaliação de expressões

Filas (FIFO)

  • Primeiro a entrar é o primeiro a sair
  • Operações básicas: enqueue (enfileirar) e dequeue (desenfileirar)
  • Complexidade: O(1) para ambas operações
  • Implementações: com vetor (tamanho fixo ou circular) ou com lista encadeada

Fila com Prioridade

  • Elementos com maior prioridade são atendidos primeiro
  • Pode ser implementada com duas filas separadas ou usando heap
  • Complexidade: inserção O(log n), remoção O(1)
  • Aplicações: escalonamento de processos, algoritmos como Dijkstra

5. Comparação de Estruturas

Estrutura Vantagens Desvantagens Melhor Caso de Uso
Vetor Acesso rápido por índice, baixo overhead Tamanho fixo, inserções/remoções custosas Quando o tamanho é conhecido e há muitos acessos aleatórios
Lista Encadeada Tamanho dinâmico, inserções/remoções eficientes Acesso sequencial, maior uso de memória Quando o tamanho varia muito e há muitas inserções/remoções
Pilha Operações rápidas O(1), simples Acesso limitado ao topo Chamadas de função, undo/redo, avaliação de expressões
Fila Operações rápidas O(1), ordem justa Acesso limitado às extremidades Processamento em ordem de chegada, buffers

Dicas Importantes

Otimização de Busca

Para vetores grandes com muitas buscas, prefira ordenados com busca binária

Inserções/Remoções

Para aplicações com muitas inserções/remoções, prefira listas encadeadas

Gerenciamento de Memória

Sempre libere memória alocada dinamicamente com free()

Desempenho

Use passagem por referência (ponteiros) para structs grandes para melhor desempenho

Ver Atividade no GitHub