Preciso estudar sempre: Listas encadeadas em Java

Olá caros leitores do blog Preciso Estudar Sempre, o tópico desta semana será sobre listas encadeadas. Escolhi esse tema porque acredito que é importante e porque não me lembro de ter falado sobre tal antes.

O conhecimento deste assunto é de grande importância no desenvolvimento de software pois, as listas encadeadas possuem uma estrutura bem diferente das listas tradicionais. Tal estrutura que pode nos ajudar em certas situações.

Antes que você se impressione com o assunto, eu já digo: "Fique tranquilo". Este tema é de fácil entendimento. Porém, é necessário de um pouco de conhecimento de programação.

Para os que já conhecem o assunto ou que já ouviram falar, já aviso que não falarei sobre listas duplamente encadeadas ou listas circulares porque senão o post ficará muito extenso e massante.

No Java, já existem estruturas prontas para listas encadeadas. Estou falando da LinkedList, clique aqui para ver a documentação. Mas, nesse post iremos criar nossa própria estrutura de lista encadeada.

Para realizar este estudo não é necessário ter uma IDE super moderna. Se você quiser usar o notepad não tem problema.

Primeiro, vamos entender o conceito das listas encadeadas. As listas tradicionais tem suas células organizadas todas juntas e posicionadas uma atrás da outra. Isso lhes garante velocidade em buscas e acesso randômico, ou seja, eu posso acessar qualquer posição que eu queira. Porém, existe uma desvantagem nesta estrutura. Quando eu preciso inserir ou remover elementos no meio da lista, o trabalho para reconstruir a lista com todos elementos é muito grande visto que, eu preciso remover os elementos que virão após o novo/removido elemento e depois recolocá-los, formando assim uma lista maior/menor.

http://voidexception.weebly.com/uploads/1/1/9/4/11944659/4652147_orig.jpg

Com as listas encadeadas não existe este problema porque suas células são organizadas de forma diferente. Nas listas tradicionais, cada elemento não tem conhecimento do próximo elemento ou do anterior porque estão todas juntas dentro da estrutura. Nas lista encadeadas, não. Cada elemento está "solto" na memória. Então, agora, você fica com aquela dúvida.

"Se os elementos estão soltos, como a lista é montada ? "

A resposta é simples, cada elemento possui uma referência somente para o próximo elemento. Como se formassem uma corrente, como se estivessem ligados (daí que vem o nome Linked List). Na figura abaixo, temos um exemplo perfeito de como é essa lista.

http://www.ime.usp.br/~pf/algoritmos/xfig/lista2a.gif

Os elos da lista são formados por ponteiros que possuem a referência para o próximo elemento. Quando não existe a referência para o próximo elemento, o ponteiro assume o valor nulo. Abaixo, temos uma relação de vantagens e desvantagens dessa estrutura.

Vantagens:

Linked lists são estruturas de dados dinâmicos que alocam a memória necessária enquanto o programa está funcionando.
Operações de inserir e deletar células (nodes) são facilmente implementadas.
Estruturas de dados lineares tais como, pilhas e filas são facilmente executadas com uma lista encadeada.
Eles podem reduzir o tempo de acesso e podem aumentar em tempo real sem overhead de memória.

Desvantagens:

Tem tendência de desperdiçar memória pelo fato dos ponteiros pediram novo espaço de armazenamento.
Nós em uma lista encadeada devem ser lidos do início.
Dificuldades surgem em listas encadeadas quando se tente percorrê-la de trás para frente. Tal tarefa é extremamente complicado. Adicionar um backpointer (ponteiro de ré) causa desperdício de memória.

Agora que já sabemos como a lista encadeada funciona, vamos ao exemplo prático. Nós criaremos uma lista encadeada que representa uma escala de indicação de empregos, ou seja, uma pessoa indica a outra para uma vaga de emprego mas, ela só pode indicar 1 pessoa e só conhece a pessoa que indicou.

Crie a classe Pessoa. Esta classe representa a pessoa.

 package pkg;  

 public class Pessoa { 
      private Integer id; 
      private String nome; 
      private String email; 
      public Pessoa() { 

      } 

      public Pessoa(Integer id, String nome, String email) { 
           this.id = id; 
           this.nome = nome; 
           this.email = email; 
      } 

      public Integer getId() { 
           return id; 
      } 

      public void setId(Integer id) { 
           this.id = id; 
      } 

      public String getNome() { 
           return nome; 
      } 

      public void setNome(String nome) { 
           this.nome = nome; 
      } 

      public String getEmail() { 
           return email; 
      } 

      public void setEmail(String email) { 
           this.email = email; 
      } 

      @Override 
      public String toString() { 
           return "Pessoa [id=" + id + ", nome=" + nome + ", email=" + email + "]"; 
      } 
 }

