Wie lässt sich eine doppelt verkettete Liste implementieren?

Die Klasse ListElem repräsentiert im Beispiel die Knoten. Sie enthält insgesamt drei Felder: Zwei Instanzvariablen verweisen jeweils auf den nächsten und den vorhergehenden Knoten, Object obj zeigt auf den Inhalt des Knotens. Man bezeichnet solche Klassen als rekursiv, da sie Elemente des eigenen Typs enthalten. Ergänzt wird die Klasse nur noch durch die üblichen Getter- und Setter-Methoden.

class ListElement {

    Object obj;
    ListElement nextElem, prevElem;

    public ListElement(Object obj) {
        this.obj = obj;
        nextElem = null;
    }

    public void setNextElem(ListElement nextElem) {
        this.nextElem = nextElem;
    }
    
    public void setPrevElem(ListElement prevElem) {
        this.prevElem = prevElem;
    }

    public ListElement getNextElem() {
        return nextElem;
    }
    
    public ListElement getPrevElem() {
        return this.prevElem;
    }

    public Object getObj() {
        return obj;
    }
} 

Die Klasse DoppeltVerketteteListe stellt die eigentliche Listenimplementierung dar. ¹ In ihr werden zunächst zwei Listenelemente, der 'Kopf' und der 'Schwanz' angelegt. Sie verweisen als Nachfolge- und Vorgängerelemente gegenseitig auf sich. Die Methode getFirstElem() liefert den Kopf der Liste, die Methode getLastElem() durchläuft die Liste und gibt das letzte Element zurück.
In addLast(Object o) wird das letzte Element über das Durchlaufen der Liste ermittelt und dies mit einem neuen Listenelement so verknüpft, dass dies als Nachfolger des ehemals letzten, nunmehr vorletzten Elementes dient.
Die Methode insertAfter(Object prevItem, Object newItem) fügt ein neues Listenelement nach einem vorgegebenen Element ein. Hierzu wird als erstes das erste Element hinter dem Kopf in der Variablen pointerElem abgelegt. Die Liste wird anschließend von vorne nach hinten so lange durchlaufen, bis der Einfügepunkt erreicht wird. Er wird über den Inhalt der Elemente ermittelt. Hier liegt ein Haken dieser Listenimplementierung: Der Inhalt eines Listenelementes muss in der Liste einmalig sein. Falls dies nicht der Fall ist, wird als Einfügepunkt das Element mit dem ersten Vorkommen des entsprechenden Inhaltes verwendet.
Ist der Einfügepunkt erreicht, wird ein neu gebildetes Listenelement mit dem Einfügepunkt als Vorgängerelement und dem dem Einfügepunkt nachfolgenden als Nachfolgeelement verbunden. Wichtig ist hierbei, dass die Verbindungen auch bei den bereits vorhandenen Elementen entsprechend erfolgen.

Ähnlich aufgebaut ist die Methode insertBefore(Object insertItem, Object newItem). Auch hier wird die Liste durchlaufen, der Listendurchlauf wird jedoch in dem Moment abgebrochen, an dem der Inhalt der gesuchten Elementes erreicht ist. Die Verknüpfungen finden dann so statt, dass das gesuchte Element als Nachfolgeelement des neuen fungiert. Ein Element wird durch die Methode delete(Object o) gelöscht. Hierzu werden die Verknüpfungen des Elementes mit dem Inhalt o gelöst und das Vorgänger- und Nachfolgerelement des zu löschenden neu miteinander verbunden. Hierbei muss darauf geachtet werden, dass das Nachfolgeelement des bisherigen Nachfolgeelementes nicht null ist. Ist dies der Fall, so handelt es sich um das letzte Element der Liste, das keinen Nachfolger besitzt.

public class DoppeltVerketteteListe {


    ListElement startElem = new ListElement("Kopf");
    ListElement tailElem = new ListElement("Schwanz");

    public DoppeltVerketteteListe() {
        startElem.setNextElem(tailElem);
        tailElem.setPrevElem(startElem);
    }

