Video 8-2: Lineare Listen

0:03 Im nächsten Abschnitt schauen wir uns den Hauptabstrakten Datentyp an. Lineare Listen. Was ist das? Was soll das? Äh letzt letztlich Dinge, die Sie kennen. Äh ein paar Details, über die man vielleicht nicht immer gezwungen ist nachzudenken. Möchte aber rauskehren.

0:20 Also, es ist ein Container oder eine eine Collection ähm die im Wesentlichen aus einer Sequenz von Objekte besteht. Wir werden gleich als sozusagen mathematische Struktur, über die wir die Bedeutung der Operation definieren, einfach so eine Sequenz von Objekten annehmen. Sie können auch äh sagen, es ist die Semantik könnte man als Array definieren. Das würde auch funktionieren. Ich habe hier bewusst das als mathematische Folge von Objekten äh geschrieben, um klarzumachen, das ist nicht wie wir es implementieren. Das ist rein äh eine Spezifikation, um zu erklären, was die Bedeutung der Operation sein soll. Äh, für mich heißt das äh lineare Liste oder linear List. Ähm, was nicht ganz das gleiche ist wie diese Java Utilist.

1:13 Die Idee ist ähnlich, aber auf die Details, wo sich ähm die Dinge unterscheiden, ähm werde ich noch eingehen. Ähm es ist eine dynamische Sequenz von Objekten. Der Punkt die Betonung auf dynamisch. Ich kann die Sequenz von Objekten verändern. Äh mathematische Objekte sind in aller Regel unveränderlich. Wir gehen davon aus, dass es ein Wert ist, der sich nie verändert. Wenn ich den verändere, habe ich einen neuen Wert. Dagegen sind die Datenstrukturen, die haben noch die gleiche Identität wie vorher. Ich habe sie nur verändert. Also, wir werden immer zwischen diesen beiden Welten so ein bisschen hin und her wechseln bei der Bedeutung. Äh hier ist ein Interface, was äh die Operationen angibt und ich werde gleich noch ein bisschen was dazu sagen. Die Operationen hier sind wahrscheinlich klar. Ich kann irgendwie Elemente einfügen an der bestimmten Position. Ich möchte in der Liste an beliebiger Stelle einfügen können und auch Elemente löschen. Und ich kann den Wert von einer Position auslesen oder überschreiben.

2:11 Das wäre sowas wie Zugriffsoperation in dem Array lesen und schreiben. Aber was hat's mit diesem Position auf sich? Position. Warum habe ich da noch so ein extra Interface und warum diese ähm diese komplizierte Konstruktion, dass die Klasse zwei Typ Parameter hat? Der erste ist, glaube ich, klar, das sind die Objekte, die wir speichern, aber der zweite, was soll das? Also, da ist ein zweiter Typ Parameter, über den ich ausdrücke, dass er eine Unterklasse von diesem Interface ist. Also, das ganze ist ein Interface. kann ich so noch nicht instanzieren. Ich muss es implementieren und jede Implementierung muss irgendwie angeben, wie diese Positionsobjekte aussehen. Der der Grund liegt letztlich darin, dass für verschiedene Implementierungen die Art von Position unterschiedlich sein wird. Kommen wir gleich noch mal drauf zu sprechen, wenn wir über die Bedeutung der Operationen sprechen. Erstmal abstrakt. Auf dem Abstraktionsniveau hier möchte ich abstrahieren davon, was das heißt, eine bestimmte Stelle in dieser Liste äh zu kennen. Also, ich habe eine Position, ich kann z.B. die erste Position in der Liste mir geben lassen oder die letzte und ich kann von einer Position nach vorne und nach hinten laufen und wenn ich so eine Position habe, dann kann ich diese Leseschreiboperation ausführen.

