Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Verkettete Listen

Die zweite zu behandelnde elementare Datenstruktur ist die verkettete Liste, welche in einigen Programmiersprachen (insbesondere in Lisp) als ein Grundelement definiert ist, nicht jedoch in Pascal. Pascal stellt aber einige elementare Grundoperationen bereit, die die Verwendung verketteter Listen vereinfachen.

Der entscheidende Vorteil verketteter Listen gegenüber Feldern besteht darin, daß ihre Größe zu- und abnehmen kann, solange sie existieren; insbesondere muß ihre maximale Größe nicht im voraus bekannt sein. In praktischen Anwendungen wird es dadurch oft möglich, daß sich verschiedene Datenstrukturen den gleichen Speicherbereich teilen, ohne daß man zu irgendeinem Zeitpunkt speziell auf ihre jeweiligen Größen achten muß.

Ein zweiter Vorteil verketteter Listen ist, daß sie eine höhere Flexibilität ermöglichen, indem sie es gestatten, die Elemente in effizienter Weise umzuordnen. Diese Flexibilität wird auf Kosten eines schnellen Zugriffs auf ein beliebiges Element in der Liste erreicht. Das wird später noch klarer werden, nachdem wir einige der Haupteigenschaften verketteter Listen und einige der grundlegenden Operationen, die wir mit ihnen ausführen können, betrachtet haben.

Eine verkettete Liste ist eine Menge von Elementen, die - wie in einem Feld - sequentiell organisiert sind. In einem Feld wird die sequentielle Anordnung implizit bewirkt (durch die Position im Feld); in einer verketteten Liste verwenden wir eine explizite Anordnung, in welcher jedes Element Teil eines »Knotens« ist, der auch eine »Verkettung« zum nächsten Knoten enthält. Abbildung 3.1 zeigt eine verkettete Liste, bei der die Elemente durch Buchstaben dargestellt sind, die Knoten durch Kreise und die Verkettungen durch Linien, die die Knoten verbinden. Wir werden uns später im einzelnen ansehen, wie Listen im Computer dargestellt werden; einstweilen werden wir einfach die Begriffe »Knoten« und »Verkettungen« verwenden.

Schon die einfache Darstellung in Abbildung 3.1 macht zwei Details sichtbar, die wir beachten müssen. Erstens besitzt jeder Knoten eine Verkettung, so daß die Verkettung im letzten Knoten der Liste einen gewissen »nächsten« Knoten deklarieren muß. Wir vereinbaren, daß wir für diesen Zweck einen »Pseudoknoten« einführen, den wir z nennen wollen; der letzte Knoten der Liste zeigt auf z, und z zeigt auf sich selbst. Außerdem wollen wir vereinbaren, daß wir normalerweise auch am anderen Ende der Liste einen Pseudoknoten haben. Dieser Knoten, den wir Kopf (head) nennen, zeigt auf den ersten Knoten der Liste. Der Hauptzweck der Pseudoknoten besteht darin, bestimmte Operationen mit den Verkettungen, insbesondere mit denen, die mit dem ersten und dem letzten Knoten der Liste zusammenhängen, zu vereinfachen. Andere Vereinbarungen werden später erörtert. Abbildung 3.2 zeigt die Struktur einer Liste einschließlich dieser Pseudoknoten.

Abbildung 3.1
Abbildung 3.1 Eine verkettete Liste.

Abbildung 3.2
Abbildung 3.2 Eine verkettete Liste mit ihren Pseudoknoten.

Diese explizite Darstellung der Anordnung macht es nun möglich, bestimmte Operationen wesentlich effizienter auszuführen, als dies für Felder möglich wäre. Nehmen wir zum Beispiel an, daß wir das T vom Ende der Liste an den Anfang setzen wollen. In einem Feld müßten wir jedes Element verschieben, um Platz für das neue Element am Anfang zu schaffen; in einer verketteten Liste verändern wir nur drei Verkettungen, wie Abbildung 3.3 zeigt. Die beiden in Abbildung 3.3 dargestellten Varianten sind äquivalent; sie sind lediglich auf unterschiedliche Weise gezeichnet. Wir lassen den T enthaltenden Knoten auf A, den S enthaltenden Knoten auf z, und Kopf auf T zeigen. Auch wenn die Liste sehr lang wäre, könnten wir diese Strukturänderung vornehmen, indem wir nur drei Verkettungen verändern.

Was noch wichtiger ist, wir können vom »Einfügen« eines Elements in eine verkettete Liste (deren Länge dadurch um 1 wächst) sprechen, einer Operation, die in einem Feld unnatürlich und schwierig ist. Abbildung 3.4 zeigt, wie X in unser Beispiel einer Liste eingefügt werden kann. Dazu fügen wir es in einen Knoten ein, der auf S zeigt, und lassen dann den I enthaltenden Knoten auf diesen neuen Knoten zeigen. Nur zwei Verkettungen müssen für diese Operation verändert werden, gleich, wie lang die Liste ist.

