Video 8-5: Einfach verkettete Listen

0:03 Im nächsten Abschnitt wollen wir endlich diese Einschränkung loswerden, dass unsere bisherigen Implementierung von linearen Listen und Stacks und wie sie alle heißen eine feste Kapazitätsobergrenze hatten, die wir im Konstruktor angeben mussten und danach nicht mehr verändern konnten. Das ist äh lästig. ist es eventuell auch eine Speicherplatzverschwendung, weil ich dann einen sehr großen eine sehr große Kapazität anfangs angeben muss, damit mir der Platz reicht. Und es ist auch eigentlich geschummelt, denn die abstrakten Datentypen sollen beliebig groß sein können.

0:43 Ich hatte eben schon die Frage gestellt, äh wie viel Erfahrung Sie d? Deswegen ähm hier kurz Ergebnisse einfach, um zu schauen, wie wie schnell oder langsam äh machen wir den Teil. Äh wieso oft ist in der Vorlesung die das breite Spektrum der Hörerschaft erkennbar? Ich denke, da gibt's ähm diese zwei Drittel um und bei, die das schon kennen, die das äh vielleicht in Kerninformatik Vorlesung einfach gesehen haben und dann gibt's das das Drittel, die vielleicht das ähm die die Vorle äh die vor die Vorgängerveranstaltung in Informatik gar nicht machen müssen.

1:24 Dementsprechend machen wir es ein Drittel langsam und zwei Drittel schnell. Nein. Ähm, ich mach's ein bisschen langsamer und die ähm dreiviertel ähm mögen wir es etwas nachsehen. Es ist aber dankswerterweise ein recht einfaches Konstrukt, das auch auch von null auf eigentlich relativ fix erklärt ist.

1:45 Wir hätten gerne Listen ohne feste Kapazität. Das heißt, wir müssen irgendwie die anders strukturieren in dem Array geht nicht. Und das Einfügen war ja sowieso auch Mist. Ähm, wenn Sie die Fortschritts fortgeschrittenen Vorlesung, die die Fortsetzungsvorlesung dieser Vorlesung hören, effiziente Algorithmen, werden Sie noch mehr über David Wheeler hören. Ist aber auch oder es wurde zumindest ihm nachgesagt, dass er hier diesen Spruch geprägt hat, der in der Informatik gerne verwendet wird. All problems in Computer science can be solved by another level of indirection. Und indirection heißt in aller Regel, man hat nicht direkt Daten, sondern man hat eine Referenz auf Daten oder eine Referenz auf eine Referenz auf Daten. Das ist damit gemeint. Äh, wenn man es damit übertreibt, wird alles kompliziert und langsam, aber es kann einfach helfen, Dinge flexibel zu machen. Und so auch hier konzeptionell war, was wir bisher gemacht haben, eine Tabelle, in der in jeder Zeile stand, was Nachfolger ist, der Zeile davor, s, dass wir direkt über die Adresse, über die Position in der Tabelle ähm das so und so viel Element zugreifen konnten. Ich kann, obwohl ich jetzt hier diese Reihenfolge gar nicht verändert habe, mir auch die Speicherweise ein bisschen anders denken. Ich habe immer noch Adressen, die sind aber hier bewusst sozusagen nicht numerisch, damit man gar nicht in die Versuchung kommt mit denen zu rechnen. Und stattdessen merkt sich jedes Element, wo steht denn die nächste Zeile, in der das nächste Element steht.

3:18 Und hier folgt das im Wesentlichen immer einfach der nächsten Zeile. Aber das müsste hier im rechten Beispiel nicht so sein. Ich könnte jetzt auch auf die Idee kommen zu sagen, ja, C, nee, C liegt bei mir jetzt hier unten irgendwo in der Fortsetzung von dieser Tabelle. Also hier ist jetzt mein eigentliches C und dann ist der Inhalt, den ich hier vorher hatte, der steht jetzt hier an einer anderen Stelle im Speicher z.B. Aber die Bedeutung für die Liste ist äh die gleiche. Ich kann immer noch von 1 zu 2 zu 3 zu vier und zu fünf gehen.