3:41 Okay, also wir abstrahieren erstmal einfach davon, was das heißt, so einen einen Finger in diese Liste äh haben zu können. Um die Operation zu definieren, was sie tun, ähm gehen wir davon aus, dass die Liste so eine mathematische Bedeutung hat, also eine Folge von Objekten. Und in der Beschreibung sind Positionen dann einfach Indizs, also Zahlen. Und A1 wäre z.B. Das erste. Dementsprechend ist die Startoperation in dieser formalen ähm in dieser Welt der mathematischen Sequenzen einfach die Konstante 1. Das ist die Zahl 1. Äh die dieses äh End äh da kommt jetzt der erste interessante Detailkram rein. Ist nicht das letzte Element, sondern eine Position dahinter. Das kommt von der Konvention, die wir sonst auch immer verfolgt haben, dass Startidcs inklusive sind, endcs exklusive. ähm ist aus ist eine Konvention an manchen Stellen einfach bequemer. Ähm damit ist klar, was Next und Previous machen muss. Einfach eins drauf addieren, eins abziehen. Ähm mit dem kleinen Randfall, dass ich eventuell, wenn ich ans Ende oder an den Anfang der Liste gelaufen bin, keine weitere Position habe und dann sind diese zwei Operationen letztlich verboten.

5:03 Und was man da in Java machen würde, wäre, wenn jemand die Operation aufruft, eine Exception werfen. Also, wir würden prüfen, kann ich noch einen Schritt nach vorne oder nach hinten? Und wenn dem nicht so Fall mit dem nicht der Fall ist, werfen wir eine Exception. Ich habe hier einfach nur Exception geschrieben, damit es kurz ist. Im Code würden sie natürlich irgendeine speziellere Exception verwenden wollen, die dem armen Programmierer, der da jetzt Mist gebaut hat, denn der hätte ja nicht diese Operation aufrufen dürfen an der Position, äh ein bisschen genauer sagt, was da jetzt schief gegangen ist. Aber das ist sozusagen der Software Engineering Teil, der nicht auf eine Folie passt. An der Stelle ähm ich habe so ein bisschen ihre Gesicht, es gab so ein paar Stirnrunzeln und komische Blicke. Was soll dieser Quatsch mit diesen Warum haben wir diese extra Position Operation, wenn die letztlich nur eins zu einer Position aufadieren und vielleicht diesen Check mit N machen?

5:57 Das klingt irgendwie überkompliziert und Sie werden gleich sehen, warum das an der Stelle ähm hilfreich ist. Aber ich stimme Ihnen sofern zu, als wenn ich nur diese Position äh wenn ich nur diese Liste habe, wie sie hier mathematisch hingeschrieben ist, dann ist das überflüssig, dann sind das einfach Zahlen und Indiz. Da bräuchte ich diese Operation nicht.

6:24 Bevor dazu kommen, noch kurz die anderen Operationen, die sind alle relativ selbsterklärend. Wieder angenommen, ich habe eine Liste so dargestellt und meine Position ist eine Zahl, dann liest Get eben das passende Element aus, sofern die Position gültig ist. Und wir haben hier eingeschränkt, ja, es darf nur eine Position ist immer gültig per Definition, außer es ist dieses hinter dem letzten Element. Das ist die einzige ungültige Position, die mein mein Positionstyp haben kann. Sprich, eine Implementierung muss das sicherstellen. Ja, ich kann hier gar nicht aufrufen mit -7. Das äh muss ich vom Typsystem her irgendwie unmöglich machen. Wer mal sehen. Ähm, ich kann einen Schreibzugriff machen, der ersetzt natürlich einfach das entsprechende Element durch einen neuen Wert. Auch wieder unter der Annahme, dass ich diese Operation ausführen darf. Ansonsten sollte ich wieder eine Exception werfen.

7:23 Ähm, weiß nicht, hier hätten wir vielleicht auch Exception werfen sollen. Weiß nicht, warum ich das da nicht geschrieben habe. Ähm, ein bisschen interessanter ist vielleicht insert. Äh, da habe ich eine Position und hier ist die Konvention. Wir fügen äh vor dem Element ein, auf das wir zeigen. Also, wenn ich das Pelement als Position hier habe, dann landet das X davor.

