Então pessoal, estou tentando implementar uma lista encadeda. Para isso uso uma classe No. A lista tá funcionando belezinha, mas minha dúvida é a seguinte eu usei o método getNo para pegar a referência ao próximo do próx…

Lista encadeada

wbsouza 1 de ago. de 2004

Os metodos get e set são uma convenção "padronização". Na verdade não há nada que ligue o seu getNo com No :shock:

Vai aí um "prototipo" do que deveria ser ...

public class No { 
    No proximo; 
    Object data; 

    public No(No pai) {
      pai.proximo = this;  
    }

    public No getProximo() { 
        return proximo;
    } 
}

[]s, Welington B. Souza

W

Wonder 1 de ago. de 2004

A lista simplesmente encadeada é a mais básica de todas as estrutura de dados. Uma lista simplesmente encadeada é uma seqüência de objetos alocados dinamicamente, cada qual fazendo referencia ao seu sucessor na lista. Apesar de simplicidade obvia, existem diversas variações de implementação

A figura (b) ilustra o esquema de lista simplesmente encadeada que escolhemos para implementação. São Utilizados duas estrutura inter-relacionada. Os elementos da lista são representados com o uso de instâncias da classe LinkedList.Element, que compreende dois campos, datum e next. O primeiro é empregado para fazer referência aos objetos da lista; o ultimo é um ponteiro para o elemento seguinte da lista. A estrutura principal é uma instância da classe LinkedList, que também compreende dois campos, head e tail, que se referem ao primeiro e ultimo elemento da lista, respectivamente

package datastruct;

/**
 * <p>Title: Data Struct</p>
 * <p>Description: Data Struct</p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: www.woniz.com</p>
 * @author Wonder Alexandre Luz Alves
 * @version 1.0
 * <p>
 * <p>
 * Implementação de uma lista simplesmente encadeada
 */

public class LinkedList {
     /**
      * referencia para o primeiro elemento da lista
      */
     protected Element head;

     /**
      * referencia para o ultimo elemento da lista
      */
     protected Element tail;

     /**
      * contrutor vazio
      */
     public LinkedList() {
     }

     /**
      * metodo que esvazia uma lista ligadas
      */
     public void purge() {
          head = null; //referencia do incio da lista
          tail = null; //referencia do final da lista
     }

     /**
      * metodo de acesso ao Elemento do inicio da lista
      * @return Element - retorna o primeiro elemento da lista
      */
     public Element getHead() {
          return head;
     }

     /**
      * metodo de acesso ao ultimo elemento da lista
      * @return Element - ultimo elemento da lista
      */
     public Element getTail() {
          return tail;
     }

     /**
      * retorna true se a lista for vazia e false se não
      * @return retorna true se a lista for vazia e false se não
      */
     public boolean isEmpty() {
          return (head == null);
     }

     /**
      * pega o dado do primeiro elemento da lista
      * @return retorna o dado do primeiro elemento da lista
      */
     public Object getFirst() {
          if (head == null)
               throw new NullPointerException();
          return head.datum;
     }

     /**
      * pega o dado do ultimo elemento da lista
      * @return retorna o dado do ultimo elemento da lista
      */
     public Object getLast() {
          if (tail == null)
               throw new NullPointerException();
          return tail.datum;
     }

     /**
      * inicializando a lista ligada
      * @param item
      */
     public void prepend(Object item) {
          Element tmp = new Element(item, head);
          if (tmp == null)
               tail = tmp;
          head = tmp;
     }

     /**
      * inserindo um novo elemento no final da lista
      * @param item
      */
     public void append(Object item) {
          Element tmp = new Element(item, null);
          if (head == null)
               head = tmp;
          else
               tail.next = tmp;
          tail = tmp;
     }

     /**
      * esvazia a lista e preenche a mesma com uma outra lista preenchida
      * @param list
      */
     public void assign(LinkedList list) {
          if (list != this) {
               purge();
               for (Element ptr = list.head; ptr != null; ptr = ptr.next) {
                    append(ptr.datum);
               }
          }
     }

     /**
      * retirando um elemento da lista
      * @param item
      */
     public void extract(Object item) {
          Element ptr = head;
          Element prevPtr = null;
          while (ptr != null && ptr.datum != item) {
               prevPtr = ptr;
               ptr = ptr.next;
          }
          if (ptr == null) {
               throw new NullPointerException();
          }
          if (ptr == head)
               head = ptr.next;
          else
               prevPtr.next = ptr.next;
          if (ptr == tail)
               tail = prevPtr;
     }



     /**
      *
      * <p>Title: Data Struct</p>
      * <p>Description: Data Struct</p>
      * <p>Copyright: Copyright (c) 2004</p>
      * <p>Company: www.woniz.com</p>
      * @author Wonder Alexandre Luz Alves
      * @version 1.0
           * {@docroot} class interna para representar os elementos de uma lista encadeadas
      */
     public final class Element {

          /**
           * atributo para armazenar os dados da lista
           */
          private Object datum;

          /**
           * referencia para o proximo elemento da lista
           */
          private Element next;

          /**
           * Contrutor da class
           * @param datum
           * @param next
           */
          public Element(Object datum, Element next) {
               this.datum = datum;
               this.next = next;
          }

          /**
           * metodo que pega os dados da lista
           * @return <Object> retorna os dados da lista
           */
          public Object getDatum() {
               return datum;
          }

          /**
           * metodo que pega o proximo Elemento
           * @return <Element> retorna o proximo elemento da lista
           */
          public Element getNext() {
               return next;
          }

          /**
           * metodo que insere um objeto depois de um elemento arbitrario da lista
           * @param item
           */
          public void insertAfter(Object item) {
               next = new Element(item, next);
               if (tail == this)
                    tail = next;
          }

          /**
           * metodo que insere um objeto antes de um elemento arbitrario da lista
           * @param item
           */
          public void insertBefore(Object item) {
               Element tmp = new Element(item, this);
               if (this == head)
                    head = tmp;
               else {
                    Element prevPtr = head;
                    while (prevPtr != null && prevPtr.next != this)
                         prevPtr = prevPtr.next;
                    prevPtr.next = tmp;
               }
          }

     } /* fim da class interna */

}

baixe o fonte da classe LinkedList

Luiz-SP 1 de ago. de 2004

Desculpa pessoal, mas eu postei o códio errado na verdade é isso:

class No { 
   No proximo; 
   Object data; 

   public No getNo ( No no) { 
      return no; 
   } 

   public No getProximo(){
        return proximo;
   }

}

Achou que não me espressei bem, minha dúvida não é em relação a lista, o que não entendi é como esse método me retornou um referência ao proximo do próximo do próximo. Algo como:

No - proximo - proximodoproximo
Usando assim:
[code]
noqualquer = noqualquer.getNoFinal(noqualquer.getProximo);
[/code/

pcalcado 1 de ago. de 2004

HEIM :shock: ?!?!

Que tal um vetor?

[]s

MarcoFloriano 18 de nov. de 2008

Wonder, os métodos da sua lista me ajudaram muito aqui, obrigado fera !

L

lucas_sa 18 de nov. de 2008

e ai mano blz ??

da uma olhada nesta apostila explica tudo direitinho …

abraco…

6 Respostas

Topicos relacionados