In analoger Weise können wir vom »Entfernen« eines Elements aus einer verketteten Liste sprechen (wodurch sich deren Länge um 1 verringert). Beispielsweise zeigt die dritte Liste in Abbildung 3.4, wie man X aus der zweiten Liste entfernen kann, indem man den Knoten, der I enthält, einfach auf S zeigen läßt, und X ausläßt. Nun existiert zwar der X enthaltende Knoten noch (tatsächlich zeigt er sogar immer noch auf S), und vielleicht sollte er auf irgendeine Weise beseitigt werden; entscheidend ist jedoch, daß er kein Bestandteil dieser Liste mehr ist und nicht erreicht werden kann, indem man vom Kopf aus den Verkettungen folgt. Wir werden später noch darauf zurückkommen.

Abbildung 3.3
Abbildung 3.3 Änderung der Reihenfolge in einer verketteten Liste.

Abbildung 3.4
Abbildung 3.4 Einfügen in eine verkettete Liste und Entfernen aus einer verketteten Liste.

Andererseits gibt es Operationen, für welche verkettete Listen nicht gut geeignet sind. Am offensichtlichsten ist das beim »Finden des k-ten Elements« (Auffinden eines Elements, wenn sein Index gegeben ist): In einem Feld wird dies einfach durch den Zugriff a t[k] realisiert, in einer Liste müssen wir dagegen k Verkettungen durchlaufen.

Eine weitere Operation, die für verkettete Listen unnatürlich ist, ist das »Finden des Elements vor einem gegebenen Element«. Wenn wir lediglich die Verkettung zu T in unserer Beispielliste haben, so besteht der einzige Weg zum Auffinden der Verkettung zu S darin, beim Kopf zu beginnen und die Liste durchzugehen, um den auf T zeigenden Knoten zu finden. Tatsache ist, daß diese Operation erforderlich ist, wenn wir in der Lage sein möchten, einen gegebenen Knoten aus einer verketteten Liste zu entfernen: Wie sollten wir sonst den Knoten finden, dessen Verkettung geändert werden muß? In vielen Anwendungen können wir dieses Problem umgehen, indem wir die grundlegende Operation des Entfernens in das »Entfernen des nächsten Knotens« umändern. Ein analoges Problem für das Einfügen kann vermieden werden, indem die grundlegende Operation des Einfügens als »Einfügen eines gegebenen Elements nach einem gegebenen Knoten in der Liste« formuliert wird.

Pascal stellt elementare Operationen bereit, die es gestatten, verkettete Listen direkt zu implementieren. Der folgende Ausschnitt eines Programms ist ein Beispiel einer Implementation der elementaren Funktionen, die wir in diesem Zusammenhang erörtert haben.

  
    type link ^node;
         node = record key: integer; next: link end;
    var head,z,t: link;
    procedure listinitialize;
      begin
      new(head); new(z);
      head^.next:=z; z^.next:=z
      end;
    procedure deletenext(t: link);
      begin 
      t^.next:=t^.next^.next;
    end;  
    procedure insertafter(v: integer; t: link);
      var x: link;
      begin 
      new(x); 
      x^.key:=v; x^.next:=t^.next;
      t^.next:=x
      end;  

Das genaue Format der Listen wird in der type-Spezifikation beschrieben: Die Listen setzen sich aus Knoten (nodes) zusammen, wobei jeder Knoten eine ganze Zahl und eine Verkettung (link) zum nächsten Knoten der Liste enthält. Der Schlüssel (key) ist hier nur der Einfachheit halber eine ganze Zahl; er könnte beliebig komplex sein. Die Verkettung ist der Schlüssel zur Liste. Die Variable head ist eine Verkettung zum ersten Knoten einer Liste; wir können die anderen Knoten der Reihe nach betrachten, indem wir den Verkettungen folgen, bis wir z erreichen, wobei die Verkettung, die auf den Pseudoknoten zeigt, das Ende der Liste darstellt. Die Syntax von Pascal für aufeinanderfolgende Verkettungen ist der »Pfeil nach oben«: Um uns auf den Knoten zu beziehen, auf den eine Verkettung verweist, schreiben wir die Bezeichnung dieser Verkettung, gefolgt von diesem Symbol. Zum Beispiel bezieht sich head^.next^.key auf das erste Element in einer Liste, head^.next^.next^.key auf das zweite Element.

Die type-Spezifikation beschreibt lediglich das Format der Knoten; Knoten können nur erzeugt werden, indem die Standardprozedur new aufgerufen wird. Zum Beispiel erzeugt der Aufruf new(head) einen neuen Knoten, und legt in head einen Zeiger auf diesen ab. Der Zweck dieser Verfahrensweise besteht darin, den Programmierer von der Aufgabe der Speicherzuordnung für die Knoten zu entlasten, wenn sich die Liste verlängert. (Wir gehen auf diesen Mechanismus später noch genauer ein.) Es gibt eine entsprechende Standardprozedur dispose für das Entfernen, welche durch die aufrufende Routine benutzt werden kann. Andererseits kann der Knoten aber auch einer Liste hinzugefügt werden, obwohl er aus einer anderen Liste entfernt wurde.

