Damit die Zugriffsoperationen effizient (mit konstantem Aufwand) realisiert werden können, sollte es möglich sein, von beiden Enden her in die darunterliegende Datenstruktur hineinzulaufen, und dies gelingt am besten über eine doppelt verkettete Liste, in der jeder Knoten je einen Verweis auf den Nachfolger und den Vorgänger trägt.
Analog zu früher können wir jetzt definieren:
TYPE liste = POINTER TO Knoten;
TYPE Knoten = RECORD wert: atom;
vor, nach: liste;
END;
Diese Datenstruktur ist auch für sich gesehen interessant,
weil Einfügen und Löschen jetzt auch im Inneren
einer Liste einfach möglich ist.
Wenn wir die beiden Verkettungen einzeln für sich betrachten,
so erhalten wir jeweils wieder eine verkettete Liste,
und wir können jeweils noch vorgeben,
ob dies eine gestreckte Liste oder eine
Ringliste sein soll.
Als Beispiel geben wir eine Operation für das Entfernen eines Knotens aus einer doppelt verketteten Ringliste an:
PROCEDURE entferne(VAR y: atom; VAR p: liste);
VAR n, v: liste;
BEGIN y := p^.wert; v := p^.vor; n := p^.nach;
v^.nach := n; n^.vor := v;
DISPOSE(p);
END entferne;
Der Anwender muß darauf achten, daß er noch einen weiteren
Zeiger in die Liste behält, sonst wird sie unzugänglich!
Einfügen vor oder hinter einem gegebenen Element geht ganz
analog, und ebenso einfach.
Wir haben hier zwei Hilfszeiger v und n eingeführt, um das Programm übersichtlich zu halten. Statt der zweiten Zeile im Prozedurrumpf hätten wir auch schreiben können:
Dann brauchen wir die Hilfszeiger nicht, und die Routine wird schneller, aber weniger leicht zu lesen. Ein wirklich guter, moderner Compiler macht die Verbesserung automatisch. (Sie kann erheblich sein; auf einem TR4-Prozessor aus den 60-er Jahren braucht das Entfernen nur 6 Maschinenbefehle!)p^.vor^.nach := p^.nach; p^.nach^.vor := p^.vor;
Natürlich ist für die neu gewonnene Flexibilität ein Preis zu zahlen, gemäß der Regel, die gelegentlich TAANSTAAFL-Law genannt wird:
There Ain't Absolutely No Such Thing As A Free LunchHier ist der notwendige Zusatzaufwand der Platz, den der zweite Verweis in jedem Knoten belegt.
Die Struktur der doppelt verketteten Liste enthält erhebliche Redundanz (im Grunde überflüssige Information): für jedes über einen Zeiger p zugängliche Element einer doppelt verketteten Liste muß gelten
Diese Redundanz läßt sich ausnutzen: ist etwa in einer doppelt verketteten Ringliste ein einziger Zeiger zerstört (aber nur so weit, daß ein Zugriff über ihn nicht auf einen Laufzeitfehler führt!), so kann dieser Fehler nicht nur erkannt , sondern sogar korrigiert werden. Allerdings bleibt dann noch die womöglich schwierige Aufgabe, herauszufinden, wie es zu dem Fehler überhaupt kommen konnte!p^.vor^.nach = p und p^.nach^.vor = p
Wir haben in einem größeren Implementierungsprojekt
Anfangs der 70-er Jahre die doppelt verketteten Listen als Grundlage
für alle anderen vorkommenden Listenstrukturen verwendet
(damals waren Kenntnisse über Datenstrukturen noch nicht in dem
Maße Allgemeingut, wie sie es heute sind oder zumindest sein sollten),
und das hat uns öfters geholfen,
Fehler beim Zugriff durch mehrere parallel ablaufende Prozesse
auf gemeinsame Datenstrukturen zu finden.
Wie solche parallelen Zugriffe korrekt zu synchronisieren sind,
haben wir dadurch besser verstanden.