4:01 Wir brauchen dann noch irgendeine Konvention, um zu sagen, jetzt ist Schluss, das ist das Ende der Liste. Ich habe hier mal dieses dieses Bottom Symbol genommen, was gerne für undefiniert gerade in der Logik oder so verwendet wird. In der Implementierung nehmen wir dafür in der Regel Nullpointer. Das ist genau was diesen tun.

4:28 Das ist die Idee. Also jedes ähm jede Zeile repräsentiert ein Stück von dieser Liste und merkt sich, wo es weitergeht, damit wir das tatsächlich umsetzen können. Java ist jede Zeile ein Objekt und die Wo geht es weiter sind Referenzen auf andere Objekte. Wir haben also so eine Art, wenn man das das erste Mal sieht, finde ich verwirrend, eine selbst ein selbstbezüglichen Datentyp.

4:52 Normal kann man sich denken, dass ein Datentyp aus anderen Teilen besteht, sowie ähm unser Fixed Size äh Stack war ein Objekt und das hatte ein Array, um die Objekte zu speichern. Da kann ich mir vorstellen, ich habe hier mein Fixed Size Fixed Size Array Stack. Ich kürz mal ab und da drin hatte ich dieses Object Array für Elements. Da kann ich mir vorstellen, das ist einfach ein Teil von dieser größeren Box. Was wir jetzt bauen werden, sind Objekte, die auf andere Objekte des gleichen Typs zeigen und niemand hindert sie daran, da auch Kreise zu bauen oder irgendwelche komplizierten Konstrukte, dann kann ich diese Darstellung, alle Objekte sind sozusagen Teil von was größerem, kann ich nicht mehr machen, weil das plötzlich selbst bezüglich ist und äh Kreise enthalten kann. Deswegen werden wir die Dinge ein bisschen anders malen, nämlich als eine Box pro Instanz und dann eben Zeiger oder Referenzen sind Pfeile von einem dieser Knubbel hier soll eine Referenzvariable sein in Java, ja, wo ich ein ein Objekt eine Objektrefferenz speichern kann und der Wert davon ist das Ende von Pil. Okay, wenn sie das schon gesehen haben, ist es so intuitiv, dass sie gar nicht mehr drüber nachdenken.

6:18 Äh, nur noch mal der Vollständigkeit. Nullpinter habe ich hier so gemalt, wie wie eine Erdung. Also hat das Donald Koth gemacht. Fand ich einprägsam. Also, ich könnte meine meine Liste hier aus diesem Beispiel so repräsentieren und äh dann ist egal, wo genau im Speicher diese Boxen liegen, solange jede weiß, wo das weitergeht. Das ist die Idee von verketteten Datenstrukturen.

6:49 Im Code können wir das auch genauso umsetzen. Wir haben Objekte für diese einzelnen Boxen für die Knoten. Die heißen hier List Notes. Das ist aber tatsächlich eine Klasse innerhalb von der umgebenden Klasse, die diese verketteten Listen implementiert. Zum Namen noch mal. Weiß ich nicht, hatte ich das hier irgendwo auf den Folien nicht wirklich. Äh, auf Deutsch würde man verkettete Listen sagen. Ähm, der englische Begriff ist Linked List. Ich habe in meinem Code die Englischen belassen, damit sie beide kennen. Äh, gewöhnen sich an das Chaos. Äh, wir haben also eine äußere Klasse Linklist, die auch wieder dann eine lineare Liste implementiert. Und wir haben diese Knoten, die diese einzelnen Boxen innerhalb von so einer Linked List darstellen und die bestehen aus einem Wert und Einheffen Verweis auf das nächste auf die nächste Box und die ist eben vom gleichen Typ. Das ist, was ich eben schon gesagt hatte. Äh, dann gibt's hier noch eine clevere Mikrooptimierung Mikroooptimierung, wenn Sie so mögen.

