Video 8-7: Doppelt verkettete Liste

0:03 Im letzten mal Abschnitt hatten wir uns einfach verkettete Listen angeschaut und insbesondere festgestellt, die haben eine Eigenheit, die ein bisschen unintuitiv ist. Wenn ich so eine Position in der Liste haben möchte, um einzufügen oder zu löschen, dann muss die Position auf den Vorgänger des Elements zeigen, auf dem ich eigentlich arbeite. Das funktioniert zwar, ist aber so ein bisschen unintuitiv und äh was ich auch nicht machen kann in der Liste, ist irgendwie rückwärts laufen. Also, wenn ich ähm iterieren muss in beide Richtungen, dann kann ich das mit der einfach verketten Liste erstmal vergessen.

0:41 Eine einfache Variante, die das besser unterstützt, ist die doppelte Verkettung. Da habe ich mehr Speicherplatz für äh für diese Pointer ähm aufgewendet, verschwendet, wenn man wenn man es böse ausdrückt. Aber dafür wird das ähm Leben in der Datenstruktur deutlich einfacher. Also jedes Element, jeder Knoten ist jetzt ein ein Trippel, wenn Sie so wollen, aus einem Element und einem Next und Previous Zeiger im Code. Also ganz ehrlich wie vorher, wir haben eine doppelt verkettete Liste, die immer auch immer noch aus List Node Objekten besteht. Da das aber eine innere Klasse ist, kann die den gleichen Namen haben. Die hat den Namespace von der umgebenden Klasse und die hat eben jetzt neben dem Objektzeiger, neben dem Element selbst zwei Zeiger auf andere Knoten.

1:33 Auch hier ähm kann man natürlich jetzt so die Liste aufbauen und die Frage ist, was mache ich am Ende? Da gibt's verschiedene Optionen. Ähm, eine bequeme hier, die tatsächlich diverse Randfälle vermeidet, ist ein künstliches Header Dummy Objekt wieder einzuführen, das also kein echtes Element speichert. Hier die A1 bis AN sind nicht das in dem Element gespeichert. Was aber ähm immer vorhanden ist, auch wenn die Liste leer ist und was die Liste schließt zu einem Kreis. Äh das das bedeutet einfach, dass beim Durciterieren man immer einen bekannten Endwert hat, dass man äh nie Nullpointer hat, mit denen man sich rumärgern muss. Ähm ist ist die Konvention, die ich am am bequemsten finde. Also initialisieren, indem wir ein Header Element anlegen für eine leere Liste und das ähm auf sich selbst zeigen lassen in beiden in beiden Richtungen. Und sie können sich vorstellen, wie das dann mit Einfügung funktioniert. Da wir das einmal in viel Detail gesehen haben, hier vielleicht etwas verkürzt.

2:40 Äh, wir verwenden wieder ähm dieses äh Listne Objekt selbst als Position, die wir dann akzeptieren in Operationen. Das heißt, wir haben diese äh Operationen, die auf den Positionen selbst arbeiten. Da ist Next jetzt äh ganz einfach wie bisher. Und wir haben jetzt aber auch diese Operation Previous, die wir eigentlich in der einfach verketteten Liste gar nicht sinnvoll unterstützen konnten. Da musste man dann vom Anfang der Liste durchlaufen. Äh war nur langsam zu unterstützen. Ähm Zugriff auf die Elemente ist wie gehabt. Ähm am interessantesten ist vielleicht noch das Einfügen. Da habe ich also eine verkettete Liste und mein aktuelles Element P, das ist mein meine Position, die ist jetzt wirklich das Element ums das um das es uns geht. Und äh im allgemeinen hat diese Liste irgendwelche Vorgänger und Nachfolger. Und an der Stelle sehen Sie, warum das eine bequeme Konvention ist, denn selbst wenn die Liste leer ist, gibt es diese Vorgänger Nachfolger, die sind vielleicht auch wieder dieses Header Element, aber ich habe nie mit Nullpintern zu tun.