7:45 Hätte man auch dahinter schreiben können. Das ist eine Konvention, da muss man sich auf irgendwas einigen. Äh insbesondere das ist halt bequem, weil dann kann ich die Position mit dem mit diesem mit der Endposition ist ein Insert dann ein Anhängen ans Ende der Liste. Okay, beim Löschen ist es wiederum klarer, wenn ich auf ein Element zeige, dann ist das auch das, dass ich löschen möchte. Klammer auf. Sie können mal nachlesen, wie das bei Iterator in Java ist. Ähm, komme ich am Ende vom Kapitel noch zu. Ähm, für all diese Kapitel sortieren hatte ich es auch schon so gemacht und hier werden wir es auch wieder so machen und bei ein paar anderen. Ich schiebe so ein bisschen bis ans Ende von dem Abschnitt, was die Java Bibliothek macht. Also, ich möchte Ihnen erst so ein bisschen auf der grünen Wiese erklären, was die die äh Variante ist, wie man das bauen würde, wenn man keine sonstigen Constraints hat. insbesondere nicht die 30-jährige Historie von verpatzten Designentscheidungen und so weiter. Und am Ende komme ich drauf zurück, was stattdessen in Java gemacht wird, was auch nicht immer ähm das Klang jetzt sehr despektierlich. Äh, das sind oft Constraints, die auch durchaus relevant und wichtig sind in der Praxis, die man eben berücksichtigen muss. Äh und auf der grünen Wiese ist das Leben immer ein bisschen einfacher, aber sozusagen zuerst belasten wir uns nicht mit dem ganzen äh mit den mit den ganzen Einschränkung der echten Welt. Und am Ende möchte ich aber explizit den die Verbindung zu der Java Bibliothek machen, weil das ja letztlich ist, was sie verwenden sollen auch.

9:19 Also, dass sie mir alle hinterher äh lineare Listen neu bauen, das wäre die falsche Message da. Okay. Ähm zurück zu Delete. Ich lösche das entsprechende Element. Es sei denn, ich war auf dem End, dann kann ich nichts löschen, weil das äh kein gültiges Element ist. Jetzt habe ich ihn immer noch nicht wirklich erklärt, warum wir diese Positionsobjekte haben.

9:46 Es scheint ganz und gar unnötig, dass wir diese extra Positionsobjekte haben und irgendwie scheint das alles nur komplizierter zu machen. Aber nachdem ich so lange darüber rede, wird's schon ein Grund haben, nicht wah ähm warum können wir die nicht einfach als Zahl übergeben? Und wenn Sie ganz genau aufgepasst haben, ist ihnen vielleicht was aufgefallen in meiner Spezifikation. Ähm, ich hätte ich hätte eine fiesere Frage draus machen. Ich habe gleich noch eine Slido Frage, die dazu geht. Ähm, aber hier möchte ich es auflösen. Ähm, ich habe was unterschlagen in der Definition von meinen Operationen und der Punkt ist insbesondere bei Insert und Delete klar, was soll denn mit meiner Position, die ich übergebe, passieren, wenn ich dieses Inserwert oder Delete ausführe? Die Position ist ja ein Objekt von außen, dass der Benutzer äh reingibt und dann ist die Frage, auf was zeigt oder welche welches Element würde ich bekommen, wenn ich danach mit der gleichen Position Get aufrufe?