7:53 Wir können ähm diese List Notes selbst auch als Positionsobjekte verwenden. Da wer wir gleich noch im Detail drüber sprechen. Ähm, da jetzt eh hier auf der Folie drauf ist. Ich habe hier noch was gemacht, ähm was mehr Software Engineering als Datenstrukturen ist, aber der Kürze, das hier ist eine Private Innerclass, von der ich nicht möchte, dass jemand von außen die überhaupt sehen kann. Warum? Na ja, Datenkapslung und meine Invarianten intern, die möchte ich beschützen. Ich möchte nicht, dass jemand von außen z.B. für so ein Zeiger, so eine Referenz umbiegen kann und mir meine Liste zerschießt. Wenn ich aber die List Notes als Positionsobjekte verwenden möchte, dann müssen die Teil vom öffentlichen Interface sein. Ich muss die zurückgeben können und jemand anderes muss sie mir von außen wieder reinreichen können. Das widerspricht sich offensichtlich. Ich will einerseits die Listes nicht rausgeben und andererseits will ich sie rausgeben. Und der Trick ist, es geht beides. Man macht eine eine Oberklasse, die nichts kann und die man auch von außen nicht instanzieren kann. Alles private, aber die Klasse selbst ist public und unser Listne erbt davon.

9:12 Das heißt, von außen sieht das immer nur aus wie ein Positionsobjekt, das nichts kann, mit dem ich nichts anfangen kann, als es hin und her zu schieben. Aber für uns intern ist es eben ein Liste. Okay, kleine ähm kleine Optimierung an der Stelle, die wenn Sie sie nicht verstehen, können Sie die einfach ignorieren. Dann machen Sie das public und streichen den Teil. Funktioniert auch.

9:44 Okay. Äh ansonsten bildet das direkt ab, was wir hier in den Boxen gemalt haben. Wir müssen jetzt nur noch die Operationen auch entsprechend implementieren und äh das könnten wir direkt auf den allgemeinen Listen machen. Es ist aber für Stacks hier noch mal wieder ein Ticken einfacher. Deswegen das zuerst ähm für Stacks stelle ich mir die Liste so wie ein Stapel nach oben wachsend hin vor. Und wie funktioniert das jetzt? Also ein Linked Stack, ein Stack basierend auf so einer verketteten Liste, der speichert sich eine extra Variable, eine extra Box, die ähm ist keine Instanz von List Note. Vielleicht sollte ich es anders malen. Das ist eine Variable, die auf dieses oberste Element zeigt. Wir merken das immer den den obersten Eintrag auf dem Stack Liste. Die Klasse ist genauso wie eben. Abgesehen davon, dass ich keine Position hier brauche im Stack. Und hier sind die Operationen Top. Wenn ich das oberste Element zugreifen will, muss ich diesen diese Referenz verfolgen und auslesen, welches Element da steht.

10:47 In dem Fall 7 mache, indem ich hier drauf zugreife. Wenn ich ein neues Element einfügen will, das war das also gibt in dem Fall 7 zurück. Ja, ähm wenn ich ein neues Element einfügen will, dann lege ich erst ein neues eine neue Box an mit dem Wert, den ich einfügen will. Also hier machen wir Push 66.

11:20 Ich lege so ein neues Objekt an. Das soll jetzt Teil von diesem Stapel werden. Das heißt, ich muss hier die entsprechenden Zeiger setzen. Das hier soll auf die sieben zeigen und top hinterher auf 66. Das sind diese beiden Aufrufe. Ich äh klaue mir was bisher in Top war, als das ergibt als den Wert für meinen Nextsteiger und biege Top um auf das neue Element. Und hier bewusst so ein bisschen ähm aus der Reihe gemalt. Es ist völlig egal, wo diese Box im Speicher liegt. Ja, ich muss nur die Referenzen aktualisieren und Pop ist ähnlich. Ähm, dann würde ich einfach top hier auf das next von Next biegen und dann ist das Element entfernt.

12:07 Und wir sehen keine nirgends im Code steht eine Obergrenze für die Größe vom Stack. Ich kann das so lange ausführen, bis mir irgendwann bei diesem Aufruf von New List Node die Java Runtime sagt, keinen Speicherplatz mehr auf dem Hieb, dann habe ich mein Limit erreicht. Aber das ist sozusagen ein Limit, dass man konfigurieren kann von außen. Das ist nicht fest im Code vergeben. Deswegen ist der Stack selbst unbegrenzt groß.

