Construindo uma lista duplamente encadeada ou ligada

Nesse tópico vou mostrar o modo de se construir uma lista duplamente encadeada chamada também de LinkedList, esse tipo de estrutura permite
criar uma lista da qual todos os seus elementos estão ligados pela referência de seu elemento anterior, todo elemento numa LinkedList tem uma referência ao próximo elemento da lista e ao elementos anterior na lista, o mesmo ocorre nas extremidades dessa estrutura (inicio e final), no caso do primeiro elemento a referência anterior do mesmo será um valor null, e no caso do último elemento da lista a referência para seu próximo elemento será um valor null também.

Veja a imagem abaixo:



Repare que o primeiro elemento dessa lista está apontando para o próximo, em cada célula ou nodo dessa lista, existe o elemento(dado) em questão, e a referência para o próximo e anterior.
Esta lista possui inicio e fim, o que a difere de uma lista circular que é infinita, a cada novo elemento adicionado nessa lista ocorre a contabilização do mesmo, existe um atributo na lista duplamente encadeada que serve para fazer a contagem de elementos na mesma, este também serve como controle de tamanho e é usado como referência num laço de repetição (por exemplo um for) do qual o índice pode começar em 0 e ir até ser menor do que o total de elementos dessa lista.

A Lista Duplamente Encadeada é composta por duas classes, a classe Célula (que é chamada também na literatura de Nodo, ou Elemento) e a classe de Lista Duplamente Encadeada, esta é a classe aonde ocorrem as operações de adicionar ou remover elementos no inicio, no final, ou por índice na lista, métodos de retornar o tamanho de uma lista, métodos que retornam o primeiro ou o último elemento dessa lista, métodos para verificar se algum elemento existe na lista (método de consulta), e também métodos especiais, que não existem no pacote de código fonte de uma LinkedList em java mas podem ser criados para ordenar uma lista (método ordenarPorBubble), reverter os elementos da lista(método inverter lista), subList (método que cria uma sub-lista a partir de uma lista) e também métodos para transformar a mesma numa lista circular.

Primeiramente vou mostrar como é feita a composição de uma Célula ou Nodo nessa lista, segue-se a classe que eu denominei Nodo, primeiramente será postado todo o código fonte da mesma e em seguida será explicado como é feita:

Classe Nodo:

Código:

public class Nodo {
   
   private Nodo proxima;
   private Nodo anterior;
   
   private Object dado;
   
   public Nodo(Object dado) {
      this.dado = dado;
   }
   
   public Nodo() {
      // Default Constructor
   }
   
   public Object getDado() {
      return dado;
   }
   
   public Nodo getAnterior() {
      return anterior;
   }
   
   public void setAnterior(Nodo anterior) {
      this.anterior = anterior;
   }
   
   public void setProximo(Nodo proxima) {
      this.proxima = proxima;
   }
   
   public Nodo getProximo() {
      return proxima;
   }
   
   public void setDado(Object dado) {
      this.dado = dado;
   }
   
   
   @Override
   public String toString() {
   
      return ""+dado ;
   }
   
   
}

Está é classe aonde compõe-se os dados, os atributos da mesma são próxima e anterior (que são do tipo Nodo mesmo), e um atributo dado( do tipo Object).

Código:

private Nodo proxima;
private Nodo anterior;
   
private Object dado;

Por boa prática de programação, esses atributos ficam como private, e são criados posteriormente seus métodos get e set para o uso indireto dos mesmos,

Código:

public Object getDado() {
      return dado;
   }
   
   public Nodo getAnterior() {
      return anterior;
   }
   
   public void setAnterior(Nodo anterior) {
      this.anterior = anterior;
   }
   
   public void setProximo(Nodo proxima) {
      this.proxima = proxima;
   }
   
   public Nodo getProximo() {
      return proxima;
   }
   
   public void setDado(Object dado) {
      this.dado = dado;
   }

Também é criado um novo construtor além do construtor padrão, nele existe apenas um parâmetro de entrada que é o dado em si.

Código:

public Nodo(Object dado) {
      this.dado = dado;
   }

Também é sobrescrito o método toString do qual retorna o dado como uma String (método usado para fazer comparação entre os elementos de uma lista no método ordenarPorBubble, este será postado mais tarde).
O método toString não tem nenhum parâmetro de entrada e retorna uma String, ele serve para que possa ser impresso no console da IDE o valor do elemento que consta na célula (aqui citado como Nodo).

