Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — Gama Consult 2024

Listas Encadeadas: Operações e Complexidades

Gabarito: letra D. Inserir um elemento no início de uma lista encadeada é uma operação de tempo constante O(1), pois envolve apenas a criação de um novo nó e o ajuste de dois ponteiros (o novo nó aponta para a antiga cabeça e a cabeça passa a ser o novo nó), independentemente do tamanho da lista. As demais alternativas contêm erros comuns sobre listas encadeadas, confundindo-as com outras estruturas ou atribuindo complexidades incorretas.

Alternativa A — ❌ Incorreta

A descrição corresponde a uma lista circular, não a uma lista encadeada simples. Em uma lista encadeada simples, cada elemento aponta para o próximo, e o último elemento aponta para null (ou equivalente). O ciclo só ocorre se a lista for explicitamente circular.

Alternativa B — ❌ Incorreta

Listas encadeadas não são mais eficientes que arrays para acessar elementos por índice arbitrário. Arrays permitem acesso direto (O(1)) por meio de cálculo de endereço, enquanto listas encadeadas exigem percorrer os elementos a partir do início até a posição desejada (O(n)).

Alternativa C — ❌ Incorreta

Acessar o n-ésimo elemento de uma lista encadeada tem complexidade O(n), não O(1). É necessário percorrer sequencialmente os n-1 primeiros nós para chegar ao n-ésimo.

Alternativa D — ✅ Correta ⟵ GABARITO

A inserção no início de uma lista encadeada realiza-se em O(1): cria-se um novo nó, seu ponteiro next é ajustado para o atual primeiro nó, e a referência de cabeça da lista é atualizada para o novo nó. Nenhum deslocamento ou realocação é necessário, ao contrário de um array, onde inserir no início exige deslocar todos os elementos (O(n)).

Gabarito: letra D