Dem Leser wird empfohlen, diese Implementationen in Pascal mit den oben gegebenen Erläuterungen zu vergleichen. Insbesondere ist es in diesem Stadium lehrreich, sich zu überlegen, wozu die Pseudoknoten von Nutzen sind. Erstens würde die Prozedur insert einen speziellen Test für das Einfügen am Anfang der Liste erfordern, wenn man head auf den Beginn der Liste zeigen läßt, anstatt einen Knoten head einzuführen. Zweitens schützt die Vereinbarung für z die Prozedur delete (zum Beispiel) vor einem Aufruf zum Entfernen eines Elements aus einer leeren Liste.

Eine weitere gebräuchliche Vereinbarung für das Beenden einer Liste besteht darin, daß man den letzten Knoten auf den ersten zeigen läßt und dafür zumindest auf einen der Pseudoknoten head oder z verzichtet. Dies wird zyklische Liste genannt: Sie gibt einem Programm die Möglichkeit, die Liste immer wieder zu durchlaufen, solange noch etwas in ihr enthalten ist. Die Verwendung eines Pseudoknotens ist manchmal zweckmäßig, um den Anfang (und das Ende) der Liste zu markieren und die Behandlung des Falls einer leeren Liste zu erleichtern.

Es ist möglich, die Operation »Auffinden des Elements vor einem gegebenen Element« durch die Verwendung einer doppelt verketteten Liste zu unterstützen, in welcher wir für jeden Knoten zwei Verkettungen festlegen: Eine zum vorhergehenden Element und eine zum nachfolgenden. Der Preis für die Bereitstellung dieser zusätzlichen Möglichkeit ist die Verdopplung der Anzahl der Operationen mit den Verkettungen für jede Grundoperation. Dieses Verfahren wird daher normalerweise nur dann angewandt wird, wenn es speziell benötigt wird. Wie oben erwähnt kann jedoch in dem Fall, wo ein Knoten entfernt werden soll und nur eine Verkettung zu ihm zur Verfügung steht (er kann auch Bestandteil einer anderen Datenstruktur sein), doppeltes Verbinden benötigt werden.

In späteren Kapiteln werden wir viele Anwendungsbeispiele für diese und andere elementare Operationen mit verketteten Listen finden. Da die Operationen nur wenige Anweisungen erfordern, arbeiten wir normalerweise direkt mit den Listen, anstatt die obengenannten exakten Prozeduren zu benutzen. Als Beispiel betrachten wir nun ein Programm zur Lösung des sogenannten »Problem des Josephus«, das von der Art des Siebs des Eratosthenes ist.

Für das Problem des Josephus stellen wir uns vor, daß N Personen beschlossen haben, einen Massenselbstmord zu begehen, indem sie sich in einem Kreis aufstellen und jedesmal die M-te Person im Kreis töten, wobei sich immer wieder die Reihen schließen, wenn eine Person aus dem Kreis ausscheidet. Das Problem besteht darin zu ermitteln, welche Person als letzte sterben wird (obwohl vielleicht diese Person am Ende ihre Meinung ändern könnte!), oder allgemeiner, die Reihenfolge zu bestimmen, in der die Personen sterben müssen. Falls zum Beispiel N = 9 und M = 5 ist, werden die Personen in der Reihenfolge 5 1 7 4 3 6 9 2 8 getötet. Das nachfolgende Programm liest N und M ein und gibt diese Reihenfolge aus:

    program josephus(input,output);
    type link ^node;
         node = record key: integer; next: link end;
    var i,N,M: integer; 
        t,x: link;
    begin
    read(N,M);
    new(t); t^.key:=1; x:=t;
    for i:=2 to N do
      begin new(t^.next); t:=t^.next; t^.key:=i end;
    t^.next:=x;
    while t<>t^.next do
      begin
      for i:=1 to M-1 do t:=t^.next;
      write(t^.next^.key);
      x:=t^.next;
      t^.next:=t^.next^.next;
      dispose(x);
      end;
    writeln(t^.key);
    end.

Das Programm verwendet eine zyklische Liste, um die Folge der Hinrichtungen direkt zu simulieren. Zunächst wird die Liste mit Schlüsseln von 1 bis N aufgebaut: Die Variable x bezeichnet den Anfang der Liste, während diese aufgebaut wird, und danach wird der Zeiger im letzten Knoten in der Liste auf x gerichtet. Anschließend realisiert das Programm das Durchlaufen der Liste, wobei es M - 1 Elemente abzählt und das nächstfolgende entfernt, so lange, bis nur ein Element übrigbleibt (welches dann auf sich selbst zeigt). Man beachte den Aufruf von dispose für das Entfernen, welches einer Hinrichtung entspricht; dispose ist das Gegenstück zu new, wie oben erwähnt wurde.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]