Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESPE / CEBRASPE 2019

Estrutura de dados: lista duplamente encadeada

Gabarito: letra C. A descrição do enunciado — "cada um dos elementos, com exceção dos elementos inicial e final, referencia sempre outros dois, um que o antecede e outro que o sucede" — é a definição exata de uma lista duplamente encadeada (doubly linked list). Nessa estrutura, cada nó (elemento) armazena dois ponteiros: um para o nó anterior e outro para o próximo, permitindo a navegação bidirecional.

Análise das alternativas

Alternativa A — ❌ Incorreta (lista circular)

Em uma lista circular, o último elemento referencia o primeiro (e vice-versa, se for duplamente encadeada), o que contraria a exceção mencionada ("com exceção dos elementos inicial e final").

Alternativa B — ❌ Incorreta (grafo)

Um grafo é uma estrutura não linear em que os vértices podem ter um número arbitrário de conexões (arestas), não se limitando a exatamente dois vizinhos (antecessor e sucessor).

Alternativa C — ✅ Correta ⟵ GABARITO

Na lista duplamente encadeada, cada nó possui referências para o nó anterior (prev) e para o nó seguinte (next). O primeiro nó não tem anterior (prev = null) e o último não tem seguinte (next = null). Exatamente como descrito.

Alternativa D — ❌ Incorreta (árvore)

Em uma árvore, cada nó (exceto a raiz) tem exatamente um predecessor (pai), mas pode ter vários sucessores (filhos), e não apenas dois.

Alternativa E — ❌ Incorreta (pilha)

Uma pilha (stack) é uma estrutura linear onde cada elemento referencia apenas o próximo (ou apenas o anterior, dependendo da implementação), e não os dois sentidos.

Gabarito: letra C.