3:58 Also hier ist unsere verkettete Liste. Jetzt würden wir gerne neues Element einfügen. Die Konvention ist bei so einer Position, dass wir das direkt davor einfügen. Das passt dann so so wie wir Start und äh Ende definiert haben. Wenn ich so ein neues Element einfügen möchte, dann lege ich einen neuen Knoten an mit diesem Wert X. Das passiert hier. Und dann setze ich von meinem bisherigen Knoten Ma der Reihenfolge im Code nach. Sorry. Erst aktualisieren wir den neuen Knoten. Das previous erbt er von unserem Eintrag hier. Next zeigt auf den Knoten P selber, also auf den Knoten hier. Jetzt sehen Sie schon, das ist konzeptionell aus der Sicht von X zwischen diesen beiden Elementen, aber natürlich sind die Zeiger dahin noch nicht umgebogen. Note previous, next, das ist dieser Pointer, den biegen wir jetzt um auf das neue Objekt. Das heißt, wir verlaufen von hier nach hier, dann nach hier und dann nach hier. Jetzt würden wir gerne noch hier den Preous Zeiger umbiegen, also den hier, dass der wiederum auch auf das oben zeigt. Krieg ich das noch irgendwie hin, ohne zu überkreuzen?

5:31 Sie sehen schon, das ähm sieht dann im Bild chaotisch aus. Da hätte ich jetzt gerne noch die Möglichkeit, das rumzuschieben und die Pfeile folgen. Äh könnten wir natürlich wieder tun in dem Python Tutor Tool.

5:43 Ähm, jetzt kriege ich ohne Tastatur das Ding hier nicht versteckt. Also, hier ist der Code für die doppelt verkältete Liste und ich versuche mal das hier so zu umgehen, wenn wir ein paar Elemente bauen, das initialisieren, ähm schenke ich uns mal.

6:07 Also, wir sind jetzt an der Stelle, wir haben eine leere Liste, die besteht nur aus diesem einen Headerobjekt, das auf sich selbst wieder zurückzeigt. Ich mache mal wieder hier diese gebogenen Linien. Weiß nicht, ob die besser sind, aber zumindest kann man sie etwas leichter auseinander halten. Ist mein Eindruck. Ähm, jetzt würden wir ein Element einfügen. Das ist der degenerierte Fall, wenn sowohl Vorgänger als Nachfolger auch das Element selbst Header sind. Aber witzigerweise funktioniert der gleiche Code dafür ohne Änderung.

6:44 Ich lege mein neues Objekt an und schreibe da diesen neuen Wert X rein. Soweit so einfach. Und jetzt muss ich die Pointer umbiegen. Also so wie es hier steht, gleicher Code wie auf der Folie. Und wenn ich damit fertig bin, dann sieht das eben so aus. An der Stelle ähm sind beide Pointer jetzt jeweils parallel und zeigen auf das gleiche Element. Und ich habe jetzt so einen winzigen Kreis mit zwei Elementen bisher gebaut.

7:11 Äh, wenn ich noch eine Einfügung dazu packe, also noch ein neues Objekt da unten mit dem Wert 2. Jetzt sind wir an der Stelle, wo wir die Pointer umbiegen.

7:22 Also, das wird eingefügt an dem am Ende der Liste nach der 1. Das ist die Konvention. Das heißt, ich würde von ein den Next Zeiger hierhin biegen wollen und den Preis Zeiger von hier zurück. Von zwei den Next Zeiger auf Head und von Head zurück hierher.

7:43 Und das ist das, was hier dann passiert. Das heißt, jetzt haben wir so einen kleinen Kreis aus drei Elementen gebaut. Okay, man sieht es mit dem Point dann tatsächlich nicht so richtig toll, aber wenn Sie einzelnen Zeigern folgen, dann äh passt es. Komm, mach mal den Fokus hierauf. Mag nicht. Ja, okay. Ähm, wenn Sie wenn Sie das den Code selbst nicht selbsterklärend finden, spielen Sie noch mal alleine damit ein bisschen rum. ähm ist wahrscheinlich immer noch besser als von Hand diese Bildchen so zu malen, wo das dynamisch die Knoten hin und her bewegen nicht so gut funktioniert.