    public void addLast(Object o){
        ListElement newElem = new ListElement(o);
        ListElement lastElem = getLastElem();
        lastElem.setNextElem(newElem);
        newElem.setPrevElem(lastElem);
    }

    public void insertAfter(Object prevItem, Object newItem) {
        ListElement newElem, nextElem = null, pointerElem;
        pointerElem = startElem.getNextElem();
        while(pointerElem != null && !pointerElem.getObj().equals(prevItem)){
            pointerElem = pointerElem.getNextElem();
        }
        newElem = new ListElement(newItem);
        if(pointerElem != null){
            nextElem = pointerElem.getNextElem();
            pointerElem.setNextElem(newElem);
            newElem.setNextElem(nextElem);
            newElem.setPrevElem(pointerElem);
        }
        if(nextElem != null)
            nextElem.setPrevElem(newElem);
    }
    
    public void insertBefore(Object insertItem, Object newItem){
        ListElement newElem, pointerElem;
        newElem = new ListElement(newItem);
        pointerElem = startElem.getNextElem();
        while(pointerElem != null){
            if(pointerElem.getObj().equals(insertItem)){
                newElem.setPrevElem(pointerElem.getPrevElem());
                pointerElem.getPrevElem().setNextElem(newElem);
                pointerElem.setPrevElem(newElem);
                newElem.setNextElem(pointerElem);
                break;
            }
            pointerElem = pointerElem.getNextElem();
        }
    }

    public void delete(Object o){
        ListElement le = startElem;
        while (le.getNextElem() != null && !le.getObj().equals(o)){
            if(le.getNextElem().getObj().equals(o)){
                if(le.getNextElem().getNextElem()!=null){
                    le.setNextElem(le.getNextElem().getNextElem());
                    le.getNextElem().setPrevElem(le);
                }else{
                    le.setNextElem(null);
                    break;
                }
            }
            le = le.getNextElem();
        }
    }
    

    public boolean find(Object o){
        ListElement le = startElem;
        while (le != null){
            if(le.getObj().equals(o))
            return true;
            le = le.nextElem;
        }
        return false;
    }
    

    public ListElement getFirstElem() {
        return startElem;
    }

    public ListElement getLastElem() {
        ListElement le = startElem;
        while(le.getNextElem() != null){
            le = le.getNextElem();
        }
        return le;
    }

    public void writeList() {
        ListElement le = startElem;
        while(le != null){
            System.out.println(le.getObj());
            le = le.getNextElem();
        }
    }

    public static void main(String[] args) {
        DoppeltVerketteteListe list = new DoppeltVerketteteListe();
        list.addLast("1");
        list.addLast("2");
        list.addLast("3");
        list.addLast("4");
        list.addLast("5");
        list.insertAfter("2", "nach 2");
        list.delete("4");
        list.insertBefore("3", "vor 3");
        System.out.println("erstes Element: " + list.getFirstElem().getObj());
        System.out.println("ist '4' enthalten? " + list.find("4"));
        System.out.println("ist '5' enthalten? " + list.find("5"));
        System.out.println("letztes Element: " + list.getLastElem().getObj());
        System.out.println("vorletztes Element: " + list.getLastElem().getPrevElem().getObj());
        list.writeList();
    }
}

class ListElement {


    Object obj;

    ListElement nextElem, prevElem;

    public ListElement(Object obj) {
        this.obj = obj;
        nextElem = null;
    }

    public void setNextElem(ListElement nextElem) {
        this.nextElem = nextElem;
    }
    
    public void setPrevElem(ListElement prevElem) {
        this.prevElem = prevElem;
    }

    public ListElement getNextElem() {
        return nextElem;
    }
    
    public ListElement getPrevElem() {
        return this.prevElem;
    }

    public Object getObj() {
        return obj;
    }
}

1) Die Klasse LinkedList der Java-API stellt eine doppelt verkettete Liste bereit.