Como Implementar uma Lista Circular em Java

Uma lista circular é uma lista ordenada (encadeada) onde o item após o último é o primeiro, e o item anterior ao primeiro é o último. É um caso curioso de algoritmos que, não menos curiosamente, reflete uma infinidade de situações reais. Exemplos:

1. O itinerário de um ônibus circular. Ao chegar ao último ponto, o ônibus não pára nem volta pelo caminho contrário, mas sim continua em frente e alcança o primeiro ponto, de onde partiu inicialmente, perfazendo todo o caminho de novo.
2. Os dias da semana ou os meses do ano. Após o último, vem sempre o primeiro de novo, reiniciando um novo ciclo.
3. A roleta de um jogo. Percorrida seqüencialmente, após completar um círculo completo a roleta volta à primeira posição.

Listas circulares são associadas a qualquer situação onde haja um ciclo característico. E periodizar ou repetir as coisas é uma característica extremamente humana ("Tenho fases, como a lua", lembrando o "Lua Adversa", de Cecília Meireles ou, quem sabe, de outras poetisas...).
Listas circulares têm grande aplicação em jogos, manipulação de imagens, manipulação de streams e arquivos, vários sistemas humanos, além de milhares de outras ocasiões.
A classe abaixo implementa a criação de uma lista circular em Java a partir de um ArrayList. Não é uma classe Thread-safe, assim como o ArrayList também não o é, mas é um exemplo razoavelmente completo, testado e seguro que você poderá utilizar livremente em muitas situações. Se você utilizar esta classe em seus programas e sistemas, por favor, faça as referências do seu autor, data, etc, conforme mostrado no javadoc. Considere-a lançada sob licença LGPL.


FONTE: http://pastebin.com/NSw67CbW

Note que esta classe se comporta exatamente como um ArrayList, podendo inclusive ser construída a partir de qualquer Collection. No entanto, existem 3 métodos de navegação que implementam o comportamento circular da lista:

getActual(): retorna o objeto atual. Existe um índice interno que controla a navegação. Assim, você poderá navegar passo a passo pela lista, indo tanto na direção progressiva (para frente) quanto na direção regressiva (para trás). Cada vez que a lista é percorrida, este índice interno é alterado. Se precisar pegar o objeto que corresponde exatamente à posição onde o índice está parado no momento, este método faz isto por você!

next(): retorna o próximo objeto, caminhando com o índice para frente e posicionando-o sobre este objeto retornado. Como é uma lista circular, se você está no último item da lista e dá um "next()", então você receberá o primeiro item da lista, mantendo a característica cíclica da mesma.

previous(): faz o mesmo que o next(), mas em direção oposta: retorna o objeto anterior, caminhando com o índice para trás e posicionando-o sobre este objeto retornado. Como é uma lista circular, se você está no primeiro item da lista e dá um "previous()", então você receberá o último item da lista, mantendo a característica cíclica da mesma.

Além destes métodos, o método get(int index), que já existe na superclasse, foi sobrescrito de forma que nunca lance ArrayIndexOutOfBoundsException, ou seja, qualquer índice que seja passado vai sempre retornar um elemento dentro da lista, calculado circularmente de acordo com o total de elementos da lista. Assim, é seguro usar uma lista como esta dentro de um laço arbitrário, onde o índice do laço é bem maior que a lista. Como exemplo, imagine que você quer desenhar um quadro de tamanho 100x100 com apenas 3 cores que se repetem. Você poderia muito bem fazer:

// Lista circular com 3 elementos apenas!!
CircularArrayList circularList = new CircularArrayList(colors);

for (int i=0; i<100;>

Bom, esta classe ainda pode ser mais aprimorada, se for de seu interesse. Possíveis melhorias seriam:

• Métodos como "moveTo(int newIndex)" e "moveTo(E element)", que reposiciona o índice em uma posição arbitrária. É útil se a navegação tender a se tornar mais alternada que seqüencial, especialmente se a lista for grande.
• Métodos "first()" e "last()", se houver necessidade.
  
• Uma versão desta classe completamente Thread-safe e otimizada para bom desempenho!! Isto seria de fato uma grande contribuição!!

Espero ter ajudado com este artigo!! Qualquer coisa, COMENTEM!!!