8:22 Was hier zu beobachten ist, ähm abgesehen davon, dass es vielleicht verwirrend ist, weil wir so viele äh Linien in dem Bild haben, ist das Update selbst total einfach. Ich habe genau die Position, wo ich einfügen möchte und dadurch kenne ich meinen Nachfolger und Vorgänger in beide Richtungen und kann das neue Element einfach da reinplatzieren, indem ich diese Zuweisung an die Pointer mache. Äh löschen ist übrigens noch einfacher, denn da würde ich jetzt einfach ein Element, was vorher in dieser Liste mit eingebaut war, okay, das kann ja niemand sehen. Ähm, da würde ich dann einfach hier das überspringen mit so einem langen vorwärts und einem langen Rückwärtszeiger und das Element löschen und schon ist es aus der Liste entfernt. Also konzeptionell sind die doppeltverketteten Listen einfacher, aber sie brauchen deutlich mehr Speicherplatz.

9:24 ein paar Nitpicks, was die Bedeutung angeht. Einfügen vor so einer Position Pedeutet, dass diese Position selbst sich nicht ändert. Das heißt, in meinem Beispiel hier ist dieses P immer noch das Element hier, vor dem es jetzt ein neues Element X gibt. Das ist anders als die Konvention für die einfach verketteten Listen. Also nicht mal untereinander sind diese verketteten Listen direkt austauschbar, ohne dass die Pointer ihre Bedeutung ändern. Und das ist einfach, man könnte das versuchen künstlich umzubiegen. Dann müsste ich aber dazu lassen, dass mein mein Positionsobjekt hier sich verändern darf wie ein Insert, denn ähm ich kann hier an das P selbst eigentlich nicht gut Zuweisung machen oder möchte man aus anderen Gründen eigentlich nicht machen. Dementsprechend kann ich zwar Pointer umbiegen, aber mein P bleibt bloß ist. In der einfach verketteten Liste war der Zeiger auf den Vorgänger. Das heißt, die semantische Bedeutung damals war, ich meine eigentlich das Element nach dem auf das ich zeige und das hat sich verändert, wenn ich einfüge. Hier ist es nicht der Fall.

10:27 Ähnliches gilt beim Löschen. Ähm löschen von einer Position bedeutet, dass die Position selbst jetzt auf einen verweisten Knoten zeigt, der gar nicht mehr Teil der Liste ist. Das heißt, die Position wird dadurch ungültig. Damit werde ich wahrscheinlich leben müssen, weil ähm ich ja jetzt diese Position entfernt habe. Wenn ich aber von der Position aus weiter iterieren möchte, dann muss ich das vor der Löschung tun.

10:53 Anders als bei der Einfachverkettenliste ist aber wenigstens eine andere eine andere Position von meiner Löschung nicht beeinträchtigt. Also sind so Randfälle äh die man einfach ein bisschen ähm sich bewusst machen muss, wenn man mit den Dingern auf Ultra Ebene arbeitet. Ähm, das ist auch alles, was ich Ihnen zu den verketteten Listen sagen möchte. Ich denke, die die Datenstruktur ist ansonsten nicht besonders kompliziert von diesen buddeligen Details abgesehen.

11:22 Äh eine Anwendung möchte ich ihn noch präsentieren, die streng genommen ähm für beide für beide Kapitel gilt. Ein Klassiker in numerischen Algorithmen ist mit Matrizenrechnen. Äh heutzutage noch viel mehr als eh schon immer. Und die klassische Variante, zumindest in vielen numerischen Simulationen, ich bin versucht zu sagen, war, dass die meisten Einträge in solchen Matrizen null sind. Ähm auf GPUs und so weiter ist es ein bisschen ein anderer Tradeoff. Da ähm hat man oft mehr davon, reguläre Daten zu nehmen und ähm damit zu leben, dass vielleicht viele Nullleinträge dabei sind. äh klassische in in der CPU optimierte Verfahren ähm können davon profitieren, dass wir diese ganzen Nullleinträge nicht mitschleppen. Also alle Matrixoperationen, ich will jetzt kein Ausfügen linear Algebra machen, aber diese ganzen Matrizen Addition, Multiplikation, Matrixvektorprodukte, all diese Dinge sind im Wesentlichen so, dass wenn es da viele Einträge gibt, das Ergebnis eigentlich auch viele Nullen haben kann oder zumindest viele der Operationen zwischendrin weglassen weggelassen werden könnten, weil ich irgendwo mit 0 null multipliziere.

