Artigos Java Programando com estruturas de dados e padrões de projeto

Por que eu devo ler este artigo:Este artigo apresenta uma explicação do funcionamento de uma das estruturas de dados mais utilizadas no desenvolvimento de aplicações, a lista encadeada. Esta análise será feita de forma crescente, construindo ao final uma solução mais sofisticada e que contemple as características descritas no Padrão Iterator, que é utilizado para permitir o acesso aos dados sem que seja necessário expor características de implementação da estrutura de dados utilizada. Para isso, iniciaremos com o desenvolvimento de uma versão simples, porém funcional, da lista encadeada, a partir da qual pequenos incrementos serão realizados até que se obtenha o resultado desejado.

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.

Representação das ligações entre os elementos de uma lista encadeada

Figura 1. Representação das ligações entre os elementos de uma lista 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.

Listagem 1. Código da classe No.

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 nó da lista estará ligado, como no caso de se estar instanciando o primeiro nó da lista (portanto os atributos que representam as conexões ao próximo nó e ao nó anterior são inicializados como null, indicando que este elemento não está ligado a outros nós da lista); e outro construtor para o caso em que já se sabe a quais elementos o novo nó estará ligado, como nos casos de elementos a serem inseridos no meio da lista (portanto, as ligações com os seus vizinhos são inicializadas com as respectivas referências passadas como parâmetros ao construtor e armazenadas nos atributos correspondentes). Em ambos os casos, a referência ao objeto que representa o dado a ser armazenado no nó é recebida como parâmetro.

A lista encadeada é definida não apenas pelos nós que representam os seus elementos, mas também pelas operações que são realizadas nestes elementos/nós. Portanto, são necessários métodos para inserir, consultar e remover elementos da lista encadeada. Para representar a lista também se faz necessária a declaração de uma classe, na qual estes métodos serão implementados. Além disso, a implementação da classe também precisa conhecer os seus nós inicial e final. Resumindo, uma lista duplamente encadeada é constituída de elementos ou nós, conectados entre si em uma determinada sequência (definida pela aplicação que faz uso da lista) e também de duas referências, que indicam dentre os elementos armazenados na lista qual é o primeiro e qual é o último, como está representado na Figura 2.

Representação de uma lista duplamente encadeada

Figura 2. Representação de uma lista duplamente encadeada.

A classe que representa a lista duplamente encadeada é apresentada na Listagem 2, porém, sem as implementações correspondentes aos métodos de inserção, remo ...

Quer ler esse conteúdo completo? Tenha acesso completo