12:41 Äh bevor wir zur allgemeinen Liste kommen, schauen wir uns auch die QS noch an. Die sind fast genauso einfach. Was sich ändert ist, dass ich an beiden Element an beiden Enden der Que einfügen bzw. löschen können möchte. Äh für den Einfügeteil äh sorry, für den entfernen Teil Front sieht das fast genauso aus wie im Stack. Da habe ich eine Variable front, die merkt sich den Eintrag, den ich als nächstes entfernen soll, den ersten Eintrag in der Queu einfügen hinten habe ich eine extra Variable Rear, die auf das letzte Element zeigt, dass ich aktuell in der Que gespeichert habe. An der Stelle ähm sehen Sie so ein bisschen ähm klingelt vielleicht die Erinnerung von den von den Ringsp von den Ringpuffern noch nach. Was mache ich mit Rear? Wenn die Q leer ist, dann kann ich entweder sagen, ja, dann ist Rear halt null in dem Fall, das wäre eine Option. Dann habe ich aber überall, wo ich Rear verwende, jetzt noch ein extra Fall, den ich zu überprüfen habe.

13:46 Oder ich müsste mir irgendwas anderes ausdenken. Und die, was wir hier uns ausgedacht haben, ist es gibt immer einen extra Knoten front. Hier ist es ein echter extra Knoten, der auch kein Element speichert. Der hat quasi Nall als Eintrag für für dieses Element und der ist aber immer da, selbst wenn die Que leer ist. Das heißt, ich habe immer einen Eintrag, auf den Rear zeigen kann, ohne dass es äh diese extra Fallunterscheidung braucht. Ist Rear null oder nicht? Das zeigt immer auf ein gültiges Listode Objekt und das macht den Code an einigen Stellen kompakter. Ähm z.B. kann ich jetzt bei ähm bei DQ, da rufe ich eh Peak auf. Ähm eigentlich sieht man es nur bei Inq hier an der Stelle, aber eine kleine Optimierung ist es trotzdem. Äh ich kann hier jetzt einfach auf rear.n zugreifen, ohne mir Gedanken machen zu müssen, dass das vielleicht null pointer Exceptions wirft. Also für in würde ich ein neues Element anlegen. Ja, dann habe ich hier mein an + 1.

15:07 Das hat jetzt einen Nullpinter, aber ich würde dann von Rear, das Element, was ich hier mit finde, diesen Zeiger, den würde ich jetzt umbiegen auf das neue Element.

15:21 Und letztlich würde ich Rear auch Und das funktioniert auch, wenn die Queue am Anfang komplett leer ist. Dann würde nämlich Rear auf Front zeigen. Da habe ich auch einen gültigen Next Zeiger, den ich umbiegen kann. Ich habe halt dann nur äh ein anderes Element verwendet, aber ich brauche keine Fallunterscheidung.

15:42 Okay, wo man aufpassen muss, ist bei Peak, ich lese hier dann nicht direkt in Front den Wert aus, sondern ich muss immer zum ersten echten Element wechseln, also ein einen Pointer verfolgen, eine Referenz verfolgen.

16:01 Ist so eine Mikroimierung, aber auch da ähm das ganze Thema mit verketteten Listen ist nur dann spannend, wenn man sich wirklich eine konkret eine konkrete Implementierung auch anschaut. Äh, die sind nicht konzeptionell schwer, aber an diesen Randfällen kann man sich aufhängen. Deswegen wollte ich Ihnen an den ein paar verschiedene Implementierungen im Detail zeigen, wo Sie diese war Optionen sehen, die man hat. Ähm hier bei den Stacks z.B. ist es nicht so. Ich habe eine Referenz top und die kann auch null sein, dann ist der Stack eben leer. Ich muss dann eben drauf aufpassen, dass ich nicht drauf zugreife, aber das äh prüfe ich hier bei äh Top sowieso. Äh und empty ist hier eben die für der Vergleich mit Null. Andere Option ist, man hat so einen Dummy Knoten, der einem diesen Fall abwängt.

