Algoritmos e Estrutura de Dados · FGV · 2026 | Questão sqc-fg127328

Complexidade de operações em estruturas de dados

Gabarito: letra B. A Lista Duplamente Encadeada permite inserção e remoção no meio com complexidade O(1) quando já se possui um ponteiro para a posição desejada, pois basta ajustar os ponteiros dos nós adjacentes — não há necessidade de deslocar elementos. Essa é a principal vantagem sobre as demais estruturas listadas.

A questão testa a compreensão das características fundamentais de cada estrutura de dados, especialmente o custo das operações de inserção e remoção em posições arbitrárias. A banca explora a diferença entre estruturas com acesso indexado (arrays) e estruturas encadeadas.

Estrutura de Dados	Inserção/Remoção no Meio (com ponteiro conhecido)	Acesso Indexado	Ordem Sequencial
Array Estático	O(n) — desloca elementos	O(1)	Sim
Lista Duplamente Encadeada	O(1) — ajusta ponteiros	O(n)	Sim
Tabela Hash	Não se aplica (sem índice linear)	O(1) médio	Não
Array Dinâmico	O(n) — desloca elementos	O(1)	Sim
Árvore Binária de Busca	O(log n) — rebalanceamento	O(log n)	Sim (in-order)

Alternativa A — ❌ Incorreta

Arrays estáticos têm tamanho fixo e exigem deslocamento de todos os elementos à direita (ou à esquerda) para inserir/remover no meio, resultando em O(n) no pior caso. O acesso indexado é O(1), mas a operação pedida não é acesso e sim modificação no meio.

Alternativa B — ✅ Correta ⟵ GABARITO

Na lista duplamente encadeada, cada nó possui ponteiros para o anterior e o próximo. Com um ponteiro direto para o nó alvo, inserir um novo nó antes ou depois exige apenas reatribuir ponteiros locais — operação de tempo constante, O(1), independentemente do tamanho da lista.

Alternativa C — ❌ Incorreta

Tabelas hash oferecem inserção, remoção e busca O(1) em média, mas não mantêm uma ordem sequencial acessível para “meio da lista”. A posição não é determinada por um índice linear; a operação de inserir em uma posição específica (como o meio) não é natural e, se forçada, exigiria percorrer a estrutura, o que degrada a complexidade.

Alternativa D — ❌ Incorreta

Arrays dinâmicos (como ArrayList em Java ou list em Python) oferecem acesso O(1) por índice, mas inserir ou remover no meio requer o deslocamento de todos os elementos subsequentes, resultando em O(n). A realocação do array quando a capacidade se esgota também pode custar O(n) amortizado, mas a operação no meio é sempre O(n).

Alternativa E — ❌ Incorreta

Uma árvore binária de busca (ABB) equilibrada, como AVL ou Rubro-Negra, permite inserção e remoção em O(log n), mas não O(1). Além disso, a localização do “meio” não é direta: é necessário percorrer a árvore até o nó desejado. A ABB é otimizada para buscas e ordenação, não para modificações em posições arbitrárias.

PEGA ESSA DICA!

Associe rapidamente: se a operação exige deslocamento físico de elementos → array; se ajusta ponteiros localmente → lista encadeada. Inserir/remover no meio de uma lista com ponteiro conhecido é o exemplo clássico de O(1) em listas duplamente encadeadas.

Gabarito: letra B.