12:38 Wenn ich dann meine Matrix als zweidimensionales Array darstelle, das die natürlichste Art ist zu tun, dann verschwende ich damit einerseits Platz, weil die Nullen ich mir vielleicht irgendwie kompakter hätte merken können und aber die Operationen insbesondere verschwenden auch Zeit, weil sie viel mit null multiplizieren, äh was wir uns hätten sparen können. Das kann man umgehen, indem man Matrizen oder Vektoren nicht als als Array speichert, indem ich für jeden Eintrag in der Matrix eine Position habe oder einen ein eine Zahl speichere, sondern ich speicher explizit nur eine Liste der nicht null Einträge. Äh hier ist ein Beispiel, indem ich aber dann mir merken muss, welche Position in der Matrix hat dieser Eintrag? Also beispielsweise hier äh wir können uns dann noch drüber unterhalten, in welcher Reihenfolge wir durch die Matrix gehen. Hier ist es so zeilenweise. Der eigentliche Eintrag steht an letzter Stelle und davor das sind eben Zeile und Spalte. Row und Colum Zeile und Spalte.

13:43 Also Zeile 1, Spalte 2 ist die 9. Dann ist es die nächste nicht 0, ist die 7 in Zeile 2, Spalte 1 und so weiter. Das ist genau dann kompakter, wenn ich dadurch, dass jetzt diese Indizes speichern muss, nicht noch mehr äh Daten habe, als ich einspare. Also ich muss mindestens irgendwie zwei Drittel Nullen haben um und bei, ne? Wenn das alles gleich große Zahlen sind. Ähm, das ist aber durchaus üblich in vielen Simulationen, dass man sehr viele Nullen hat, wenn die Matrix ursprünglich aus einer bestimmten Anwendung kommt. Und wenn ich danach Operationen auf dieser Matrix mache, dann lohnt sich das erst recht. Z.B. könnte ich zwei Matrizen addieren, wenn sich wenn sie in dieser Darstellung gegeben sind, indem ich parallel durch diese Listen laufe und das Ergebnis hat eben einen Eintrag, wann immer ich einen Eintrag in einer der beiden Eingabematrizen habe. Addition von Matriz ist einfach Elementweise. Äh und wenn ich aber für beide einen Eintrag habe, dann addiere ich die Einträge.

14:45 Das heißt, das Ergebnis hat dann so viele Nullen wie die Eingabe zusammen im schlimmsten Fall aufadiert. Das kann sich immer noch lohnen. Aber Matrixaddition ist irgendwie so ein bisschen langweilig. Die spannenden Sachen passieren bei Matrix Multiplikation und das ist mit dieser Darstellung nicht so ohne weiteres zu machen. Wenn ich zwei Matrizen multiplizieren möchte, dann muss ich eine der Matrizen in Zeilenorientierung durchlaufen können und die andere in Spaltenorientierung, weil ich mir diese äh Vektorprodukte für jeden Eintrag berechnen muss.

15:23 Dafür könnte man versuchen, die Darstellung irgendwie für beides einfach zu duplizieren. Ich mache eine Kopie in Zeilenordnung, eine in Spaltenordnung, aber wir sind ja losgelaufen damit, dass wir keinen Platz verschwenden wollen. Es gibt eine eine cleverere Organisation, die einfach diese Zweidimensionalität von der Matrix nachbildet und ähm für jeden Eintrag also eine Verkettung in der Zeile und eine Verkettung in der Spalte vorhält. Dann kann ich ohne die Daten doppelt zu speichern die Iteration in beiden Richtungen äh durchführen und kann also mit der einen Darstellung Matri Matrix Multiplikation an beliebiger Stelle im Produkt durchführen, egal ob ich der linke oder der rechte äh Faktor bin.