10:48 Und da gibt's einfach zwei nicht miteinander vereinbare Möglichkeiten, die beides Sinn ergeben und die aber einfach zu unterscheiden sind. Und mein Versuch mit dem Positionsobjekt war sozusagen eine ein Interface zu haben, was beidem gerecht werden kann, aber die Bedeutung im Detail ist unterschiedlich. Eine Option ist das eine indexbasierte Position. Also denken Sie einfach, P ist eine Zahl, wie auch in der Semantik. Das heißt, wenn ich eine Einfügeoperation mache, dann bleibt die Zahl, die ich da gesagt habe, füge an Position 5 ein. Die fünf bleibt die fünf, die ist davon unbeinflusst. Es gibt aber auch die Variante, dass ich mir das vorstelle, ähm, dass diese Objekte hier so in einer Reihe sitzen und ich habe sozusagen einen festen Finger auf einem bestimmten Objekt. Und wenn jetzt jemand hier ein neues Objekt einfügt, dann schaue ich immer noch auf dieses Objekt, weil ich habe da sozusagen eine Schnur dran festgebunden. Während in dem Indexmodell wäre das durchgezählte wie in einem Array.

11:55 Das heißt, wenn hier jemand was einfügen möchte und ich habe den Zeiger eigentlich auf die Position 2, wenn hier jetzt jemand was einfügt, dann ist dieses Element jetzt eins weitergerückt und dieses Element würde hier hinkommen und dann zeige ich plötzlich auch was anderes. Ist einfach ein Unterschied. Okay, also noch mal hier aufgeschrieben. Ähm, hier ist die Position immer das Pelement vom Anfang an gezählt, unabhängig davon, was ich mit meinem Insert und Delete mache. Während in dieser pointer basierten Position bleibe ich fest an meinem Element dran kleben und wandere mit dem nach hinten in der Liste, wenn jemand vorne dran einfügt. Und das wirkt sich eben darauf aus, was ich als Rückgabe bekomme, wenn ich in Delete mit Get mishe. Also, wenn ich einen äh so eine Position in einer Liste habe und jemand anderes oder ich selbst ruft zwischendrin insert weiter links in der Liste ein auf, dann ist bei einer indexbasierten Position der Wert von GET jetzt plötzlich ein anderer, denn das Element an diesem Index ist ja jetzt nicht mehr das gleiche wie vorher. Ich habe neue Elemente eingefügt, während für die pointer basierte Position würde GE immer noch den gleichen Wert liefern.

13:10 Okay, unvereinbar, aber beides eine sinnvolle Art von Position. Ähm, mir geht's nicht so sehr darum, sie zu verwirren, sondern ähm klarzumachen, dass das verwirrend ist. Äh, das sind einfach zwei Dinge und manchmal wollen wir das eine, manchmal wollen wir das andere. Also lieber explizit benennen, dass es beides gibt und dass man es eben auseinanderhalten möchte. Okay, werden auch sehen, dann in den Implementierungen ist das alles gar nicht so furchtbar kompliziert. Äh das komplizierte ist diese beeinheitte Sichtweise.

13:45 Zu guter Letzt, wenn das Ganze irgendwas mit der Realität zu tun haben soll am Ende, dann muss ja auch Java sich irgendwie diese Frage gestellt haben. Ähm in den Collections Frameworks. Vorg auf auf am Ende vom ähm von diesem von dieser Einheit, aber äh da gibt's jede Menge solcher Operationen und Positionen werden über Iterator Objekte abgebildet. Da viele von Ihnen damit gearbeitet haben, kennen Sie das wahrscheinlich. Ähm, was sind denn diese Iteratoren? Wenn es zwei Arten von Positionen gibt, muss ja auch Java diese Frage sich gestellt haben und ähm da muss es ja eine Antwort geben, oder?

14:31 Meine Hoffnung ist, dass sie da bisher nicht so richtig drüber nachgedacht haben, aber vielleicht tun sie es ja jetzt und stellen fest, es ist nicht so schwierig.

14:45 spricht soll keine Fangfrage sein, es soll einfach eine Frage sein, die sie zum Denken anregt. Also, da ich vorhin fast doppelt so viele Leute hatten in der Abstimmung. Ähm, mehrere Möglichkeiten, entweder sie sind müde oder sie sind sicher. Keine Ahnung, ist auch eine gültige Antwort.

