Lista Encadeada (Linked List)
Gabarito: letra A. Em uma lista encadeada simples, cada nó (célula) armazena um dado (objeto) e um ponteiro (referência) para o próximo nó da sequência. Essa é a definição fundamental da estrutura. As demais alternativas distorcem ou contradizem as propriedades conhecidas das listas encadeadas.
Alternativa | Afirmação | Análise | Veredito |
|---|
A | Cada célula contém um objeto e o endereço da célula seguinte. | Corresponde exatamente à definição de uma lista encadeada simples. | ✅ Correta (Gabarito) |
B | A lista encadeada sempre ocupa uma quantidade fixa de memória, independentemente do número de elementos. | Falso: a alocação é dinâmica, proporcional ao número de nós. | ❌ Incorreta |
C | Inserção no meio da lista encadeada é menos eficiente que em um array dinâmico. | Falso: na lista encadeada a inserção no meio é O(1) (com referência), enquanto no array dinâmico é O(n). | ❌ Incorreta |
D | A lista encadeada é ideal para acesso aleatório rápido aos elementos. | Falso: o acesso aleatório é O(n), ao contrário do array que é O(1). | ❌ Incorreta |
E | Os elementos são armazenados em posições contíguas de memória. | Falso: os nós são alocados individualmente e não necessariamente contíguos. | ❌ Incorreta |
Alternativa A — ✅ Correta ⟵ GABARITO
Corresponde exatamente à definição de uma lista encadeada simples: cada célula contém o elemento (objeto) e um link (endereço) para a célula seguinte. Essa estrutura permite crescimento dinâmico e inserções/remoções eficientes desde que se conheça a posição anterior.
Alternativa B — ❌ Incorreta
Afirma que a lista ocupa quantidade fixa de memória, independentemente do número de elementos. Isso é falso: uma lista encadeada aloca memória dinamicamente para cada novo nó, e o espaço ocupado é proporcional ao número de elementos. A característica de tamanho fixo é típica de arrays (vetores), não de listas ligadas.
Alternativa C — ❌ Incorreta
Diz que a inserção no meio da lista encadeada é menos eficiente que em um array dinâmico. Na verdade, é o oposto: em uma lista encadeada, uma vez obtido o nó anterior, a inserção no meio é O(1) (apenas ajuste de ponteiros). Em um array dinâmico, inserir no meio exige deslocar todos os elementos posteriores, resultando em O(n). Portanto, a lista encadeada é mais eficiente para inserções no meio, desde que a referência já esteja disponível.
Alternativa D — ❌ Incorreta
Afirma que a lista encadeada é ideal para acesso aleatório rápido. Isso é característica de arrays, que permitem acesso direto por índice em O(1). Em uma lista encadeada, para acessar o k-ésimo elemento é necessário percorrer os nós um a um, resultando em O(n). Logo, não é adequada para acesso aleatório.
Alternativa E — ❌ Incorreta
Diz que os elementos são armazenados em posições contíguas de memória. Isso descreve arrays (vetores), nos quais os elementos ocupam um bloco contínuo. Em listas encadeadas, cada nó é alocado individualmente e pode estar em qualquer região da memória; os nós são ligados por ponteiros, sem contiguidade.
Gabarito: letra A — a única alternativa que corresponde corretamente à definição clássica de uma lista encadeada.