Home > Informatik > Stufe Q1 > Referenzen

15.5 Eine doppelt verkettete Liste

Allgemeines - dynamischer Stack - sortierte Liste - NRW-Liste - 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;
    }
Übung 15-4-1 (Vortrag)

Erläutern Sie den Fall 4 in einem kleinen Vortrag mit eigenen Zeichnungen (Kästchen-Schema).

Übung 14-4-2

Erstellen Sie eine doppelt verkette dynamische Liste, welche in der Lage ist, Strings in alphabetisch aufsteigender Reihenfolge zu speichern. Und zwar sollen die neuen Begriffe sofort an die richtige Position in die Liste eingefügt werden.

Statten Sie diese Wortliste außerdem mit weiteren nützlichen Funktionen aus, Sie können sich dabei ruhig an dem ADT List orientieren, können insgesamt aber einfacher vorgehen.

Übung 14-4-3 (Experten)

Erinnern Sie sich an die Vokabelliste aus der Folge 11? Erstellen Sie nun eine dynamische Liste von Deutsch/Englisch-Vokabeln, die folgendermaßen verkettet ist:

Doppelt verkettete Vokabelliste

Die Attribute firstG und firstE zeigen auf die erste deutsche bzw. englische Vokabel in den alphabetisch sortierten Listen. Entsprechen zeigen lastG und lastE auf die jeweils letzte Vokabel.

Die Liste von Knoten ist doppelt verkettet. Jede einzelne Vokabel zeigt einerseits auf die alphabetisch folgende deutsche Vokabel und mit dem zweiten Zeiger auf die alphabetisch folgende englische Vokabel. Die Vokabel "Hund/dog" hat als deutschen Nachfolger beispielsweise "Kaninchen/rabbit" und als englischen Nachfolger "Eule/owl".

Statten Sie die Klasse mit geeigneten Methoden zum Einfügen, Suchen und Löschen von Vokabeln aus.

Sie können auch gern an Ihrem Projekt aus der Folge 11 weiterarbeiten, vor allem dann, wenn Sie ein schönes Applet zum Eingeben und Anzeigen der Vokabeln erstellt haben.