Módulo 02
Estruturas Sequenciais
Inserção, Remoção e Busca
Armazenar dados é apenas parte do problema. Uma estrutura precisa permitir que novos elementos sejam inseridos, elementos existentes sejam removidos e valores sejam localizados. Em estruturas sequenciais, essas operações mostram claramente a relação entre posição, deslocamento e complexidade.
Operações fundamentais
Modificar e Consultar uma Sequência
Em um vetor, a posição de cada elemento importa. Inserir ou remover em uma posição interna pode alterar a posição de vários elementos, enquanto uma busca precisa decidir como localizar o valor desejado.
Inserção
Adiciona um elemento. Em posições internas, é preciso abrir espaço deslocando dados.
Remoção
Elimina um elemento. O espaço deixado pode exigir o deslocamento dos elementos seguintes.
Busca
Localiza um valor. A ordenação pode permitir algoritmos muito mais eficientes.
Modelo mental: inserir é abrir espaço, remover é
fechar espaço e buscar é reduzir o conjunto de posições possíveis.
Abrindo espaço
Inserção em Estruturas Sequenciais
Inserir no fim de um vetor com capacidade disponível é simples. Inserir no início ou no meio exige preservar a ordem, deslocando os elementos para a direita.
Inserção no fim
O novo elemento ocupa a próxima posição disponível.
O(1) sem realocaçãoInserção no meio
Os elementos posteriores avançam para abrir uma posição.
O(n) no pior casoInserção no início
Todos os elementos existentes precisam avançar.
O(n)O vetor possui capacity = 10. Compare quantos elementos precisam mudar de posição dependendo do local escolhido para a operação.
Compare inserir no início, no meio e no fim.
Por que deslocar da direita para a esquerda?
Na inserção, começamos pelo último elemento e avançamos em direção à posição desejada. Assim, nenhum valor é sobrescrito antes de ser copiado para sua nova posição.
O que acontece quando o vetor está cheio?
Em um array fixo não há espaço adicional. Em um vetor dinâmico pode ocorrer uma realocação: cria-se um bloco maior, os elementos são movidos e a região antiga é liberada.
Fechando o espaço
Remoção
Se queremos manter a sequência compacta, remover um elemento interno exige trazer os elementos posteriores uma posição para a esquerda.
Remover no fim
Nenhum outro elemento muda de posição.
O(1)Remover no meio
Os elementos posteriores precisam preencher o espaço vazio.
O(n) no pior casoRemover no início
Todos os elementos restantes avançam uma posição.
O(n)
Quanto mais perto do início estiver a operação, maior tende a ser o custo.
A posição modifica a quantidade de dados que precisam ser deslocados.
Encontrando valores
Busca Linear vs. Busca Binária
Para destacar melhor a diferença, o alvo desta demonstração é o último valor do vetor: 92. Assim, a busca linear percorre praticamente toda a sequência, enquanto a busca binária divide o vetor em intervalos cada vez menores até chegar ao resultado.
Vetor principal
Divisões / passos da busca
Escolha Preparar linear ou Preparar binária. Depois, avance com
Próximo passo ou deixe a animação rodar com Auto executar.
Busca linear — O(n)
Começa no primeiro elemento e avança sequencialmente. Quando o valor procurado está no final, a busca linear precisa comparar quase todos os elementos.
Busca binária — O(log n)
A cada comparação, observamos o elemento do meio e descartamos metade do intervalo. Visualmente, isso aparece como uma sequência de subdivisões até restar um único candidato.
Por que o último número é um bom exemplo?
Porque ele torna a diferença mais evidente: na busca linear, o caso fica quase máximo; na binária, mesmo um valor no fim ainda é encontrado com poucas comparações.
Resumo de desempenho
Complexidade das Operações
| Operação | Melhor caso | Pior caso | Explicação |
|---|---|---|---|
| Inserção no fim com capacidade | O(1) | O(1) | Escreve na próxima posição livre. |
| Inserção no início | O(n) | O(n) | Desloca todos os elementos. |
| Inserção interna | O(1)* | O(n) | Depende da posição. |
| Remoção do último | O(1) | O(1) | Nenhum deslocamento. |
| Remoção no início | O(n) | O(n) | Desloca os elementos restantes. |
| Busca linear | O(1) | O(n) | Pode precisar percorrer tudo. |
| Busca binária | O(1) | O(log n) | Reduz o intervalo à metade. |
* Uma inserção interna só se aproxima de O(1) quando a posição está no final
e há capacidade disponível. O custo de uma posição qualquer depende de quantos elementos vêm depois dela.
Aplicação prática
Inserção, Remoção e Busca em C++17
Inserir no fim
#include <vector>
std::vector<int> valores{10, 20, 30};
valores.push_back(40); // final
valores.insert(valores.begin() + 1, 15); // posição 1Inserir no meio
#include <vector>
std::vector<int> valores{10, 20, 30, 40};
valores.pop_back(); // remove o último
valores.erase(valores.begin() + 1); // remove a posição 1Remover
#include <algorithm>
#include <vector>
std::vector<int> valores{10, 20, 30, 40};
auto it = std::find(valores.begin(), valores.end(), 30);
if (it != valores.end()) {
int indice = static_cast<int>(it - valores.begin());
}Busca linear
int alvo = 92;
int indice_encontrado = -1;
for (int i = 0; i < static_cast<int>(valores.size()); ++i) {
if (valores[i] == alvo) {
indice_encontrado = i;
break;
}
}Busca binária manual
int esquerda = 0;
int direita = static_cast<int>(valores.size()) - 1;
while (esquerda <= direita) {
int meio = esquerda + (direita - esquerda) / 2;
if (valores[meio] == alvo) {
indice_encontrado = meio;
break;
}
if (valores[meio] < alvo)
esquerda = meio + 1;
else
direita = meio - 1;
}Modelo mental
O Que Você Precisa Guardar
Resumo: em estruturas sequenciais, a posição determina o custo de inserções
e remoções. Na busca, a propriedade decisiva é a ordenação.