16:55 Okay, jetzt können wir also Stacks unds bauen. Was ist mit allgemeinen Listen? Wir hätten ja ähm damit jetzt schon das Problem gelöst, dass die Kapazität beschränkt war. Kann ich den auch in der Mitte einfügen und löschen? Und die Antwort ist ja, gar kein Thema. Z.B. Insert, wenn ich diese diesen Teil der Liste habe, also die geht vielleicht hier irgendwie noch lange lange weiter, aber ich habe eben eine Position, die mir jetzt hier äh diesen Teilausschnitt rausgreift und ich würde gerne ein neues Element Y zwischen diesen beiden einfügen. Na ja, dann lege ich einen neuen Knoten mit Y an und biege die Pointer entsprechend um. Und dann ist der Weg von X weiter in der Liste vorwärts jetzt über Y. Das heißt, ich habe das dort eingefügt. Jeder, der danach die Liste von vorne nach hinten verfolgt, würde erst X, dann Y und dann Z lesen. Ganz einfach. Und auch Konstantzahl, egal wo in der Liste ich bin. Ich muss einen neuen Knoten anlegen und zwei Referenzen ändern.

17:59 Löschen ist fast noch einfacher, wenn ich hier umgekehrt die Situation habe, ich habe hier mein Y, was ich entfernen möchte mit einem vor Nachgänger, vor Vorgänger und Nachfolger, dann ähm biege ich den Vorgängerzeiger auf meinen alten Nachfolger um. Das heißt, wer jetzt anfängt hier vorne zu lesen, der überspringt Y einfach. Und das war's. Ich kann d jetzt noch ein bisschen aufräumarbeiten machen. Das heißt, äh um Leutering zu vermeiden, würde ich vielleicht hier die Referenz auf Null setzen und ich könnte ich könnte das Objekt jetzt direkt irgendwie dem äh Garbage Collector übergeben mit ich bin fertig. Dafür gibt's in Java nicht wirklich eine einen Mechanismus. In anderen Sprachen würde man das an der Stelle tun.

18:57 Ja, äh freigeben, dann ist es weg. An dieser Stelle sehen Sie für beide Operationen aber einen Ball, um den wir uns irgendwie kümmern müssen. Wir brauchen nämlich in beiden Fällen Zugriff auf den Vorgänger. Wir brauchen auch eventuell Zugriff auf den Nachfolger. Das ist aber einfach, zumindest beim Löschen hier. Den Nachfolger, den habe ich ja, das ist ja mein Nachfolger. Also dieses Z, wenn ich hier löschen möchte, ist einfach zu kriegen. Den Vorgänger kriege ich dagegen nicht ohne weiteres. Ich habe keinen Zeiger rückwärts in dieser ersten Version. Klammer auf. Nächstes Kapitel schauen wir uns an. Wenn man sich mehr Speicher gibt, kann man da was vereinfachen. Ähm, muss man aber nicht. Man kann auch anders damit umgehen. Wir können hier einfach eine Konvention treffen, dass Positionen in einer verketteten Liste immer auf den Vorgänger zeigen. Also wann immer ich eine Position verwende, um in der Liste irgendwo was einzufügen oder zu löschen, dann möchte ich, dass die auf den Vorgänger von dem eigentlichen Element zeigt. Oder sie können auch umgekehrt sagen, eine Position auf einem Knoten hat logisch als Referenzelement den Nachfolger davon.

20:16 Wenn ich die Konvention treffe, dann kann ich all diese Probleme hier umgehen, denn beim Einfügen habe ich dann X, das heißt, ich habe X und auch Z als seinen Nachfolger und kann die entsprechenden Zeiger umbiegen. Wenn ich löschen will, habe ich auch X und kann entsprechend auch wieder alle Elemente finden.