Crie a classe Celula. Esta classe representa a célula (posição ou node) da lista. Como vimos acima, cada célula precisa da referência do próximo e isso é feito através do atributo proximo.

 package pkg;  

 public class Celula { 
      private Celula proximo; 
      private Pessoa valor; 
      public Celula getProximo() { 
           return proximo; 
      } 

      public void setProximo(Celula proximo) { 
           this.proximo = proximo; 
      } 

      public Pessoa getValor() { 
           return valor; 
      } 

      public void setValor(Pessoa valor) { 
           this.valor = valor; 
      } 
 }

Crie a classe ListaEncadeada. Esta classe representa a lista encadeada. Note que ela não guarda suas células em nenhum tipo de array ou vetor. As únicas referências que ela tem para suas células são os atributos primeiro e ultimo. A partir deste dois atributos, será realizada as operações na lista. O atributo posicaoAtual é usado para as operações iteração e recuperação do objeto do laço.

 package pkg;  
 public class ListaEncadeada { 
      private Celula primeiro; 
      private Celula ultimo; 
      private Celula posicaoAtual; 
      /** 
       * Adiciona uma pessoa no fim da lista. 
       * @param valor 
       */ 
      public void adicionar(Pessoa valor){ 
           Celula celula = new Celula(); 
           celula.setValor(valor); 
           if(primeiro == null && ultimo == null){ 
                primeiro = celula; 
                ultimo = celula; 
           } else { 
                ultimo.setProximo(celula); 
                ultimo = celula; 
           } 
      } 
      /** 
       * Remove uma pessoa do fim da lista. 
       */ 
      public void remover(){ 
           if(primeiro.getProximo() != null){ 
                Celula celula = this.recuperarPenultimo(this.primeiro); 
                ultimo = celula; 
                celula.setProximo(null); 
           } else { 
                primeiro = ultimo = null; 
           } 
      } 
      /** 
       * Recupera o penultimo elemento da lista 
       * @param celula 
       * @return 
       */ 
      private Celula recuperarPenultimo(Celula celula){ 
           if(celula.getProximo().equals(ultimo)){ 
                return celula; 
           } 
           return recuperarPenultimo(celula.getProximo()); 
      } 
      public boolean temProximo(){ 
           if(primeiro == null){ 
                return false; 
           } else if (posicaoAtual == null){ 
                posicaoAtual = primeiro; 
                return true; 
           } else { 
                boolean temProximo = posicaoAtual.getProximo() != null ? true : false; 
                posicaoAtual = posicaoAtual.getProximo(); 
                return temProximo; 
           } 
      } 
      public Celula getPosicaoAtual(){ 
           return this.posicaoAtual; 
      } 
 }

Agora, crie a classe Principal. Esta classe contém o método main e a partir dele, chamamos os método da lista.

 package pkg;  
 public class Principal { 
      public static void main(String[] args) { 
           ListaEncadeada listaEncadeada = new ListaEncadeada(); 
           Principal principal = new Principal(); 
           principal.adicionarPessoa(listaEncadeada); 
           principal.remover(listaEncadeada); 
           while(listaEncadeada.temProximo()){ 
                System.out.println(listaEncadeada.getPosicaoAtual().getValor()); 
           } 
      } 
      private void adicionarPessoa(ListaEncadeada listaEncadeada){ 
           Pessoa p1 = new Pessoa(1, "João", "jp@gmail.com"); 
           Pessoa p2 = new Pessoa(2, "Maria", "maria@gmail.com"); 
           Pessoa p3 = new Pessoa(3, "Bruno", "bruno@gmail.com"); 
           Pessoa p4 = new Pessoa(4, "José", "jose@gmail.com"); 
           Pessoa p5 = new Pessoa(5, "Mário", "mario@gmail.com"); 
           Pessoa p6 = new Pessoa(6, "Eduardo", "dudu@gmail.com"); 
           listaEncadeada.adicionar(p1); 
           listaEncadeada.adicionar(p2); 
           listaEncadeada.adicionar(p3); 
           listaEncadeada.adicionar(p4); 
           listaEncadeada.adicionar(p5); 
           listaEncadeada.adicionar(p6); 
      } 
      private void remover(ListaEncadeada listaEncadeada){ 
           listaEncadeada.remover(); 
           listaEncadeada.remover(); 
           listaEncadeada.remover(); 
      } 
 }

Não entrei muito a fundo nas operações que são possíveis realizar em uma lista encadeada porque, eu ficaria um mês todo escrevendo este post e no fim disponibilizaria uma API muito extensa. O meu intuito com esse post é apenas dar um guia introdutório do assunto visando, dar insumos suficientes para que os leitores possa andar "pelas suas próprias pernas".

Para baixar o projeto completo, clique aqui.

Sugestões ? Críticas ? Elogios ? Deixe aí nos comentários ou na página do facebook.

https://www.facebook.com/precisoestudarsempre/

Referências:
http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html
http://en.wikipedia.org/wiki/Linked_list
http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html