Listas duplas e circulares: variações da corrente

Andar nos dois sentidos

A lista ligada simples tem uma limitação incômoda: ela é uma via de mão única. Cada nó só sabe quem vem depois, nunca quem vem antes. Se você está no meio da corrente e precisa voltar um nó, azar: tem que recomeçar da cabeça. A lista duplamente ligada resolve isso dando a cada nó duas ligações, uma apontando para o próximo e outra para o anterior. Agora a corrente é uma via de mão dupla: de qualquer nó você anda para frente ou para trás. Isso torna barato remover um nó tendo apenas ele em mãos, porque a ligação para o anterior está ali, sem precisar procurar quem apontava para você.

A corrente que não termina

A lista circular ataca outra limitação: o fim. Numa lista comum, o último nó aponta para o nada, e chega. Na circular, o último nó aponta de volta para o primeiro, e a corrente vira um anel sem começo nem fim claros. Isso serve quando o dado é naturalmente cíclico. Pense num carrossel de jogadores que reveza a vez: depois do último, volta ao primeiro, para sempre. Ou numa playlist em modo repetir, que ao acabar recomeça. O detalhe delicado é percorrer uma lista circular: como não há o nada para servir de parada, um laço ingênuo roda para sempre. Você precisa de outra condição, por exemplo parar quando voltar ao nó de onde começou.

// percorrer uma lista circular sem laco infinito
inicio <- cabeca
atual <- cabeca
repita
  escreva(atual.valor)
  atual <- atual.proximo
ate atual == inicio   // parou ao voltar ao ponto de partida
// sem essa condicao, o anel giraria para sempre

Na circular não há o nada para parar. A condição de parada é voltar ao nó inicial.

// lista circular: A -> B -> C -> (volta para A)
inicio <- A
atual <- A
repita
  escreva(atual.valor)
  atual <- atual.proximo
ate atual == inicio

Cada variação no seu lugar

Nenhuma variação é gratuita, e por isso a simples ainda é o ponto de partida. Cada ligação a mais é memória a mais em todo nó e mais uma coisa para manter certa: numa lista duplamente ligada, ao inserir ou remover, você precisa ajustar as duas ligações dos vizinhos, não só uma, e esquecer metade gera bug. A circular pede sempre atenção à condição de parada. A regra prática é usar a variação mais simples que resolve o problema. Se você nunca anda para trás, a lista simples basta. Se precisa de navegação nos dois sentidos, como o histórico de avançar e voltar, a dupla compensa. Se o dado gira em ciclo, a circular é natural. A estrutura acompanha a forma do problema, nunca o contrário.