20:39 Das einzige, worum man ähm aufpassen muss, ist, dass man diese Konvention strickt einhält, wann immer man denn äh im Code auf irgendwelchen Objekten arbeitet. Kommen wir gleich zu. Ähnlich wie bei den Q kann man sich auch wieder einige ähm Kopfschmerzen mit Randfällen ersparen, indem man Dummy Knoten benutzt. Und hier gibt's noch den zusätzlichen Fall, dass ähm äh ich irgendwie erkennen muss, wann ich am Ende angekommen bin. Ähm es es stellt sich raus, wenn sie können einfach durch durchprobieren alle anderen Optionen ähm rauskriegen. Die eine eine schöne Konvention hier ist, dass man immer einen Dummy Knoten Head hat, der da ist, auch wenn die Liste leer ist und kein Element speichert und aber den Zeiger auf das erste Element vorhält. Und auch noch ein Dummy Knoten für den das Ende der Liste, der wiederum mit seinem Nextzeiger auf das letzte Element zeigt. Mit den beiden Dingen lässt sich bequem arbeiten. Wir haben also hier diese Invariante, dass der Nachfolger von Tail der Vorgänger von Tail ist. Also ich habe am Ende hier immer so eine kleine Schleife gebaut.

21:52 Wenn man das einhält, dann sind die Operationen relativ bequem zu machen. Auch hier wieder nicht die einzig denkbare Option, aber das ist eine der weniger nervigen.

22:04 Ich habe also auch in ähm einer leernenliste diese zwei Knoten immer Head und Tail sind echte Knoten, ein eigenes Listode Objekt. Ähm ich inzialisiere die so und setze die Invariante. Am Anfang, wenn die Liste leer ist, habe ich nur Head und Tail. Das heißt, der Vorgänger von Til ist head. Zeigt also darauf, das ist dieser Teil. Ähm, beachten Sie jetzt insbesondere, wie wir die Positionen handhaben. Die Konvention war ja, Position ist immer ein Element vor dem, dass wir eigentlich meinen. Die Startposition ist das erste Element in der Liste. Das heißt, ich kann hier Head zurückgeben, denn das ist das der Knoten vor dem Element, das ich meine. Ebenso bei End hätte ich gerne das äh logisch hinter dem letzten Element. Also eigentlich Tail, aber ich brauche jetzt den Vorgänger von Tail. Den habe ich mir dankenswerterweise in Tail next gemerkt. Das ist die Invariante. An der Stelle ist die bequem. Wenn ich auf ein Element zugreife, dann muss ich dran denken, ich muss zum Nachfolger gehen, nicht auf dem auf der Position selber arbeiten.

23:16 Gleiche, wenn ich ähm einen Schreibzugriff mache und na ja, Vorrücken ist wiederum einfach. Die anderen Operationen sind auch nicht konzeptionell schwierig. Man muss nur einfach an diese diese etwas ungewöhnliche Konvention denken, dass wir auf den Vorgänger zeigen. Äh für Insert, ich lege einen neuen Knoten an, der bekommt schon als Nachfolger dieses ähm den äh bisherigen. Also, ich habe Pred ist schon hier dieser ähm ist dieses Element. Pred next ist der alte Nachfolger, das was vorhin Z hieß. Den bekommt X direkt ähm als Nachfolger gegeben und dann muss ich noch den Vorgänger auf den neuen Knoten umbiegen. Jetzt kann es mir passieren, dass ich am Ende der Liste eingefügt habe. Dann muss ich diese Invariante von oben, das Tail auf seinen Vorgänger zeigt, wiederherstellen. Falls also der der neue Knoten der letzte ist, sprich sein Nachfolger ist Tail. Dann muss ich tail next umbiegen auf den neuen Knoten. Dann habe ich die Schleife eins weiter nach hinten verschoben.

24:30 Das ist der Teil. Ähm und für Delete, ich habe eine Position löschen möchte ich das Element. Danach setze ich also da das Null und das Löschen selbst ist dieser eine Zugriff. Ich mache den biege den Zeiger um, so dass er das Element, das ich löschen möchte, überspringt. Auch da habe ich den Fall, dass ich die Invariante wiederherstellen muss, falls ähm das Element, dass ich ähm weil es hinterher jetzt, weil es das Element, das gelöscht habe, das letzte war, dann ist jetzt die Position auf dem Element vor Tail und dann muss Tail jetzt auf diese Position zeigen, weil das vorherige Element gelöscht wurde. So, okay.

