Programando com estruturas de dados e padrões de projeto

Uma das principais atividades da computação é o processamento de dados. Esta atividade exige técnicas eficientes para organizar e acessar esses dados na memória das máquinas, de maneira que operações como inclusão, pesquisa e remoção de dados sejam facilitadas de acordo com as necessidades da aplicação. Para resolver esta categoria de problemas existem muitas soluções, chamadas de estruturas de dados. Dentre estas soluções, uma das mais utilizadas, por ser bastante adaptável e simples, é a lista encadeada. Em uma lista, os dados podem ser inseridos e removidos em qualquer ordem e em qualquer posição, diferentemente de outras estruturas, como o caso das filas e das pilhas, nas quais a ordem de inserção e remoção é determinada pelo algoritmo e não pela aplicação que o está utilizando.

A maioria das estruturas de dados podem ser implementadas utilizando-se vetores, porém isso impõe uma limitação de tamanho e é conveniente apenas quando se conhece antecipadamente a quantidade máxima de elementos que serão armazenados na mesma, como acontece nos buffers utilizados em processos de comunicação. Para os casos em que não se conhece a quantidade de elementos que serão inseridos, é indicada a utilização de uma lista encadeada, cujo princípio de funcionamento é a criação de ligações ou apontadores entre os seus elementos. Estes apontadores guardam a sequência dos elementos na lista e são utilizados para viabilizar a navegação e acesso a cada um dos elementos presentes.

As ligações entre os elementos da lista formam na memória uma estrutura como a apresentada na Figura 1. Quando as ligações são estabelecidas em apenas um sentido, a lista é chamada de simplesmente encadeada, e quando as ligações são estabelecidas nos dois sentidos, conforme a Figura 2, diz-se que a lista é duplamente encadeada. O exemplo construído ao longo deste artigo é o de uma lista duplamente encadeada.

Para implementar estas ligações se faz necessária a declaração de uma classe que contenha referências a objetos da própria classe. Estas auto-referências representam as conexões entre os elementos mostradas na Figura 1. A classe que representa os elementos de dados como ilustrado nas caixas da mesma figura, também chamados de nós da lista, deve guardar os dados referentes à correspondente posição da lista, e para não ser necessário alterar o código dela a cada novo tipo de dado a ser armazenado, recomenda-se adotar um tipo de referência que possa ser utilizada com qualquer tipo de dado que por ventura venha a ser armazenado na lista. Deste modo, é declarado um atributo do tipo Object, que é a superclasse para todas as classes definidas em Java, permitindo com isso que qualquer objeto seja tratado como sendo do tipo Object (uma alternativa ao uso do atributo deste tipo é a parametrização de classes, o que será assunto em um próximo artigo). A classe que representa o nó de uma lista duplamente encadeada é apresentada na Listagem 1.

class No{
        public No proximo;
        public No anterior;
        public Object dado;
  
        public No(Object obj){
              proximo = null;
              anterior=null;
              dado=obj;
        }
  
        No(Object obj, No prox, No ant)
        {
              proximo = prox;
              anterior = ant;
              dado = obj;
        }
}

Para a classe No mostrada na listagem 1, foram definidos dois construtores: um para o caso no qual ainda não se sabe quais são os elementos aos quais o novo ...