16:34 Es ist auch nicht eine Fangfrage. So ein bisschen ähm ist die Frage durchaus subtil. Okay, jemand noch aktiv am darüber grübeln oder sollen wir mal äh Ergebnisse anschauen?

17:02 Keiner widerspricht. Also, es gibt ähm eine deutliche Mehrheit für Pointer basierte Position, aber durchaus auch viele viele andere Antworten. Ähm, ich habe in der Vorbereitung die zwei Antworten als richtig angehakt, aber ich glaube, ich würde es noch ein bisschen zurückdrehen. Man kann fast alles argumentieren hier. Ähm, der Punkt ist, es hängt tatsächlich an der Klasse, ne? Ich glaube, Iterator ähm kann beides sein. Also im Wesentlichen könnte auch beides richtig sein, aber eben für unterschiedliche Klassen, weil Array List ja auch äh Iterator implementiert und ziemlich sicher sind das da Positionen, also Index basiert. Also ein bisschen ähm ich ma mal überall den Haken dran, was natürlich widersprüchlich ist. Warum warum warum ähm muss man nie darüber nachdenken? Warum kann es nicht zu Inkonsistenzen führen? Also lassen Sie mich noch ein Schritt ausholen. Java verspricht, es gibt ein Interface List und dafür gibt's Implementierung Linklist und Array List.

18:11 Äh das ist jetzt ein Vorg später, aber für Linkedlist möchte man pointer basierte Position und für Aralist möchte man index basierte Positionen. Das ist das, was auf natürliche Weise für die beiden Implementierungen passt. Aber die beiden sind ja anders. Die haben eine andere Semantik. Ich kann also dann in meinem Code nicht einfach Arraylist durch Linked List ersetzen und krieg die gleichen Ergebnisse. Das wäre absolut harakiri für jedes Projekt. Ich kann dann nicht einfach die Implementierung austauschen. Das widerspricht allen Softwareentwicklungspraktiken.

18:45 Das hat Java nicht gemacht. Warum passiert da nie ein Problem? Weiß es jemand? Es fängt mit C an. Also darauf werde ich dann am Ende von dem Modul noch mal eingehen. Das Ding heißt Concurrent Modification Exception und sorgt letztlich dafür, dass sie nie beobachten können, wenn die zwei Positionen sich unterschiedlich verhalten hätten. Das ist einfach sobald ähm sobald es einen beobachtbaren Unterschied geben könnte, werden die Iteratoren invalidiert und sie dürfen sie nicht mehr verwenden. Das ist so die, ich nehme mal den großen Holzhammer und haue auf alles, was sich bewegt. Lösung für das Problem. Kann man kann man so machen. Ähm, die einzige andere Alternative ist zu sagen, pass auf, je nachdem welche Liste man hier verwendet, ist die Bedeutung eine andere. Für die Algorithmen möchte ich ähm beide Optionen erstmal offen halten und auch nicht die Holzhammermethode direkt vorschreiben, was bei uns heißt, nicht alle Listen sind gleich. Die verhalten sich unterschiedlich, je nachdem welche Art von Positionen sie implementieren und sie können dann aber ja sagen, welche Art von Position jeweils verwendet wird und untereinander sind sie immer noch austauschbar.