25:20 Beachten Sie, dass das für die Operation alles wunderbar funktioniert, aber eine etwas seltsame ähm Semantik für die Position bedeutet, denn äh nach einem Löschvorgang zeigt das P jetzt logisch auf den Nachfolger von dem Element, dass ich gelöscht habe. Wir sehen, wie klar, dass ähm dass ich beim Löschen die Position nicht auf dem Element belassen kann. In diesem Fall, weil das nicht mehr in der Liste ist. Das zeigt aber immer auf das auf den Nachfolger. Was subtiler ist, ist, dass wir alte Positionen auf dem Vorgänger von dem gelöschten Element jetzt ungültig sind, denn ähm äh ähm alte alte Position auf den Nachfolger, die hätten auf den Vorgänger gezeigt und den habe ich jetzt entfernt. Das heißt, da wurden die Positionen jetzt ungültig, die darf ich nicht mehr verwenden. Das lässt sich an der Stelle nicht nicht vollständig umgehen, wenn ich diese Position so definiere. Ähm, auch bei Insert habe ich diesen Effekt, dass das Element, dass das ähm die Position auf das neue Element zeigt nachher, weil das eben der neue Nachfolger ist.

26:35 Das könnte man ändern, wenn man Position mutable macht. Das hat aber andere Probleme. Also, Long Story short für diesen Teil. Äh Positionen sind ein bisschen trickreich, haben wir schon gesehen. Im Detail hängt es hier von der Implementierung der verketteten Liste ab, was die genau machen. Wenn ich Insert und Delete Aufrufe habe. Sollte man also tunlichst genau aufpassen, was passiert. Auch da wieder der Grund ähm ist sicher alles ein Grund, warum Java das im Wesentlichen verbietet, dass man Position, wenn gelöscht wurde, noch mal verwendet, einfach weil die die Semantik kompliziert wird.

27:18 Letzter kleiner Punkt, bevor wir dann ähm am Mittwoch wohl zu den doppelt verketteten Listen kommen, die ein paar der Konvention einfacher machen. Ähm eine Anwendung für solche verketteten Listen, die ähm einerseits adressieren, was was Java auch für uns schon tut und was man manchmal auch von Hand nachbauen muss. Wenn ich so einen Aufruf habe, der einen neuen Knoten, so ein neues Listne Objekt anlegt, dann also normalerweise heißt, wenn ich nicht irgendwie keinen Speicher mehr habe, dann findet Java für mich irgendwo ein Stück ein Schnipselchen freies äh freien Speicher und verwende den dann für dieses für dieses Objekt. Wie macht Java das eigentlich?

28:00 Weiß nicht, ob Sie mal drüber nachgedacht haben oder nachgelesen haben. Das ist natürlich ein Thema, was auch dann ähm in der Betriebssystem Vorlesung genauer kommt. Ähm durchaus also kann einem passieren, dass man das selbst bauen muss, wenn man mal sowas wie eine JWM bauen muss. Durchaus ähm häufiger als man vielleicht erwartet, weil die Dinger immer wieder neu erfunden werden. Und es gibt auch einfach performance kritische Anwendung, wo ich das selbst in die Hand nehmen möchte, damit ich nicht für jedes kleine Objekt einen Aufruf ans Betriebssystem habe. Für all diese Fälle macht es Sinn, sich zumindest konzeptionell zu überlegen, wie man das machen könnte. Ähm Vereinfachung hier im Vergleich zu was das allgemeine Betriebssystem machen muss.

28:48 Wir schauen uns nur einen Typ von Objekten an oder eine Klasse. Das heißt, alle Schnipsel, die wir jemals brauchen, sind gleich groß und wir wissen auch schon, wie groß.