Em suma, esta é a classe Nodo, a parte mais interna da estrutura, será mostrada a seguir a classe Lista Duplamente Encadeada, o procedimento será o mesmo da outra classe, primeiramente é postado o código, e em seguida o mesmo será explicado passo a passo.

Segue a classe de Lista Duplamente Encadeada, aqui denominada como LinkedDoubleList:

Código:

public class LinkedDoubleList {
   
   
   private Nodo begin;
   private Nodo end;
   
   private int totalElements=0;
   
   public LinkedDoubleList() {
      // Default Constructor
   }
   
   
   
   public void deQueue(){
      
      removeInBegin();
   }
   
        public void addInBegin(Object dado){
      
      Nodo novo = new Nodo(dado);
      
      if (totalElements == 0) {
         
         begin = end = novo;
      }
      
      novo.setProximo(begin);
      begin.setAnterior(novo);
      begin = novo;
      
      totalElements ++;
   }
   
   public void addInEnd(Object dado) {
      
      Nodo novo = new Nodo(dado);
      
      if (totalElements == 0 ) {
         begin = end = novo;
      }
      
      end.setProximo(novo);
      novo.setAnterior(end);
      end = novo;
      
      totalElements++;
      
   }
   
   
   
   public Object removeInEnd(){
      
      if (totalElements ==1) {
         Nodo aux = new Nodo();
         aux = end;
         
         begin = end = null;
         
         totalElements --;
         return aux;
      }
      else if(totalElements>0){
         Nodo aux = new Nodo();
         aux = end;
         end = end.getAnterior();
         totalElements--;
         return aux;
      }
      else return null;
   }
   
   
   public Nodo removeInBegin() {
      
      if (totalElements==1) {
         
         Nodo aux = new Nodo();
         aux = begin;
         
         begin = end = null;
         totalElements--;
         return aux;
      }
      else if(totalElements>0) {
         Nodo aux = new Nodo();
         aux = begin;
         begin = begin.getProximo();
         
         totalElements--;
         return aux;
         
      }
      else return null;
   }
   
   public Nodo getFirstElement() {
      return begin;
   }
   
   public Nodo getLastElement() {
      return end;
   }
   
   public int getTotalElements(){
      
      return this.totalElements;
   }
   
   @Override
   public String toString()
   {
      if(totalElements==0) return("[]");
      
      String s = "[";
      for(Nodo aux = begin; aux!= end; aux=aux.getProximo()){
         
         s += aux.getDado().toString()+", ";
      }
      s+= end.getDado()+"]";
      
      return s;
   }
   
   
   public boolean contemElemento(Object dado){
      
      for (Nodo i = begin ; i != null; i= i.getProximo()) {
         
         if (i.getDado().equals(dado)) {
            return true;
         }
         
      }
      return false;
   }
   
   private Nodo getElemento(int indice){
      
      Nodo aux = begin;
      
      if(indice >= totalElements){
         return null;
      }
      for (int i = 0; i < indice; i++){
         
         aux = aux.getProximo();
      }
      return aux;
   }
   
   public void addForIndex(int indice, Object dado){
      if(indice==0){
         addInBegin(dado);
      }
      else if(indice == totalElements){
         addInEnd(dado);
      }
      else{
         
         Nodo novo = new Nodo(dado);
         
         Nodo anterior = this.getElemento(indice -1);
         Nodo proxima = anterior.getProximo();
         
         novo.setProximo(anterior.getProximo());
         novo.setAnterior(anterior);
         anterior.setProximo(novo);   
         proxima.setAnterior(novo);
         totalElements++;
      }
   }
}

Existe dois atributos do tipo Nodo nessa classe, o atributo begin e end, que indicam o início e o fim da lista, ambos, por boa prática de programação, também estão private, existe também outro atributo, este é do tipo int (inteiro), ele indica o número total de elementos que constam na lista, ele está também, por boa pratica de programação private, trata-se de um contador, e o mesmo é inicializado com o valor 0.

Código:

private Nodo begin;
   private Nodo end;
   
   private int totalElements=0;

   
   Explicando os métodos da classe:

   addInBegin(int):

O primeiro método que vou apresentar é o addInBegin(int), este método não retorna nenhum valor, e tem como parâmetro um dado do tipo Object,
dentro do método é instanciado um objeto do tipo Nodo, na inicialização do mesmo é passado o dado (... new Nodo(dado);), logo depois ocorre uma validação, esta verifica se o número total de elementos é igual a 0, caso sim o primeiro e o último elemento da lista vão receber o objeto do tipo Nodo:

