terça-feira, 26 de fevereiro de 2008

Estruturas de dados com JAVA - Lista duplamente encadeada

Neste post, vou colocar um exemplo de implementação de uma lista duplamente encadeada:

primeiro vamos definir a estrutura de dado para cada nó da lista:


package estruturas_de_dados;
public class DNode {

private String element;
private DNode prev;
private DNode next;

public DNode(String s, DNode p, DNode n) {
setElement(s);
setPrev(p);
setNext(n);
}

public String getElement() {
return element;
}

public void setElement(String element) {
this.element = element;
}

public DNode getPrev() {
return prev;
}

public void setPrev(DNode prev) {
this.prev = prev;
}

public DNode getNext() {
return next;
}

public void setNext(DNode next) {
this.next = next;
}


}




Após definir a estrutura de dado, vamos então implementar a lista duplamente encadeada:


package estruturas_de_dados;

public class DList {

private int size;
private DNode head;
private DNode trailer;

public DList() {
size = 0;
head = new DNode("", null, null);
trailer = new DNode("", head, null);
head.setNext(trailer);
}

public int getSize() {
return size;
}

public boolean isEmpty() {
return (size == 0);
}

public DNode getFirst() throws IllegalArgumentException {
if (isEmpty())
throw new IllegalArgumentException();
return head.getNext();
}

public DNode getLast() throws IllegalArgumentException {
if (isEmpty())
throw new IllegalArgumentException();
return trailer.getPrev();
}

public DNode getPrev(DNode v) throws IllegalArgumentException {
if (v == head)
throw new IllegalArgumentException();
return v.getPrev();
}

public DNode getNext(DNode v) throws IllegalArgumentException {
if (v == trailer)
throw new IllegalArgumentException();
return v.getNext();
}

public void addFirst(DNode v) {
addAfter(head, v);
}

public void addLast(DNode v) {
addBefore(trailer, v);
}

public void addAfter(DNode v, DNode z) {
DNode u = getNext(v);
v.setNext(z);
u.setPrev(z);
z.setNext(u);
z.setPrev(v);
size++;
}

public void addBefore(DNode v, DNode z) {
DNode u = getPrev(v);
v.setPrev(z);
u.setNext(z);
z.setPrev(u);
z.setNext(v);
size++;
}

public void remove(DNode v) {
DNode u = getPrev(v);
DNode w = getNext(v);

u.setNext(w);
w.setPrev(u);

v.setNext(null);
v.setPrev(null);

size--;
}

public boolean hasPrev(DNode v) { return (v != head); }

public boolean hasNext(DNode v) { return (v != trailer); }

}



Agora um exemplo de utilização da lista, inserindo elementos e navegando na lista:


public class Principal {

private DList lista;

/** Creates a new instance of Principal */
public Principal() {
lista = new DList();

DNode aux = null;
DNode node = new DNode("A", null, null);

lista.addFirst(node); aux = node;

node = new DNode("B", null, null);
lista.addAfter(aux, node); aux = node;

node = new DNode("C", null, null);
lista.addAfter(aux, node); aux = node;
}

public void printLista() {
DNode node = lista.getFirst();
do {
System.out.println( "Elemento:" + node.getElement() );
node = lista.getNext(node);
} while (lista.hasNext(node));
}

public static void main(String[] args) {
Principal me = new Principal();
me.printLista();
}

}

4 comentários:

  1. fica dando erro quando compilo, dizeno que não acha a classe DList

    ResponderExcluir
  2. meu, podia ter pelo menos 1% de codigo comentado.

    ResponderExcluir
  3. Maurício,
    as classes estão todas em um mesmo projeto, utilizando o classpath correto?
    Para evitar este tipo de problemas, tente criar seu projeto no Eclipse.
    Como você pode ver, a classe DList foi declarada no segundo bloco de código.

    ResponderExcluir
  4. alguem pode responder e explicar essa questão pra mim:


    Implemente a classe FilaDE esboçada abaixo, incluindo os métodos
    indicados, considerando que a fila é implementada como uma lista duplamente encadeada.
    Desconsidere a existência de uma classe que represente a lista duplamente encadeada; pode usar
    a classe NodoDE apresentada em sala. O método main deve conter as seguintes
    funcionalidades: 1) criar uma fila vazia; 2) inserir os elementos “maria”, “jose”, “joao”; 3)
    imprimir o conteúdo da fila; 4) remover dois elementos; 4) inserir os elementos “rita”,
    “antonio”; 5) imprimir o conteúdo da fila; 6) imprimir o tamanho da fila.

    public class FilaDE{
    private NodoDE front, back;
    private int tamanho;
    public FilaDE(){
    front = back = null;
    tamanho = 0;
    }
    public void enqueue(Object e){}
    public void dequeue(){}
    public int getTamanho(){}
    public void imprimeFila(){}
    public static void main(String[] args){}
    }



    a classe NodoDE citada eh:


    public class NodoDE{
    public Object elem;
    public NodoDE prox;
    public NodoDE ant;
    public NodoDE(Object e, NodoDE p, NodoDE a){
    elem = e;
    prox = p;
    ant = a;
    }

    public void setProx(NodoDE p){ prox = p; }

    public void setAnt(NodoDE a){ ant = a; }

    public NodoDE getProx(){ return prox; }
    public NodoDE getAnt(){ return ant; } // metodos acessadores e modificadores para elemento
    }

    ResponderExcluir