29:11 Das macht das Leben doch ein bisschen einfacher. Äh, die allgemeine Lösung verweise ich mal auf andere Vorlesung hier. Ähm, konzeptionell haben wir es ist ist ist das Vorgehend so, sie legen einmal am Anfang einen großen Blockspeicher zurück und verwalten den dann selbst und sorgen dafür, dass sie innerhalb von diesem Block dynamisch Speicher verwenden und wieder freigeben können. Ich stell mir das dann als eine große Tabelle vor und die Tabelle hat zwei Spalten. Eine für Daten, die Sie wirklich speichern wollen, z.B. Listenelemente und einen für so ein Nextiger. Und dieser Nextzeiger hat aber jetzt zwei verwene äh Bedeutung. Einerseits hat er den die Bedeutung von den Nextigern wie gehabt. Also z.B. diese Liste A geht eben von dieser Position zu hier und dann zu diesem.

30:07 Das heißt, ich kann ähm und -1 bedeutet hier null Pointer. Äh, das heißt, ich kann mich durch die Elemente einer Liste hangeln, aber sie sehen, es gibt auch noch Einträge für die ganzen anderen gerade nicht verwendeten äh Zeilen.

30:23 Und was wir da machen, ist eine Liste der freien Zellen auch in der verketteten Darstellung. Das heißt, ich habe hier vielleicht andere Farbe eine Verkettung aller Zellen, die gerade von niemandem verwendet werden, in genau der gleichen Weise und ich brauche beides, um das Effizient verwalten zu können. Also, wir modellieren das als eine Java Klasse so. Wir haben für jede Zeile hier ein Objekt Memory Cell. Das enthält eben ein Objekt für Listeneintrag z.B. und einen eine Adresse und wir legen am Anfang für ähm das könnte man vielleicht Capacity nennen, stattdessen wir legen am Anfang eine ein Array von diesen Memory Cells an, indem wir ähm eine bestimmte Kapazität an Speicherplatz reservieren. Und dann können wir dynamisch Speicher verwalten, indem wir sowohl die freien als auch die vergebenen Zellen in verketteten Listen verwenden. Und das Speichermanagement kümmert sich eigentlich nur um die Liste der freien Speicherzellen. Das hat einen das ist ein Stack im Wesentlichen. Also genauso wie wir den Stack vorhin implementiert hatten auf Basis von verketteten Listen, machen wir hier das auch.

31:53 Äh, Initial habe ich ich habe einen äh Index für den obersten Eintrag auf diesem Stack. Initial habe ich die so verkettet, dass quasi jedes Element auf das nächste zeigt. Und wenn jemand jetzt Speicher anfordert, dann gibt's diesen Aufruf allocate, bitte leg ein bisschen Speicher für mich an. gibt mir ein neues freies Objekt. Sofern ich noch Speicher habe, ist das immer der Eintrag, das nächste Freielement, den gebe ich dann zurück, aber vorher passe ich den noch an. Das heißt, ich setze das nächste Freielement auf den Nachfolger in diesem Stack. Das ist ein Pop Aufruf. Ja, und wenn jemand sagt hier das Adressstückchen hier, diese dieses Stück Speicher brauche ich nicht mehr, kannst du wieder freigeben. Dann ähm setzen wir im Wesentlichen unser Next Free, so dass das ähm auf dem Stack oben drauf gelandet landet. Also das freigeschäbene Stück, das ja auch diesen Next Pointer hat, setzen wir auf aktuell. oberste auf dem Stack und merken uns das auf die Art kann man in diesem festen Stück Speicher dynamisch Speicher ähm anen anderen Teil vom Programm allokieren und wieder freigeben und der Teil muss ich dann wiederum nicht drum kümmern, wie das funktioniert.

33:17 Äh, das ist in der Praxis deutlich schneller als jedes Mal ein einzelnes Objekt anzulegen, weil ich insbesondere diesen Teil effizient einmal am Anfang für alle machen kann und dann sind diese Aufrufe eben deutlich günstiger. Nachteil, ich muss eben die das Speicherlimit vorher festlegen. Ja, das hat man wieder, aber gibt durchaus ähm Fälle, wo man genau dieses Verfahren verwenden möchte.