20:02 Okay, gut. Noch ein paar einfachere Kommentare nach diesem doch subtilen Punkt. Ähm ein ein Vorteil von dieser allgemeinen Formulierung, die beide Positionen unter einen Hut bringt, ist zumindest, dass man manche abgeleitete Operationen, habe ich sie hier mal genannt, rein auf Basis dieser Operation von oben aus diesem Interface implementieren kann, also dieser dieser hier, die hier erklärt waren, ohne zu wissen, was dahinter steckt. Und als Beispiel möchte ich Ihnen da ein paar zeigen, um sozusagen äh zu demonstrieren, dass man dass man mit dieser Abstraktion arbeiten kann, obwohl die Positionen unterschiedliche Semantik haben können. Also einfachstes Beispiel ist, ich kann eine eine Bequemlichkeitsmethode schreiben, die ans Ende von der Liste anhängt. Und ähm ein kleiner Nitpick in unserer in unserer Definition. Äh man würde eigentlich einfach Insert aufrufen wollen mit End. Ähm wenn die Liste leer ist, dann gab's da, glaube ich, ein einen Randfall äh wo man es besser so macht. Aber im großen und ganzen möchte ich Insert aufrufen mit End.

21:23 Äh vielleicht hätte ich das hier zuerst machen sollen. Prepend, da ist es tatsächlich ohne irgendeine Fall underscheidung. Ah ähm ist allen diese dieses Syntax bekannt der Elvis Operator kennen den Begriff.

21:42 Das hat so ein bisschen aus wie so ein Elvis Schmalzlocke Smiley und ähm das ist der der ternäre Operator für bals das hier, dann das ansonsten das. Also ein if else als Ausdruck.

22:12 ist eine kompakte Schreibweise macht manchmal ähm das Leben ein bisschen bisschen kompakter. Äh Prepand ist einfach, ich rufe Insert auf mit dem Start der Startposition.

22:24 Ähm was können wir noch machen? Wir können Hilfsmethode äh implementieren, die prüft, ob eine Liste leer ist. Dafür prüfe ich einfach, ob die beiden äh Positionen gleich sind.

22:42 Soweit so langweilig. Äh ein paar andere können wir noch machen, die ein bisschen mehr tun. Z.B. können wir die Suche implementieren. Also hier ähm so spezifiziert, dass wir das erste Vorkommen von einem Wert finden X, den wir gegeben bekommen. Und äh wie machen wir das? im Wesentlichen durch lineare Suche. Also äh es gibt die eine Variante, die sagt: "Suche in der ganzen Liste." Die andere Variante bekommt eine Startposition und ich möchte nur ab der suchen und die kann ich natürlich dann aufeinander zurückführen. Und die Variante, die an einer bestimmten Position losläuft, die hat jetzt so eine übliche Vorschleife mit Ieratoren, wie man die ähm oft bei solchen Collections hat. Ähm, sie haben vielleicht in Java auch diese for each ähm Notation gesehen.

23:49 Das ist aber nur sozusagen syntaktischer Zucker, eine Kurzschreibweise für sowas. Wir haben einen Iterator in dem Fall nicht eine Position in der Java Bibliothek, aber konzeptionell sowas. Wir haben einen Anfang, die Anfangsposition. Solange wir noch nicht am Ende der Liste sind, führen wir hier diesen Rumpf aus und danach setzen wir die Position auf Next von der Position hier. Das ist innerhalb vom Interface Linearist. Das heißt, dieser Next Aufruf geht ans gleiche Objekt. This d next.

24:20 Okay, das machen wir so lange, bis wir äh das erste Mal ein Element gefunden haben, das gleiche ist zu unserem X. Das ein Algorithmus, den wir äh schon kurz kurz angeschaut hatten, als wir überäre Suche gesprochen hatten. Das war die lineare Suche. Ich gehe alle Elemente in der Liste durch im schlimmsten Fall. Ja, das ist auch das einzige, was wir hier tun können aus zwei Gründen. Einerseits binäre Suche geht nur, wenn ich die Liste schon sortiert habe und hier lineare Listen machen keinerlei Annahmen an die Reihenfolge der Elemente, aber der zweite Punkt ist auch, ich kann gar nicht in die Mitte springen. Binäre Suche muss ja das mittlere Element aussuchen und vergleichen und das erlaubt mir meine lineare Liste nicht. Es gibt keinen Random Access in dieser in diesem abstrakten Datentyp. Вот.