15.5 Eine doppelt verkettete Liste

Der ADT List

In diesem Abschnitt soll der ADT List noch einmal implementiert werden, dieses Mal allerdings mit einer doppelt verketteten dynamischen Liste. Eine solche doppelt verkettete Liste unterscheidet sich von einer einfachen Liste (siehe Folge 15.3) dadurch, dass jeder Knoten nicht nur einen Zeiger auf den Nachfolger hat, sondern auch einen Zeiger auf den Vorgänger. Dadurch werden einige Operationen erleichtert, vor allem das Suchen nach dem Vorgänger des aktuellen Elements.

Die Klasse Knoten

    public class Knoten
    {
       Object wert;
       Knoten vorgaenger, nachfolger;
       
       public Knoten(Object w, Knoten v, Knoten n)
       {
          wert = w;
          vorgaenger = v;
          nachfolger = n;
       }
    }

So viel Arbeit war das doch gar nicht. Wir haben lediglich ein neues Attribut vorgaenger eingeführt und mussten dafür den Konstruktor um einen Parameter und eine Zuweisung ergänzen.

Die Methoden der Klasse List

Wir wollen jetzt mal überlegen, welche Methoden der Klasse List wir überhaupt ersetzen müssen.

Konstruktor

Den Konstruktor müssen wir nicht ändern, auch bei der doppelt verketteten Liste zeigt first auf das erste, last auf das letzte und act auf das aktuelle Element.

isEmpty() und hasAccess()

Auch diese beiden Methoden können bleiben, wie sie sind.

next(), toFirst(), toLast()

Diese Methoden müssen nicht geändert werden, sie haben bisher sehr schön mit dem Nachfolger-Zeiger funktioniert; der Vorgänger-Zeiger wird hierfür nicht benötigt.

previous()

Eine neue Methode, die zwar bei den Anforderungen für den ADT List nicht vorgesehen ist, die aber durchaus sinnvoll ist, wenn es jetzt auch für jeden Knoten einen Vorgänger gibt.

    /**
     * Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht
     * das erste Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste
     * vorhergehende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung
     * des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert
     * false.
     */
    public void next()
    {
       if ((!isEmpty()) && (hasAccess()) && (act != first))
          act = act.vorgaenger;
       else
          act = null;
    }    

setContent() und getContent()

Auch diese Methoden können unverändert bleiben.

append()

Hier müssen wir mal etwas mehr überlegen. Ein neuer Knoten soll an das Ende der Liste angefügt werden. Dazu muss der Nachfolger-Zeiger des bisherigen letzten Knoten auf den neuen Knoten gesetzt werden. Bisher reichte das völlig aus. Jetzt aber hat der neue Knoten ja auch einen Vorgänger-Zeiger, und dieser Vorgänger-Zeiger muss auf den bisherigen letzten Knoten gesetzt werden.

    public void append(Object x)
    {
       if (x != null)
       {
          Knoten neu = new Knoten(x,last,null);
          
          if (isEmpty())
          {
             first = last = neu;
          }
          else
          {
             last.nachfolger = neu;
             last = neu;
          }
       }
    }

Das Einzige, was im Quelltext geändert werden muss, ist die Übergabe des last-Zeigers an den Konstruktor des neuen Knotens.

insert()

Hier würden wir jetzt ja eine Vereinfachung erwarten, da das lästige Suchen nach dem Vorgänger-Knoten von act entfällt.

    public void insert(Object x)
    {
        if (isEmpty())
        {
           first = new Knoten(x,null,null);
           last = first;
           act = null;
        }
        
        else if (hasAccess()) 
        {
           if (act == first)
           {
              Knoten neu = new Knoten(x,null,first);
              first.vorgaenger = neu;
              first = neu;
           }
           else
           {
              Knoten help = act.vorgaenger;
              help.nachfolger = new Knoten(x,help,act);
              act.vorgaenger = help.nachfolger;
           }
        }
    }

So stark wie erwartet ist diese Vereinfachung aber eigentlich nicht. Die while-Schleife zum Suchen des Vorgängers entfällt, statt dessen kann man den Hilfszeiger help direkt auf den Vorgänger des aktuellen Knoten setzen, das ist schon eine Vereinfachung. Andererseits muss man jetzt den Vorgänger-Zeiger des aktuellen Knoten auf help.nachfolger setzen, das ist wieder ein zusätzlicher Befehl.

remove()

Hier sollte man ähnliche Überlegungen anstellen: Die while-Schleife zum Suchen entfällt, dafür muss man sich aber um die Vorgänger-Knoten kümmern:

    public void remove()
    {
    // Fall 0: Liste ist leer oder es gibt kein aktuelles Element
       if ( (isEmpty()) || (!hasAccess())) return;
       
    // Fall 2: Liste besteht aus nur einem Element
       if (first == last)
       {
          first = last = act = null; 
          return;
       }
       
    // Fall 3a: es soll vorne gelöscht werden
       if (act == first)
       {
          act = act.nachfolger;
          first = act;
          first.vorgaenger = null;
          return;
       }
       
    // Fall 3b: es soll hinten gelöscht werden
       if (act == last)
       {
           act = act.vorgaenger;
           last = act;
           last.nachfolger = null;
           act = null;
           return;
       }
       
    // Fall 4: es soll in der Mitte gelöscht werden
       act.vorgaenger.nachfolger = act.nachfolger;
       act.nachfolger.vorgaenger = act.vorgaenger;
       act = act.nachfolger;
    }