Código:

if (totalElements == 0) {
         
         begin = end = novo;
      }

Caso mais de 0 elementos na lista ocorre um algoritmo do qual configurará as referências da lista, ou seja, o novo elemento apontará para o início da lista (novo.setProximo(begin);), o inicio da lista apontará para o novo elemento (begin.setAnterior(novo);) e em seguida o novo elemento passará a ser o novo início da lista (begin = novo;) e o número total de elementos será incrementado (totalElements ++;).

  Veja o Desenho Abaixo:



   Segue também o algoritmo do método:

Código:

      public void addInBegin(Object dado){
      
      Nodo novo = new Nodo(dado);
      
      if (totalElements == 0) {
         
         begin = end = novo;
      }
      
      novo.setProximo(begin);
      begin.setAnterior(novo);
      begin = novo;
      
      totalElements ++;
   }

   addInEnd(int):


Este método é bastante semelhante ao anterior, também tem como parâmetro de entrada um dado do tipo Object e dentro do mesmo também é instanciado um objeto do tipo Nodo, e no construtor deste também será colocado o dado, também ocorre a validação do número total de elementos e no caso de haver 0, também o início e fim receberão o novo elemento.
A diferença se encontra no algoritmo a seguir do qual o final apontará para o novo elemento (end.setProximo(novo);), o novo elemento apontará
para o final (novo.setAnterior(end);), e o final receberá o novo elemento (end = novo;), assim como em seguida o contador será incrementado,
o que ocorre por trás dessa ideia, de forma semelhante ao método addInBegin, é o apontamento do novo elemento a uma das extremidades da lista,
o apontamento recíproco dessas extremidades da lista ao novo elemento, e a questão desse novo elemento tornar-se o início ou o fim da lista, a grosso modo o que ocorre é um duplo apontamento para que a lista fique ligada sempre como um todo e o update do final ou começo da lista para um novo elemento.

   Segue-se outra ilustração para explicação:




   Segue-se também o algoritmo do método:

Código:

   public void addInEnd(Object dado) {
      
      Nodo novo = new Nodo(dado);
      
      if (totalElements == 0 ) {
         begin = end = novo;
      }
      
      end.setProximo(novo);
      novo.setAnterior(end);
      end = novo;
      
      totalElements++;
      
   }

   Método removeInEnd():

Esse método serve para remover o último elemento da lista, ele retorna o Nodo removido, ou seja, ele removerá o Nodo que contém o dado e a referência anterior e próxima e em seguida mostrará esse dado que foi removido, como o tipo de dado que retorna é um objeto do tipo Nodo (classe criada anteriormente) o mesmo poderá ser adicionado em uma outra lista ou até mesmo numa lista temporária num programa, cabe ao programador decidir seu melhor uso, ou simplesmente usá-lo para remover algum valor em questão .
Dentro do método ocorre uma primeira validação, a mesma irá verificar se o número total de elementos é igual a 1, caso seja será instanciado
um objeto que irá servir como um objeto auxiliar, este receberá o último elemento da lista (aux = end;), logo em seguida tanto o final como o começo da lista recebem um valor null, ou seja, caso exista somente um elementos, a lista ficará sem nenhum valor, logo após é decrementado o valor total de elementos, e retorna-se objeto auxiliar.
Caso o número total de elementos seja maior do que 1, ocorre a instanciação de outro objeto auxiliar e o mesmo receberá o último valor da lista, (aux = end;), o último valor da lista receberá o seu anterior (end = end.getAnterior();) passando a ter um novo valor, em seguida o número total de elementos será decrementado e será retornado o objeto auxiliar, enfim, o que ocorre nesse método, é a passagem de valor de um último elemento para um objeto auxiliar,e caso o número total de elementos seja maior do que 1, o elemento end recebe seu valor anterior, quando se sai do método o objeto auxiliar é perdido, porque ele só existe dentro daquele método e naquela interação, essa é a maneira pela qual ocorre a exclusão de um valor numa lista duplamente encadeada.

   Segue-se o algoritmo do método abaixo:

Código:

   public Object removeInEnd(){
      
      if (totalElements ==1) {
         Nodo aux = new Nodo();
         aux = end;
         
         begin = end = null;
         
         totalElements --;
         return aux;
      }
      else if(totalElements>0){
         Nodo aux = new Nodo();
         aux = end;
         end = end.getAnterior();
         totalElements--;
         return aux;
      }
      else return null;
   }

CONTINUA...