wir haben in der letzten folge der vorlesung listen alsfelder dargestellt was was man im prinzip schon konnten wir können mit race umgehen was neu dazu kam war dass wir dieses dynamische größen können also sie wachsen lassen indem wir immer wieder neuen speicher und zu holen und und kopieren und da dem trick verwendet hat dass wir mehr speicher reservieren als wir gerade vielleicht brauchen dass man tatsächlich sogar den speicher exponentiell schnell wachsen lassen in der hoffnung erstmal damit um kopier aktionen beneiden können oder auf einige wenige reduzieren können und wären sogar gezeigt dass wir auch die
art und weise mit konstanten aufwand oder konstanten amortisierten aufwand ins ohne liste einfügen können wir schauen uns jetzt eine andere möglichkeit an listen zu implementieren und zwar durch verkettung wo dieses einfügen gewisser weise noch mal viel einfacher oder natürlicher wird da wo wir in die nachbarschaft information implizit dadurch gegeben haben dass einträge physisch nebeneinander im speicher liegen sondern ist dem logischen speicher nebeneinander liegen muss man diese nachbarschaft information einer verketteten liste explizit machen dazu brauchen wir eine hilfs der struktur das ist ein so genannter knoten auf englisch not und dieser knoten der trägt einerseits die
nutzdaten also das was ich tatsächlich in meiner liste speichern möchte gleich irgendwas design nehmer anti sind ganze zahlen und spreche hier zum beispiel 1 1 und jetzt hat jeder knoten neben diesem attribut data also die nutzdaten die er trägt 26 das zeigt auf die nächsten knoten in der liste und auf die art und weise können wir die knoten miteinander verkettet und uns eine liste aufbauen die irgendwann zu ende ist und dieses ende markieren java damit dass dieses next attribut 0 referenz an so lässt er heißt auch ein einfachere kettete liste denn wir können von einem
knoten zum nächsten knoten gehen aber nicht zurück diese rückwärts verkettung wärme im nächsten abschnitt die doppelt verkettete liste machen eine sache fehlt ihr noch wir müssen irgendwie den ersten knoten der liste auszeichnen wir müssen wissen wo es losgeht und deswegen halten wir uns eine referenz den ersten minuten und diese referenz nenne ich hätte so was können wir jetzt machen jetzt können wir zum beispiel eine liste durchlaufen in dem wir am knoten head anfangen und dann so lange laufen wie nicht die null referenz am ende erreichen also dass er nicht hier sind so lang kann irgendwas
machen den knoten ausgeben zählen ja auch immer und wenn man das gemacht dann gehen wir zum nächsten knoten in denen wir einen tag die referenz auf die referenzen punkt next setzen das heißt wir würden bei hat angefangen endlich weg und dann würden wir irgendwas machen mit diesem knoten dann zum nächsten knoten gehen also diese referenz folgen mit dem knoten was machen diese referenz folgen mit dem knoten was machen diese referenz folgen jetzt haben wir die null die schleife bringt er spricht ab und wir sind fertig dieser einfache algorithmus zum rasieren den kann man verwenden zum
beispiel um die anzahl knoten in der liste zu zählen wenn die liste so implementieren dass wir kein attribut haben dass die anzahl der knoten der liste immer mit zelt und das immer konsistent hält das kann man machen mache ich in dieser form von der liste nicht das heißt müssen tatsächlich zählen eine andere anwendung ist wir können bis zum letzten knoten gehen dass wir da hier auch hier ist es so da komme ich nicht einfach hin sondern ich muss immer von vorne am anfang der liste so weit gehen ich gehen möchte im gegenteil bis zum letzten
knoten was muss ich dann hier machen wo ich einfach einen punkt gut geschrieben hat ich merke mir jeweils den knoten n wo ich bin geht dann zunächst wenn dann die abbruch bedingungen kommt dann habe ich mir den vorletzten gemerkt und bin am ende letzten knoten der liste an und genauso kann ich beliebigen knoten der liste gehen die mich einfach die weiter zähle und dann die steife abbrechen es gibt natürlich jeweils ein sonderfall nämlich dann wenn die liste leer ist wenn hätte gleich null referenz enthält dann passiert hier gar nichts dann muss ich mir überlegen was
das bag macht den adp lust hatten wir vorbedingungen dem fall also ich darf die methode gar nicht ausführen muss das prüfen gegebenenfalls eine ausnahme aufwerfen gleich ist wenn hierfür endgültigen index angeführt dass terry hat man eine methode buschbeck um hinten was anzufügen ist jetzt ausgerechnet schwierig für diese form von der einfach verketteten liste x1 ein glück möchte was muss ich ihr machen ich muss einmal den letzten knoten finden weil an dem knoten willich einfügen da will ich noch anhängen das kann ich zum beispiel sowie hilfs methode beck macht wie wir uns mit hilfe von den
durchlaufen implementieren und wenn ich das gemacht habe da muss ich einfach nur das sorgen dass referenz auf den nächsten knoten also dass da hier in unserem letzten knoten ersetzt wird und zwar durch einen neuen knoten er hat keinen nachfolger dann streift man hier eine null referenz und er hat aber das datum drinstehen dass wir speichern nun den e mails einfach und hängen hier oben ein diese zuweisungen hier sorgt dafür dass wir diese referenz auf den neuen knoten haben und jetzt haben hinten das ein gebiet ist nicht schwierig es müssen nicht viel zu tun das eigentliche
einfügen das einhängen ist nur diese anweisung hier aber ich muss erstmal bis zur einfüge position kommen also das halt gleich mal fest das zweite hier kostet uns nichts das konvent konstante zeit machen und zuweisungen den knoten müssen wir irgendwie bauen aber da passiert auch nichts insbesondere müssten die operation nicht abhängig von der anzahl einträge die wir schon lange liste haben aber dieses laufen bis zum nächsten knoten sowie das gerade machen dass es auch von innen wenn die anzahl der knoten in unserer liste was können wir machen wir wollen nicht nur am ende einfügen sondern wir
wollen auch einer beliebigen position einfügen zeichnen die knoten jetzt nur noch als richtig an einer beliebigen position wir machen uns gerade mal so dass wir sagen wir kennen den knoten an dem wir einfügen wollen und zeichnen den beispiel hoch wieder und jetzt sagen wir wollen nach diesem knoten einfügen alle wollen zwischen diesen knoten und diesen knoten was einführen was müsst ihr dann machen wir brauchen einmal neun knoten den wir einfügen konstruieren wir uns einfach dieser neue knoten der trägt die daten die wir mit geben aber vor allem müssen wir für dieses neuen knoten schon welcher
sein nachfolger ist das ist nämlich dieser hier und da das nichts anderes als die next reference jetzt immer fast fertig und einzige was uns jetzt noch fehlt ist diese referenzjahr verkehrt ist bei der nachfolger von gerda hier sondern das ist unser neuer knoten das muss man auch noch beschreiben das meist punkt next ist gleich mit manchmal den neuen knoten noch namen geben sagt ela knoten current und wir sind fertig alles was man mit dem verketteten listen machen lässt sich sehr schön zu aufzeichnen mit den einfach verketteten listen ist es leichter oder wahrscheinlich deutlich leichter als
mit dem doppelt verketteten listen aber das prinzip ist immer das gleiche wir müssen schauen wie es ihnen die attribute geradeaus auf welchen knoten zeigt der nächste eintrag und wie soll sie nach aussehen wie es mein endergebnis und dementsprechend was muss ich nach und nach verändern um zu dem ergebnis zu kommen dass ich haben und durch diese zuweisungen hier sollte ich eben dafür dass das jetzt nächste knoten ist und jetzt läuft meine liste tatsächlich so wie ich das auch haben will über den neuen noten beziehungsweise diese alte pfeil hier ist ob so eine sache ist dabei
noch wichtig wenn man nach einem knoten einfügen wir wollen auch in der lage sein an ersten knoten was einzufügen also dass dies erst der knoten head von der liste wie füllt man hier ein dann immer einfach die konvention dass wenn der knoten nach dem wir einfügen der 0 knoten ist dann wollen wir tatsächlich den ersten knoten in die liste ein das ist gleichzeitig wieder im sonderfall weil immer wenn sich der erste knoten von der liste ändert dann muss ich tatsächlich auch diese referenz head ändern macht man das mal so sagen wir möchten am anfang der
liste einfügen also und zwei eigene position en schreibe ich einfach nur das soll gleichbedeutend sein mit einfügen hier möchte ich einfügen was muss ich machen ich muss einfach die head referenz umsätzen auf den neuen knoten bei uns hier wieder was wissen wir über den neuen knoten wir wissen dass der nächste knoten ja jeder hier ist also der dir vorher der erste in der liste ist wo kriege ich eine referenz auf diesen knoten her ganz einfach das ist die alte referenz diese hier dass es tatsächlich unsere head referenz vergeben die alte das ist der nächste knoten
und decken ein und sagen der neue head soll dieser grüne knoten und wenn man das machen und genau dieses bild der grüne knoten zeigt nach den hier das war einfach diese referenz diese referenz geht nicht mehr von head aus weil wir hätten setzen auf diesen knoten und müssen also der sonderfall das war am anfang ein fügen ihm gesagt gegeben über den knoten ein nachdem wir an einfügen am anfang geht das nicht deswegen nehme einfach die null als platzhalter um zu sagen wir wollen am anfang ein gefühl war es gibt noch einen anderen sonderfall das ist
der sonderfall ist die ja ist es gibt noch gar keine liste ist ein paar 0 referenz dementsprechend ist die einzige wahl die wir jetzt haben dass unser nachdem wie einfügen auch 0 ist es gibt sonst kein knoten in der liste das heißt wir machen im prinzip genau das gleiche spiel hier und es endet eigentlich gar nichts wir setzen die neuen head auf den neuen knoten und der neue knoten hat als nächsten knoten die referenz gerade in het speichern um das ist aber die 0 und damit das alles merken das heißt auch diesen sonderfall hammer damit
abgehakt diese sonderfälle auf die muss man aufpassen also was passiert wenn sich am anfang oder am ende das ändert bei der doppelt verketteten liste wenn man das nachher sehen wir dann muss man auch entsprechend beweise auch den anfang bei der doppelten verkehr bei der doppelt verketteten lässt er auch auf das ende mit updaten auf die neuesten stand so schauen wir uns das ganze nochmal auf den folien jetzt aber gut an unsere einfach verketteten müssten deswegen genauso aus wie es gerade aufgezeichnet habe die verkettung erfolgt in form von referenzen diese referenzen werden in den sogenannten knoten
notes gespeichert der knoten ist im prinzip eine hilfs klasse die liste besteht aus einzelnen knoten in jedem knoten habe ich einmal die nutzlast das was ich speichern möchte und eben den verweist die referenz auf den nächsten knoten wobei wir vereinbaren dass 0 das ende der liste bezeichnet auf die art und weise wenn man immer zunächst nächsten nächsten gehen meine einfach verkettete liste auf englisch singt we link lässt wir wollen das ganze ausdrücken in der klasse s löst dies angelehnt an die spd fordert ist aus der titus standort bleiben diese liste hält in der form einfach
nur eine referenz auf den ersten knoten also unsere klasse essen ist die implementiert erstmal was hat er aber das ist ein interface das war im nächsten abschnitt kennenlernen die implementiert noch ein anderes interface kraft ist aber dass es von mir um die liste auch visualisieren anzeigen zu können ein bisschen später darauf haben gesagt wir brauchen knoten dieser knoten ist tatsächlich eine hilfs klasse und hier macht man das was mein winter noch nicht macht dann wir eine klasse innerhalb einer klasse und das ist das sogenannte schacht orte klasse oder mästet glas als wir definieren die klasse
knoten innerhalb der klasse s lässt hier steht auch kein public davor kein public bedeutet privat beziehungsweise package privat also diese klasse not die knoten klasse die geht tatsächlich niemanden was an wir wollen die implementierung der liste ja auch nicht nach außen weitergegeben jeder knoten speichern lust nutzlasten data vom typ t und speicherten verweis auf den nächsten knoten also typ not beide referenzen initialisiert hier mit 0 braucht man die schnelle gar nicht gibt einen konstrukt damit er möchte den nutzlast haben und er möchte auch immer gleich wissen wer der nächste kenntnis und setzten beiden attribute entsprechend
die liste selber hat ein attribut nämlich hätte das ist die referenz auf den ersten knoten am anfang ist die liste leer steht in het 0 referenz so jetzt haben wir verschiedene methoden die erstes eis also wir schauen wollen wissen wie lang die liste ist dazu gehen wir einfach einmal von vorne nach hinten durch im prinzip genau wie wir es gerade eben skizziert haben so lange nicht am ende sind macht irgendwas in dem fall zell und geht zum nächsten coup und dann gehen wir das zurück was war gezählt haben und das ganze hat natürlich ein aufwand
der linear ist ein händen weil ich muss am anfang bis zum ende einmal durch die listen wenn ich bis zu einem bestimmten knoten zum mieten knoten geben gehen möchte dann mache ich das ganz genauso ich zähle einfach mit und 0 bis bissig am entsprechenden quoten wenn die immer zum nächsten das einzige was jetzt dazu kommt ist ich muss schauen ob die dass die tatsächlichen gültigen indexes das erfahre ich erst unterwegs also wenn ich schau komme ich überhaupt so weit wie ich gehen möchte oder erreiche ich vorher 0 referenz das muss ich einmal abrufen dafür haben
hier auch wieder eine hilfs methode die falls wir unterwegs 0 referenz treffen exception eine ausnahme aufwirft ansonsten ist das genau das gleiche wie gerade eben fürs 1 los dass wir eben nach wie vielen schritten abbrechen so push back hatten uns auch schon angeschaut wir haben im prinzip zwei fälle wir hatten mit dem allgemeinen fall angefangen ich hatte angenommen dass meine hilfs methode hätte hier ist die mit eingebaut und dann hängen wir hinten einen neuen knoten an sonderfall ist wenn die liste leer ist da können wir nicht so einfach nach hinten gehen weil dann gibt es
keinen letzten knoten dann fühlt man einfach den ersten knoten in die liste ein hier ganz wichtig ich muss die sonder für den immer betrachten in dem fall dass die liste lea ist wenn die liste leer ist dann kann es keinen ersten knoten geben an denen ich etwas anhängen das heißt dass hier dürfte ich nicht aus der code ist nicht so schwer zu lesen er ist auch relativ kurz was tut sich aber viel leichter ihn zu lesen wenn was ist tatsächlich noch mal mit auf malt so wie wir das gerade gemacht im sat after genauso wie
gesagt not gleich null soll beschreiben den fall dass wir vor dem ersten knoten also unmittelbar nach hat was nicht ganz richtig vor dem ersten knoten was einfügen dann ersetzt war einfach die head referenz durch den neuen knoten und dessen wächst der knoten ist head da ist egal ob vorher was im heck drin stand ob das 0 ist oder ob es tatsächlich auch den knoten gezeigt habe die liste ist danach korrekt oder wenn ich einen beliebigen anderen knoten habe dann muss ich mir einfach merken was der nächste knoten von diesen knoten war legen wir neun minuten
an der kriegt als nächsten dies next referenz und dann weiß ich das ganze zu ich hätte das auch in einer zeile schreiben können also dieses notebook next hier rein schreibt hier reinschreiben können der effekt wird der gleiche gewesen allerdings wäre es nicht so schlimm lesbar gewesen weil man muss sehen dass hier der alte werth drin steht und ihr der neue gesetzt wird ein tipp wenn ihr sowas macht macht im zweifel einen schritt mehr so dass es auch schön aufzeichnen können es ist einfach leichter lesbar und man tut sich nicht es bringt nichts an dem an
der stelle diese eine code zeile zu sparen so einer beliebigen stelle einfügen oder einem bestimmten index einfügen geht oder genauso am index 0 bedeutete am anfang einfügen da nehme ich einfach immer öfter mit sagen ich möchte am anfang einfügen jeweils im nu 0 referenz mit ansonsten zelig bis einem knoten vor dem knoten und fügt dann danach ein bereist wir schreiben keinen code doppelt zu verwenden einfach den code den wir uns überlegt hat nochmal und machen damit weiter weil wir finden für inside einfach das in saft in haft wenn man noch mal zurück gehen hier ist
eine funktion egal in welchem fall wir hier sind wir schaffen das in konstanten aufwand hier passiert nix außer das neue knoten erzeugt und eingehängt wird das geht 1 die inside methode ist warum weil wir in dem fall dass die größer als null ist erstmal ist an die einzige position uns vor handeln müssen genau wie für push back for buschbeck haben dann haben wir auch ob beck wir wollen den letzten eintrag entfernen dazu muss man natürlich schauen ob bei kap eine vorbedingung die liste darf mich leer sein ob es wenigstens einen knoten der liste gibt das
kann ich mit dieser hilfsfunktion check machen und die schaut einfach ob ich eine null referenz eingibt wenn ihn hat keine 0 referent steht dann kann die liste nicht mehr sein dann muss ich wieder bis zum letzten knoten gehen nämlich ganz den letzten wirklich aushängen ich muss also bis zum vorletzten gehen hängen danach den letzten knoten aus das könnt ihr euch selber mal aufzeichnen was hier tatsächlich passiert und noch ein bisschen allgemeiner raise ich möchte an der eaton position den knoten aushängen funktioniert auch wieder ganz genauso nur ich muss an diese position erst hin ich muss
mich also auch sowie bei inside an der stelle ich mich erst mal dort bewegen ja sowohl für pop beck als auch für ace auch wieder einen aufwand von ofen weil ich mich erst durch die liste bewegen muss das sieht erstmal sehr ernüchternd aus weil selbst so einfache methoden die sei es gibt die anzahl der einträge in der liste sind wovon app gibt er den mieten knoten ist offen weil ich immer bis zum entsprechenden knoten nicht erst vorhanden muss gleiches beim buschbeck beim pop beck und auch bei aris also wir haben alleine überhaupt nichts gewonnen dieses
traver sieren zum richtigen eintrag hin das macht uns ja sympathischen kosten im vvk ab und ist natürlich ein bisschen irreführend weil ich hab mir grad die operationen rausgesucht die beim vector hutin ufern 1 oder amortisiert den ofen 1 geklappt und harry weggelassen die jetzt bei unserer einfach kippen liste gut klappen und das sind die operationen wo ich vorne an der liste was ändern also in der es ist kann ich in konstanter zeit den ersten eintrag bestimmen das ist ganz leicht weil dass der eintrag auf den head zeigt wenn ich den ersten eintrag denn das hier
front haben möchte dann habe ich die vorbedingung dass die liste nicht leer ist dass es das was die checks methode überprüft und front sollen wir in dem fall ich den knoten zurückgeben wir erinnern uns der knoten knoten klasse ist privat es ist eine klasse innerhalb der klasse s das macht sie noch nicht privat aber ich habe ziemlich explosiv public gesetzt die geht niemanden was an das heißt wir wollen hier immer nutzers zurückgeben und nicht nur knoten zurück damit ist auch klar dieser knoten mit last muss existieren sonst kann ich fand mich aufrufen was macht front
busch front hängt einfach am anfang der liste einen neuen noten 1 und pop und hängt den wieder aus sowie front of pop und einen eine vorbedingung die ich ab prüfen muss bevor wir zur doppelt verketteten liste gehen schauen wir uns das gerade einmal noch kurz an was passiert wenn ich hier in die liste vorne was anhängen naja es ist ganz leicht ich bau mir einen neuen knoten und dem neuen knoten kenne ich die nächsten schon das ist nämlich das was gerade in het drinnen steht also ich nehme im prinzip diese referenz und pause hier ein
und dann setze ich die head referenz auf diesen neuen fertig jetzt habe ich was vorne ein lenkkopf front würde den ersten knoten wieder rausnehmen also einmal schaue ich das in het überhaupt gefüllt die referent steht dann weiß ich diesen knoten möchte ich rausnehmen sondern alles was ich jetzt mache ist ich schaue mir von diesem ersten knoten was ist denn der nächste hier was ist der da und diese referenz die trage ich jetzt einfach in het ein damit diese pfeil hier so lebt weil die referenz habe ich ausgetauscht und jetzt bin ich im prinzip fertig in
java muss ich nichts weiter machen dieser knoten der spielt einfach nicht nur mit irgendwann kommt der garbage collector und sagt den speicher für diesen knoten den möchte ich wieder haben wenn ansonsten man braucht und meine liste sieht so aus so viel zu einfach verketteten ist wo wir einfach verketten können kann man natürlich auch doppelt verketten die idee ist genau die gleiche nur dass zu dieser doppelt verketteten liste auf englisch der playlist jetzt noch zusätzliches attribut für jeden knoten dazu kommt ich habe nicht nur eine referenz auf die nächsten knoten sondern ich habe auch noch eine
referenz auf den vorhergehenden quoten also nicht nur next sondern auch previews gleichzeitig merke ich mir in der liste nicht nur den ersten knoten sondern auch den letzten nicht nennen hier taylor die bezeichnung ist nicht ganz konsistent mit unserer bezeichnung im winter weil david haye tatsächlich eine teil liste hier in dem fall ist oder sollte den letzten knoten bezeichnen so so sieht die klasse aus alles was passiert es ist dass wir neue andere knoten klasse haben mit einem zusätzlichen attribut das belaufen konstrukteur gesetzt werden und unsere klasse deel ist der frühling ist im gegensatz zu es
ist single link lässt die hat jetzt noch eine referenz auf den letzten knoten jetzt können wir im prinzip alles was war für die assist gemacht haben auch für die gel ist machen nur das was sehen einmal das verketten ist ein kleines bisschen mehr arbeit das ist der preis den wir zahlen dafür kümmern einige operationen mehr in konstanter zeit machen haben uns das auch kraft noch mal an und zwar sofort und push back das ist der code wie man gerade auf der folie gesehen haben also wir haben unsere liste mit dem ersten eintrag diese erste eintrag
hat keinen vorgänger also das treffen tribut 0 zeichne ein knoten einmal mit einem attributen danach das zu umständlich wie kommt der nächste knoten die hat auch nochmal nächsten knoten er hat auch dementsprechend vorgänger so wäre hier soll unseren letzter sein hier hat keinen nachfolger mehr dementsprechend muss der letzte knoten ist zeigt t also das was hier oben steht das in attribute und deal ist das was ich hier mache das sind attribute in unserer knoten klasse also die klassen not die wir innerhalb von dienst definiert was soll jetzt pusch front machen einmal pusch front bedeutet wir
wollen einen neuen knoten am anfang einfügen haben uns erst mal mehr platz immer noch das gleiche bild platz gemacht für den neuen knoten der da jetzt kommt wir müssen diesen neuen knoten einmal anlegen das passiert hier also dieser monaten von dem ergebnis ich bestimmte nutzlast mit das ist das argument angespornt von dem bisher hat kein vorgänger seid ihr auf die null referenz der hat einen nachfolger der nachfolger dass es der knoten auf den head gerade zeigt und den tag mit ihr beim aufruf des konstrukteurs schon ein jetzt sorgt man dafür dass head nicht mehr auf
den alten ersten sondern auf diesen neuen ersten knoten zeigt das heißt diese referenz hier ist jetzt obsolet was wir jetzt machen müssen ist wir müssen dafür sorgen dass der grüne knoten der vorher der erste war ja jetzt merkt dass er nicht der erste ist was ist falsch hier der grüne knoten hat noch einen beweis 0 referenz also in keinem verweis auf den vorgänger quoten wir müssen jetzt dafür sorgen dass dieser grüne knoten als vorgänger unsere neuen roten knoten bekommt dazu müssen wir diese referenz setzt diese präferenz setzen wie geht das das ist das was hier
passiert ein kleines bisschen trickreich dadurch dass wir mit den referenzen und mit den bezeichnungen spielen also wir haben hat schon gesetzt auf unseren neuen ersten kloten das heißt wir haben auch head punkt next schon gesetzt das ist nämlich ihr oben passiert und head next zeigt auf diesen grünen knoten dieser grüne knoten hatten attribut das ist das was wir setzen soll wollen das was vorher noch auf die 0 gezeigt und wir setzen uns jetzt auf den neuen ersten knoten und das wiederum ist der knoten auf den head jetzt auch hier es ist nicht ganz leicht zu
lesen es wird aber vielleicht aber muss ich auch mal also nach dem ersten teil ist wird das ganze so aus einmal hat es immer moden quoten next sind beim grünen knoten vom grünen knoten setzt man das attribut auf das worauf heck zeigt also auf den roten knoten fertig das haben wir verstanden jetzt müssen wir aufpassen jetzt schlagen wieder unsere sonderfälle zu nämlich einmal was passiert wenn es da keinen nächsten knoten gibt das heißt was passiert wenn uns liste am anfang leer war dafür haben wir dieses tief oben und auch noch mal den zweiten fall einer
schauen uns an wie das ausschaut zeigt nirgendwo hin wenn hat nirgendwo hin zeigt zeigt auch taylor irgendwo hängen und riss das wär was passiert jetzt wir machen einen neuen knoten er hat keinen vorgänger und als nachfolger hat er auch einen knoten mal als nachfolger hatte das passierten head steht das auch wieder beide jetzt setzen wir treffen zum auf diesen neuen knoten und jetzt zeichnet noch mal das zeichne ich das ganze noch ein bisschen schöner und zwar es gibt null referenz zwar nur einmal aber damit zunächst noch viele beide niederlagen verdoppelt so einfach einmal nach hier
einmal nach da und hat haben wir gesagt zeigt jetzt auf diesen neun soweit zimmer nachdem er die erste zeile ausgeführt haben in der zweiten zeile wollten wir jetzt den nachfolger von diesen knoten zu korrigieren dass dessen vorgänger auf den grünen knoten zeigt es gibt aber keinen nachfolger weil die liste ist hier gleich wieder zu ende das heißt ja immer erst mal gar nichts zu tun der erste fall er wird nicht ausgeführt so taylor habt ihr einen fall zu viel schon weggewischt zeigt vorerst immer noch auf die null referenz jetzt haben aber den knoten eingefügt wenn
tel 0 referenz wahr ist dass die liste war vorher lea wenn man was eingefügt haben ist die liste nicht mehr leer es gibt genau einen knoten also muss auch tel auf diesen noten zeigen und die entsprechende referenz haben ja gerade eben nachher eingetragen also diese beiden fälle als erste und das zweite hilft das sind die sonderfälle ein sonderfall mit zwei sonderfälle ein einzelner dass die liste und wer ihnen lehrern ist was einfügen wollen ganz genau so aber spiegelverkehrt funktioniert buschbeck vertauschte im wesentlichen head und tail ich muss nicht mehr wie bei der einfach verketteten liste
jetzt bis ans ende gehen sondern ich bin schon da in dem ich über taylor auf der couture ist der gleiche wie für push front nur das hätte und tail die rollen vertauscht können uns das noch mal ausführlich zu machen eine operation bleibt jetzt noch und zwar das einfügen nach einem bestimmten quoten auch hier haben wir wieder sonderfälle und zwar einmal dass wir am anfang einfügen wollen wir nehmen genauso wie weiter es ist bei der einfach verketteten liste wieder die konvention dass wenn wir nach dem knoten einfügen hatten wir einfach die null referenz einsetzen dann wollen
wir vorne einfügen vorne einfügen können aber jetzt schon wir machen das einfach in den bus front aufrufen wenn wir nach dem letzten knoten die referenz auf den letzten knoten steht intel einfügen dann kann man das einfach mit buschbeck machen dass man gerade auch implementiert also damit bleibt eigentlich nur noch der fall dass wir irgendwo mitten in der liste einfügen und wir wissen dass diese liste auch nicht leer sein kann weil es uns wärmer in einem von diesen beiden wellen gewesen also jetzt soll es noch mal darum gehen das heißt ich habe eine liste mit [Musik]
das ist der erste knoten der hat keinen vorgänger das ist der letzte knoten er hat keine nachfolger und wenn man hier zwei knoten und wir wollen nach diesem knoten hier einfügen also tun so als wäre der knoten nach dem wir einen hügel rollen was macht man jetzt die arbeiten im prinzip diesen code ab und malen uns alles auf was dabei passiert wenn man auch mal wird tatsächlich einfach also einmal speichern und die referenz not in der hilfs variablen pov reviews vorgänger warum das ist der knoten der danach gehe vor dem knoten kommen soll den mann
fühlen prv zeigt auch den gleichen knoten in not wir merken uns den knoten der im moment der nächste es ausgehend von diesem knoten also und next dann sind wir hier in diesen quoten merkt man uns in der hilfs variablen nxt not ein zweiter und den bezeichnen wir mit äxten jetzt beim 19 knoten den karren und aktueller neuer knoten b ab trägt bestimmt nutzlast das objekt dass wir hier mit rein geben aber von dem was man schon welcher knoten seinen vorgängern ist das ist nämlich der den wir mit pr bezeichnet hat und welcher knoten sein nachfolger
ist das ist nämlich der nehmen wir hier mit next bezeichnen kann das heißt dieser neue knoten den haben wir jetzt sie eingehängt war es noch nicht stimmt das sind diese referenzen hier die müssen wir noch korrigieren sowie korrigiert die wir kennen den vorgänger das ist das worauf die r v zeigt und wir müssen jetzt nur dafür sorgen dass dessen next referenz nicht mehr auf den hier zeit sondern auf 19 knoten und das machen wir einfach indem das hirn schreib airport punkt next soll auf unseren aktuellen club zeigen und umgekehrt der vorgänger von nxt soll auch
nicht mit der da hier sein sondern soll jetzt unser neuer knoten sei und damit haben wir einmal diese referenz und danach diese referenz ersetzt und wir haben den neuen knoten in die liste eingehen so dass man hier zum neuen knoten zum nächsten alten knoten kommen und umgekehrt vom nächsten alten knoten zu unserem neuen knoten und auch wieder zurück zum vormals erste knoten kommen wichtig hier ist mir braucht man der stelle keine sonder bei der mehr betrachten denn die haben wir alle erhoben schon abgearbeitet und dafür verwenden einfach gespannt und speck alles muss man einmal implementiert
auch nämlich nicht nochmal implementieren da bleiben uns treu informatiker sind faul der versuchen jedes problem einmal gut zu lösen und dann gesagt das land geschwemmt so speck und eben ins after löschen geht genau analog wir müssen auch hier wieder dinge referenzen umbiegen ersetzen in dem fall habe ich eine löschfunktion hier die den eaton knoten löscht das heißt ich muss wieder erst an den entsprechenden knoten hingehen ich muss mich einmal durch die liste der handeln entweder von vorne oder von hinten und dann kann ich löschen dann kann ich aus dem egal ob wir das so schreibt
oder ob ihr löscht die mir sagt ihr löscht den knoten nach einem bestimmten knoten das aushängen funktioniert sie genau spiegelverkehrt wie das einfügen macht das einfach mal mit papier und stift und schreibt euch dann dazu und co ihr könnt natürlich jederzeit vergleichen mit den beispielen die ich euch mit geht das muss man auf den folien gesehen haben ist ein ausschnitt davon aber es ist tatsächlich eins zu eins der quote nicht verwendet um die klassen ist und die liszt zu implementieren so wenn man stil ist jetzt abschließen anschauen wir haben immer noch linearen aufwand um die
anzahl einträge in der liste zu zählen wir könnten auch attribut spendieren dass die anzahl einträge zählt und jedes mal wenn ich einen einfügt oder einen lösch den zähler mit den orten bringt dann hätten wir hier auch von 1 stehen um den preis dass man bisschen mehr aufwand haben bisschen mehr buch führen müssen ein attribut mehr haben front und back gehen jetzt beide in konstanter zeit ich muss einfach nur nett und taylor auswerten vorsichtig muss auch immer die vorbedingung überprüfen dass die liste nicht leer sein darf ist immer noch wenn ja muss mich durch die ganze
liste hangeln muss front und geschmack sind jetzt in konstanter zeit möglich in satt und arrays an der bestimmten position an der ersten position sind in ja weil ich dort hinkommen muss front und push back sind jetzt beide und von 1 möglich alles was wir gemacht haben zum einfügen und zum löschen machen würden ist umsetzen der entsprechenden referenzen wie gesagt wenn was es auszeichnet dann ist es ganz leicht wenn man es programmiert ist die schwierigkeit manchmal dass man sich in der reihenfolge nicht thun da und sofern auch das brauchten die übung zeichnet euch tatsächlich die einzelnen
schritte auf und stellt sicher dass genau das passiert was ihr wollt das passiert wir haben immer wieder sonderfälle nämlich wenn sich das erste und das letzte element ändern oder wenn ein erstes und ein letztes element entstehen weil die liste vorher leer war dann muss ich auch die referenz head und thailänderin eine ganz elegante lösung wie man um diese sonderfälle rumkommt findet ihr in der implementierung im hoch und sagt sattler die speichern in der liste nicht referenzen head & taylor auf den ersten und letzten knoten sondern dort sind head und tel tatsächlich selber knoten die allerdings
nicht mitgezählt werden das hat den großen vorteil da habe ich den knoten also die entsprechende note datenstruktur die ist da ein hemmnis immer daran taylor war auch in der liste ich zähle nur die knoten die zwischen head und tail eingehängt werden aber dadurch dass beide immer als datenstruktur da sind kann ich auch immer ein und aus gingen ohne dass ich einen sonderfall betrachten muss der preis den ich zahlen ist das meine datenstruktur jetzt nicht nur zwei referenzen hat und erhält sondern tatsächlich zwei komplette knoten halten muss das ist aber nicht weiter schlimm aber alle objekte
mit hilfe von der referenz gespeichert werden in c++ täte uns dass gegebenenfalls mehr wie wenn so ein knoten eine größere nutzlast hat dann habe ich zwei nutzlasten noch mit dabei in meiner liste effektiv ex bringen und auch ein paar andere implementierungs problem in java habe ich das alles nicht dass es tatsächlich eine sehr schöne und sehr elegante lösung schaut euch einfach mal an damit sind wir fertig mit diesem zweiten kapitel und schauen uns nächsten kapitel literaturen anmachen den kurzen ausflug zu den java collections und werden der ganze vorlesens kapitel abschließen damit dass wir den vektor
und die erste ist die liszt verwenden um ein stack bzw eine kuh zu implementieren