16:12 Also auch hier ähm schauen sich das Beispiel an. Äh, das ist rein optisch. Ja, sehen Sie, ist überall, wo hier nicht Null Eintrag ist, ist hier so ein so eine Box und die sind eben verpointet in sowohl Zeile als auch äh sowohl Zeile als auch Spaltenordnung. Ähm, detaillierter Coach erspare ich uns allen hier erstmal. Äh, das ist aber etwas, was in äh klassischen linearen Algebra System eingebaut ist. Da haben Sie in aller Regel auch, wenn sie das verwenden, die Wahl zwischen einer dichten Darstellung äh Dance Matrix oder einer Sparce Matrix und intern ist das diese beiden Datenstrukturen. Entweder ist es ein 2D Array oder es ist eine eine verkettete Darstellung in etwa in dieser Form.

17:06 Also das alles können diese verkehrten Listen für uns tun. Ähm Zusammenfassung von diesem Teil ähm auf dem wir seige Zeit verbracht haben. Wir hatten die eingeschränkten Datentypen oder abstrakte Datentypen Stacks und QS. Da ist tatsächlich so, dass mit dieser Verkettung wir eine bestmögliche Realisierung bekommen haben. Alle Operationen Worst Case Konstantzeit und wir haben diese Beschränkung in der Größe, die die Array basierte Lösung hatte. endlich hinter uns gelassen. Ähm, wir können aber viel allgemeiner in verketteten Listen an beliebiger Stelle einfügen und löschen, sofern wir das mit den Positionen wichtig lösen. Und wir können effizient über eine Liste eterieren in der Reihenfolge, in der die Elemente da sind, für eine verkettete, doppelt verkettete Liste, sogar rückwärts und vorwärts oder hin und her, wie auch immer. Aber die haben auch einige Nachteile, die in der Praxis durchaus schwer wiegen. Ähm, einerseits der Speicherplatz kommt auf die Anwendung an, wie schlimm das tatsächlich ist. Für die doppeltverketteten Listen ist es im Wesentlichen zwei Drittel nur overhead an Metadaten von Pointern, ne? Nur jeder dritte Eintrag, wenn die alle gleich groß sind, ist wirklich echte Daten. Das schon einiges. Ähm werden wir noch sehen, dass insbesondere für diverse Anwendungen dieser Punkt schwierig ist.

18:25 Wir haben keinen Random Access oder auf Deutsch wahlfreier Zugriff oder Zugriff per Index. Ich denke, Sie wissen, was ich meine. Ich kann in dem Array sagen, ich möchte an das 42. Element springen. Das kann ich in der verketteten Liste nicht machen. Ich weiß nicht, wo das Ding im Speicher liegt. Alles, was ich tun kann, ist vom Anfang anfangen und 42 mal den äh Pointer zum nächsten Element verfolgen oder 41 mal. Äh und dieses ähm sogenannte Pointer Chasing, also immer wieder ein Pointer verfolgen, der mich dann zum nächsten führt. Äh, das funktioniert, aber es ist relativ langsam. Einerseits, weil ich diese ganzen Schritte habe, aber auch, weil üblicherweise jeder Zugriff auf irgendeine andere Stelle im Speicher springt, so wie wir die Bilder auch malen und das in der Regel dann nicht gecasht ist. Äh zusätzlich ist natürlich auch diese Objekte anlegen in Overhead. dem kann man noch ein Stück weit entgehen äh indem man dieses Do it yourself Memory Management einsetzt, aber dem Overhead äh durch rein den dem Pointer defferenzieren, dem entkomme ich nicht ohne weiteres, aber man kann nicht alles haben. Ah.