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();
    }
    
}