zum abschluss des ersten kapitels zu listen schauen wir uns noch zwei datenstrukturen an die wir als abstrakte datentypen aus dem wintersemester können und zwar ist dass der stuck und die kuh beide kennen wir schon was ist ein stack einen stack ist eine datenstruktur die im wesentlichen zwei operationen bietet um den stack zu verändern zu manipulieren mit push kann ich etwas oben drauf legen mit pop kann ich es von oben wieder runternehmen gleichzeitig kann ich das oberste element und nur dieses vom stack jederzeit erfragen dazu muss es natürlich ein oberstes element auch geben das wiederum kann
ich abfragen in dem ich frage ob das tech leer ist oder nicht das im wesentlichen der adt stack mit den operationen wie wir sie uns im winter auch angesehen haben was wir aus dem wintersemester auch schon wissen ist dass wir den stack implementieren können wenn wir eine implementierung eine liste an ich nehme hier die esslust pusch entspricht der operation prompt pop entspricht der operation pop front top entspricht der front und ist im titel kriegen geschenkt warum habe ich pushe und und pop band gewählt und nicht pusch berg kommt ob beck weil ich natürlich die operation
wähle die am billigsten sind die in ofen 1 in konstanter zeit möglich sind ich kann den stack aber auch mit hilfe von rektorin implementieren dann würde ich für push natürlich buschbeck für pop pop beck wählen das wahr ist auch wieder die operationen die amortisiert in konstanter zeit möglich sind ihr könnt natürlich auch die doppelt verkettete liste nehmen dass wir in diesem fall aber zu viel des guten denn beim stack arbeit mehr tatsächlich immer nur an dem einen ende oberst auf und auch wieder runterkommt wir haben uns im letzten semester schon eine anwendung von dem stack
angeschaut da müsse man therme in umgekehrter polnische mutation gerechnet wir werden in den nächsten kapiteln viele anwendungen vom stack haben in der regel wird es darum gehen dass wir aggressive algorithmen interaktiv schreiben und den stack als eigentliches datenstruktur brauchen die andere datenstruktur ist die kuh da wo der stack nach dem prinzip was zuletzt reinkommt kommt zuerst wieder raus last in first out funktioniert so funktioniert die ju nach dem prinzip first in first out deswegen wird eine kuh oft auch als fifa datenstruktur oder kurz einfach tief bezeichnet sowie beim stack gibt es auch hier zwei operationen
die die crew manipulieren ich kann etwas hinten rein geben hinten anstellen und ich kann etwas vorne wieder rausnehmen ich nenne die operationen hier ein crew und die crew für den stacks begriffe pushen pop immer gesetzt bei der kuh ist es oft je nach implementierung anders entdecken meines erachtens die generischen begriffe die wir hier verwenden können so beim stack kann man es keine implementierung angeschaut weil mir gesagt hat wir müssen im prinzip nur eine datenstruktur implementieren die einfach alle aufrufe der entsprechenden methoden push pop weiterreicht an die aufrufe von ds lässt bzw vom dem vector bei
der crew wird so kleines bisschen komplizierter beziehungsweise kleines bisschen interessanter wir schauen uns zwei möglichkeiten an die crew zu implementieren und zwar einmal doppelt verketteten liste das wird recht einfach gehen und zum zweiten das ist auch nicht wirklich schwer aber neu die idee mit hilfe von einem ring kupfer das heißt mit hilfe von einem feld und dann immer wieder unseren weckt oder wie können wir jetzt eine kuh mit hilfe von einer doppelt verketteten liste implementieren bei einer doppelt verketteten liste kann ich an beiden enden vorne wie hinten manipulieren ich kann jeweils vorne wie hinten in
konstanter zeit aus einfügen und etwas rausnehmen genau das müssen wir bei der em auch machen hinten anfügen von rausnehmen dementsprechend implementieren wir die kuh ich nenn secude dl das dl steht verdoppelt verkehrte liste oder so landers deal ist erinnern diese view erweitert erstmal einen abstrakten datentyp cju das heißt wer dann zwei verschiedene implementierungen für diesen abstrakten datentypen haben einmal mit hilfe der doppelt verketteten liste und gleich noch mit hilfe von dem feld diese kuh ist recht einfach gestrickt die eigentliche da eigentlichen daten werden in der doppelt verketteten liste welche data gehalten die ist bei konstruktion
der coole der akku leer dann haben wir die entsprechenden methoden ist ente und front die einmal abfragen ob die cholera ist geben die abfrage einfach an die liste weiter die den ersten eintrag der lüste zurückgeben in dem fall ist es so auch das wird man aus dem wintersemester für frontmann keine vorbedingungen die steht ist in der liste im prinzip auch schon implementiert die steht auch bei front schon ich schreibe hier explizit nochmal und wählt ein klein bisschen andere exception oder wer eine andere exception in dem fall ist geschmackssache aber dass die fehlerbehandlung in der liste
macht oder etwas er explizit noch mal hier in der kino macht wichtig ist front hat eine vorbedingung ich muss prüfen ob die liste leer ist oder nicht jetzt kommen wir zu den operationen auf der liste ich geb gas in die uhr ein mit alkohol was raus mit die q in q ist ganz einfach das ruft einfach prospekt auf also ich reich meinen eintrag einfach weiter an die liste und für den hinten an die kuh wieder genau die gleiche situation wie eben hat eine vorbedingung und secude darf nicht leer sein auch hier prüft muss explizit in
der kuh ab und werfen entsprechend exception auf anders als bei der liste möchte ich hier ein datum tatsächlich zurückgeben das heißt ich merke mir einmal den ersten eintrag und danach nehme ich den ersten eintrag raus aus der kuh und gibt das was ich mir gemerkt habe zurück was es hier anders hauptfront für die liste war so implementiert dass es nichts zurück gibt die kuh ist so implementiert das etwas zurückgibt ist in dem fall sinnvoll weil in der regel wenn ich etwas rausnehmen aus der kuh möchte ich diesen eintrag den ich rausnehmen auch sofort haben und
verwenden können damit hat noch unsere crew auch schon implementiert das war recht einfach mit der doppelt verketteten liste wir delegieren einfach unsere methoden aufrufe von der kuh an die die listen sind fertig tatsächlich ist es aber so dass wir das ganze auch mit einer einfach verketteten liste machen könnten wir brauchen eine doppelte verkettung allerdings nicht mit unserer es ist so wie sie gerade ist es reicht der einfache verkettung bevor es weitergeht überlegt mal was du machen müsstest wie du es liszt verändern müsstest so dass man damit auch eine kuh implementieren könnte beziehungsweise wie meine crew
mit hilfe von der einfachen verkettung implementieren kann so sieht unsere einfach verkettete liste aus wie wir sie bisher haben das problem ist wir müssen für die kuh an beiden enden arbeiten können manipulieren können das geht mit der einfach verketteten ist nicht wollen wir eben nur den einstiegspunkt hätte haben das lässt sich aber leicht ändern indem wir einfach zwei das attribut tale noch mit einführen genau wie bei der deal ist aber ohne dass wir jetzt eine doppelte verkettung der rückwärts verkettung noch machen sondern wir merken uns einfach immer was der letzte eintrag in unserer liste ist
wenn man das machen dann ist es sehr einfach so was wie push back zu implementieren was muss ich dann machen buschbeck würde einfach vom letzten knoten ausgehen also von dem hier neun knoten konstruieren das ist der den ich einfügen möchte so da ich weiß was der letzte knoten hätte ich jetzt einfach dessen next referenz auf den neuen knoten und der neue knoten hat keinen nachfolger das heißt ich habe hier einfach nur referenz so diese referenz verschwindet und was sich schließlich machen muss ist ich habe neun knoten eingefügt und damit weiß ich dass ich auch ein
teil verändert hat ich muss einfach die täler referenz umsätzen fertig bis hin zu wählen jetzt fertig das heißt wir haben jetzt eine zusätzliche methode buschbeck die auch in ufa mainz möglich ist wir haben sowieso schon prompt vom 1 und damit sind wir im prinzip fertig puff beck ist jetzt einfach das neue andrew und pop fand ist entsprechend dass die kuh also wenn ich die einfach verkettete liste so erweitere da sich immer auch den letzten eintrag kennen dann kann ich mit einer einschränkung auch am hinteren ende was machen ich kann nämlich am hinteren ende das einhängen
ich kann nicht den letzten knoten wegnehmen dazu müsste ich ja den kennen da brauche ich eine doppelte verkettung zu aber ich kann hinaus einhängen und vorne kann ich sowohl ein als auch aushänge in dem fall werde ich das natürlich so wie es für die crew brauche hinten wird eingefügt vorne wird weggenommen und ich habe entsprechend gerade heben eine kuh wo die leute oder die einträge durchmarschieren jetzt schauen wir uns noch die zweite möglichkeit an wie man eine kuh implementieren kann und wir verwenden dafür in so genannten ring puffer oft auch sehr clever wann immer ich
den ausdruck puffer oder buffer verwende ist damit in der regel ein feld mit einer festen vorgegebenen länge gemeint immer mal an dieses feld hat die länge dieses geld soll jetzt die daten aus unserer crew aufnehmen dabei soll gelten dass wir zwei indizes hätten ähnlich dem staat und dem ende von einer kuh verwenden nur bezeichnen diese indiz ist jetzt die position des ersten eintrags head und die position dass letzten eintrag stale stimmt nicht ganz sondern tales oder index nach dem ersten eintrag sein also ein später spricht er für die position sein wo als nächstes eingefügt wird
head ist die position wo als nächstes was rausgenommen wird aus der kuh also die idee ist dass unsere crew von taylor nach head läuft weiter vorne sind die einträge die früher drinnen waren weiter hinten kamen einträge dazu also bei hat nämlich raus bei tale füge ich ein dabei würde ich beim einfügen den index tale immer um 1 zu erhöhen und beim herausnehmen aus der crew bei der crew den index hat immer um 1 erhöhen also hier höhe jeweils die indizes immer um eins naja wenn ich das macht immer um eins erhöhe irgendwann laufe ich aus
meinem heraus was man deshalb jetzt machen ist wir betrachten die indizes alle module deswegen ring puffer der ring schließt sich jetzt wieder wo ich rechts raus lauf laufe ich links wieder weint nun 1 2 3 4 5 6 7 und so weiter und so fort ich habe das hier einfach noch mal aufgemacht also wir haben hier fällt ein puffer der länge 4 mit indizes 01 23 wenn ich jetzt weiter zählt 45 67 und links wieder ein lauf würde das bedeuten 45 67 acht neun zehn elf und so weiter und so fort die vier wird wieder
auf die null die von ihr auch die einst die sechs auf die zwei die sieben auf die drei die acht auf die nullen usw abgebildet ich mache alle berechnungen hier modul 4 das heißt ich bekomme immer indizes zwischen null und drei hätten tale werden jetzt tatsächlich immer um 1 erhöht aber eben module module der länge des rs wir können uns das auch so vorstellen wir haben hier eine raiders potenziell beliebig groß werden darf und fügen da ein also bauen daraus eine kuh mit head und tail als indizes und wenn man das machen kapiere kyu das
sind drei elemente drin jetzt nehme ich zwei raus und fügt wieder eins an dann würde head um zwei erhöht teil um 1 erhöht die beiden sind jetzt belegt da nehme ich eins raus hätte um 1 erhöht führt wieder eins und noch eins an teil um zwei erhöht und so weiter und so fort hier würde ich einfach immer weiter nach rechts laufen das geht natürlich nicht weil meine würde einfach immer größer und größer irgendwann geht mir einfach der speicher aus wenn ich das ganze modell 4 mach dann sieht das entsprechend so aus wo ich irgendwann links
raus lauf hier noch nicht hier habe ich tatsächlich genau vier einträge hier passiert jetzt da laufe ich einfach auf der anderen seite wieder rein und so weiter und so fort also da wo ich hier die indizes 0 1 2 3 4 5 6 7 hat habe ich jetzt in die zimmer von 0 bis 3 also die vier wieder auf die null die fünf wieder auf die eins die sechs wieder auf die zwei die sieben wieder auf die 3 das heißt zum beispiel hier was hier am index 5 liegt haben wir hier wieder index 1 es
gibt natürlich ein problem an der sache hier links gehen wir davon aus dass wir beliebig viel speicher haben rechts gehen wir davon aus dass wir model of fear rechnen das heißt es kann einem überlauf geben also unser club hat eine gewisse kapazität und mehr geht nicht es passen hier höchstens vier beziehungsweise so wie wir es implementieren höchstens drei einträge rein wir müssen also entweder vorher wissen wie groß und secure maximal werden darf oder wir müssen ein sonderfall behandeln wenn es einen überlauf gibt und dafür sorgen dass wir mehr speicher zur verfügung kriegen hier ist das
beispiel noch mal model 4 diesmal mit head um taylor ich schreibe diesmal keine indiz ist als zahlen sondern der index auf den head zeigt den markiere ich mit dem punkt der index auf den teil zeigt den markiere ich mit einem stern am anfang sind beide gleich null und die konvention ist das unserem profil er ist genau dann wenn head und tail gleich sind all das ist gleichzeitig schon eine implementierung für mtu oder smt ist einfach nur ein vergleich hat und tail wenn die gleich sind ist die kuh leer so jetzt fangen wir an in die
kuh einzufügen also jetzt kommt eine 1 betragen was passiert die einst wird eingefügt an der stelle auf die teil gerade zeigt danach wird teil um 1 erhöht so entsteht eine eins in unserer gut an wir geben noch mal was ein der 2 die zwei wird eingefügt an der stelle wo teil steht und teil wird um 1 erhöht also immer da oder stern drin ist das ist der index auf den titel bezeichnet dort schreibe ich mein datum rein danach schiebe ich den index um 1 weiter kommt noch mit drei dazu genau das gleiche spiel und jetzt
nehme ich das erste mal was raus raus nehmen bedeutet die crew schaut was steht an dem index auf den head zeigt und dieser eintrag wird zurückgegeben ich habe zu ihr leeres feld stehen die einst wird nicht nicht irgendwie gelöscht sondern die kann da auch stehen bleiben auf jeden fall sie wird zurückgegeben und ist nicht mehr bestandteil der crew was immer hier stehen bleibt ist nicht mehr bestandteil der kuh alles was in der kuh ist ist zwischen head und tail ausschließlich so dass kann weitermachen wir können noch mal was raus nehmen aus der cube gleiche spiel
an der position von head steht mit 2 die zwei geht man zurück danach wird head um 1 weiter geschoben also der kreis bezeichnet immer den ersten eintrag in der kuh also der der als nächstes rauskommt der der schon als längstes wartet jetzt gehen wir das rein in die q4 die vier wird eingefügt an der position oder stern steht also auf die tale zeigt danach wird teil um 1 weiter geschoben aber eben jetzt model of fear das heißt links raus und rechts wieder rein genau hier sehen wir den effekt von otto 4 gut es gibt eine
5 dazu auch wieder einzige position ist da oder stern steht da steht jetzt die fünf danach wird teil um 1 weiter gerückt das heißt der stern wandert 1 weiter nach rechts wenn wir jetzt was rausholen dann schauen wir wo steht der kreis dass es hätt da steht mit drei die liefer zurück danach erhöhen wir hat um 1 und so kann man das spiel immer weitertreiben wichtig dabei ist wir haben die konvention dass der puffer genau dann leer ist wenn head gleich tail ist das war hier der fall das bedeutet es ist nicht nur ein überlauf
möglich nämlich dann wenn wir versuchen mehr als vier einträge in dem puffer unterzubringen sondern diese überlauf passiert schon 1 vorher immer nach dem dritten element das vierte mit einfügen stellen wir uns vor diese zeile hier stellen wir uns vor wir versuchen hier jetzt noch einen weiteren eintrag mit einzufügen dann würde mir das ixs hier an der stelle einfügen oder stern steht da ist tail und danach würde mattei um 1 verschieben model auf 4 also hier her und jetzt haben aber ein problem weil nach dem was wir gerade eben gesagt haben es hat gleich tale gleichbedeutend
mit profis leer hier am abend gleich tail und profis voll und das darf natürlich nicht sein das widerspricht sich das heißt wir haben in diesem puffer der größe m platz für in -1 einträge wenn man die konvention so machen und ich finde sie ganz vernünftig das so zu machen wir vermeiden einfach sonderfälle also es kann im überlauf geben um diese überlauf passiert immer dann wenn ich hätte gleich taylor habe unmittelbar nach dem ende das heißt wenn ich versuche das ente element einzufügen schauen uns eine mögliche implementierung an die findet ihr wie alles in den beispiel
auch hier und secure erweitert den abstrakten datentypen auch der ist bestandteil der beispiel das ist meine kuh ich habe hier keinem so fix wie gerade eben die eltern das wird die crew sein die wir die meiste zeit benutzen ich finde die ring puffer variante oft die sinnvollste und oft auch die performanz erste variante sowas haben wir haben einmal data ich habe vorhin gesagt wir können unseren std vector nehmen ich mache hier trotzdem noch mal zu fuß und dem tatsächlichen eric sowie was gerade gesagt haben umfeld feste länge im puffer und zwei indizes hat und ich
konstruiere eine kuh in dem ich eine kapazität vor gibt also kappa city entspricht der maximalen anzahl von einträgen interview das was man gerade mit n bezeichnet haben und am anfang sei nett und tail jeweils gleich null essent ist einfach wir vergleichen einfach head mit themen die us genau dann leer wenn hätte gleich telis front ist auch reicht das ist einfach das was an der position head steht das einzige was jetzt dazu kommt es wir haben eine vorbedingung front kann ich nur ausführen wenn die kuh nicht leer ist wo diese vorbedingung prüfe ich wenn sie nicht
erfüllt es wird der ausnahme aufgeworfen als auch hier hält zeigt auf den ersten eintrag teil zeigt auf den eintrag nach dem letzten eintrag so dass ich wann immer ich was aus der kuh herausnehme auch wieder prüft ob sie nicht danach mir den eintrag nehme der an der stelle entsteht das war gerade immer das kästchen mit dem kreis drin ich habe gesagt die ich mach die kästchen leer das muss ich nicht unbedingt machen in java mag es tatsächlich sinnvoll seien jetzt hier den eintrag mit 0 zu überschreiben und im garten collector eine chance zu geben alles
was da drin war und vielleicht nicht mehr gebraucht wird tatsächlich auch zu löschen es wird erstmal noch gebraucht weil ich es zurück gehen habe ich möchte nicht gegeben weil es nicht dass es in der crew bestehen bleibt so und danach zähle ich hätt um eins drauf das ganze aber model jo en bzw lothar größe der länge eines puffers und ich gebe schließlich den eintrag den ich mir gemerkt habe zurück jetzt müssen wir noch was in unserem kino einstellen können mit 1 q der neue eintrag ex der wirt abgelegt an der stelle auf die sail zeigt
danach teil um 1 erhöht modul unsere puffer länge allerdings müssen wir noch prüfen ob es den überlauf gibt den überlauf gibt es genau dann wenn dieser wert hier auf den virtuell weiter schieben würden gleich den head ist deswegen berechne ich mir die neue position teil zuerst aus ob diese neue position aufhält zu liegen kommt wenn nein gibt es keine überlauf dann füge ich einfach ein und zählte weiter indem ich auf die neu berechnete position sind ansonsten gibt es den überlauf und ich muss irgendwie damit umgehen es gibt verschiedene möglichkeiten an vielleicht ist die naheliegendste tatsächlich
zu sagen ich gebe den fehler aus beziehungsweise werfen eine ausnahme auf die andere möglichkeit ist ich vergrößere den puffer so wie es ihr vorschlag dabei gehe ich einfach einen neuen profi kopier die alten werte in den neuen puffer vorsieht muss mit der reihenfolge aufpassen und schau gegebenenfalls dass dieser neue profi groß genug ist dass man vielleicht auch wieder ein exponentielles wachstum haben ähnlich wie bei unserem sektor also das ist das was ich hier vorschlag das kann sinnvoll sein muss nicht immer sinnvoll sein es gibt noch eine andere möglichkeit news werden oft verwendet wenn prozesse miteinander
kommunizieren wobei jeder prozess unabhängig von dem anderen arbeitet das heißt die können dinge parallel ausführen und dann wird so sein dass wenn jemand versucht was in chur einzugeben um dann gleich weiterzumachen und jemand anders soll aus dieser kuh was raus nehmen um damit was zu machen dann sollte man einfach dafür dass derjenige der was rein gibt aber die kuh ist voll so lange blockiert bis wieder jemand was auf der anderen seite aus der kinos nicht das interessiert uns hier nicht weil wir uns parallele verarbeitung nicht anschauen aber uci vor spikes wie immer ich es nennen
werden eben oft auch als kommunikationsmittel benutzt und dann ist genau so ein verhalten sinnvoll und insbesondere ist es dann in der regel fast immer so dass diese kuh dieser fifa als einkäufer heißt ein ring puffer implementiert ist damit sind wir fast fertig mit diesem ersten kapitel zu listen bevor wir zusammen fassen noch ein paar bemerkungen was ist denn jetzt die bessere implementierung der verkettete liste oder 1 fällt die antwort ist tatsächlich nicht ganz einfach insbesondere weil der sympathische aufwand natürlich eine sehr grobe abschätzung ist und in der praxis nur sehr bedingt aussagekräftig im zweifel mit
der stoppuhr hinsetzen beziehungsweise bisschen eleganter sich eine stoppuhr programmieren und nachmessen ein paar dinge kann man sich aber immer noch leicht vorstellen wenn man rays und listen miteinander vergleichen dann punkten in der regel die airways warum hier liegt alles kompakt im speicher und ich brauch keine zusatzinformation die mir die verkettung darstellt bzw die mir sagt wie von einem zum nächsten kommen ich muss ja einfach nur den index anzeiger oder was auch immer weiter schieben erhöhen ich muss einfach eine addition durchführen und danach noch mal ein speicher zu krismer bei listen das ist immer ein bisschen
komplizierter weil die knoten haben halt einmal die nur lasst das was ich tatsächlich speichern will also das was hier in jeder zelle drin steht aber ich brauche eben noch zusatzinformationen für die verkettung hallo ich habe in der regel mehr speicher den ich brauche um eine liste darzustellen außerdem da wo ich in einem harry einfach nur satire und zum nächsten zum nächsten zu kommen muss ich bei der liste immer speicherzelle auslesen zum nächsten gehen speicherte auslesen und so weiter und so fort ich habe immer mehr speicher zugriffe und auf den heutigen rechnern zum speicherzugriff relativ teuer
berechnungen zum deutlich billiger als speicher zugriffe zumindest dann wenn dem datum nicht dort im speicher liegt wo ich es gerne hätte und dass es insbesondere dann der fall wenn meine daten nicht kompakt oder lokalem speicher liegen wie hier eine mary sondern vielleicht irgendwie über den speicher verstreut wie hier in der liste wo ich keine ahnung habe wo djavadi einzelnen knoten tatsächlich ablegt wer nachlesen gibt viel in der literatur beziehungsweise auch viele artikel ich habe einen von pianist rost hat das ist der erfinder von c++ rausgesucht der damals geschrieben hat zu listen und feldern und die
quintessenz ist in der regel seid ihr mit feldern mit race besser dran aber das ist nur eine ganz grobe daumenregel es kommt auf viele verschiedene dinge an insbesondere eben auch die konkrete situation was will ich eigentlich durchaus aber auch auf dem rechner mache ich das dieses speicherzugriff ist im teuer berechnungen sind billig das war vor 20 25 jahren noch anders auch die programmiersprache kann damit rein spielen in java stelle ich alles als ein referenz dar es kommen noch die prinzip primitiven datentypen dazu aber im prinzip ist jedes datum dass ich in java ableger ist mal
was relativ kleines in java habe ich sowieso immer solche in direktionen weil ich immer über referenzen geht das heißt auch in java würde ja tatsächlich so aussehen in c++ ist das nicht so das kann ich so machen nur sich nicht so machen und dementsprechend verhalten sich die implementierungen auch anders ich empfehle euch wenn möglich bei felder zu bleiben die sind einfacher und in der regel auch schneller bei gleicher symbolischen aufwand in der praxis in absoluter zeit schneller ihr müsst zwar ausprobieren allerdings spielen listen ihre stärken oft aus bei bestimmten operationen wo ich mich mit aris
wiederum sehr sehr schwer tut schauen wir uns ein beispiel an ich habe zwei listen l1 und l2 und wir stellen uns einfach mal vor dass ich diesen mittleren teil hier aus der liste l1 ausschneiden und in die liste l2 einfügen möchte so bei dem raid tape ich mich hier schwer ja ich hätte hier ich musste in 2 eine lücke schaffen im ersten eine lücke wieder schließen das heißt ich muss hin und her kopieren in der liste ist es ganz einfach ich muss nur wissen dass ich von diesem knoten weg bis zu diesem knoten hin ausschneiden
möchte und wie muss ich l1 ändern ich muss einfach diese referenz in diese referenz um ändern und ich muss schließlich den rest hier nehmen hier unten einzufügen so ganz sich nochmal eine referenz ändern nämlich ich wollte zwischen diesen beiden knoten einfügen naja jetzt frittieren referenz auf den hier und der nächste zudem hier ist der 1 und das schöne ist beide operationen des aushängen wie das einhängen gehen in konstanter zeit in opern 1 völlig egal wie viele einträge hier zwischen den listen verschoben habe in owen einst geht das wenn ich genau weiß an welcher position ich
jeweils schneiden und einfügen muss und das krieg ich mit rs so nicht hin also listen sind immer dann gut wenn ich ganze teile davon verschieben möchte noch eine andere bemerkung es gibt vielmehr datenstrukturen also wir uns hier in der vorlesung anschauen aber eine idee ist oft ganz wichtig es hindert uns niemand drin dran dinge miteinander zu verknüpfen also listen zu entwerfen deren knoten airways sind um so quasi bisschen was von den vorteilen von beiden abzugreifen also jetzt habe ich in jedem knoten nicht ein datum sondern mehrere stehen ich kann jetzt hier auch wieder was machen
dass die knoten dynamisch wachsen schrumpfen können bis zu einer vordefinierten maximalgröße und auf die art und weise habe ich so ein mix zwischen den eigenschaften von der liste und den eigenschaften von dem was heißt manchmal auch dekoder double endet crew weil ich mit sonaten struktur zum beispiel die crew auch sehr schön und sehr effizient implementieren könnte insbesondere dann wenn diese kuh auch sehr groß werden kann ich das aber vorher nicht weiß oder wenn meine kuh im lauf der zeit sehr stark wächst und schrumpft ich die daten aber möglichst kompakt halten möchte kurz bemerkung noch zu
java wenn ihr den beispielcode und damit auch den code auf den folien anschaut dass immer mal wieder eine hinweis auf den garbage collector oder dass ich irgendwas machen um den um dem garbage collector eine chance zu geben dinge freizugeben die speicherverwaltung und java ist grundsätzlich sehr einfach ich muss mir überhaupt keine gedanken drüber machen also sie ist damit vor allem einfacher als ein c c++ wo man alles explizit und zu fuß machen muss aber wir wissen ja der garbage collector überprüft ob ein objekt noch referenziert wird und nur wenn nicht hat eine chance dieses objekt
auch frei zu geben und nur wenn nicht wird das auch passieren wir haben keine garantie dass das passiert wir wissen nicht wann das passiert aber wir wissen es passt kann nicht passieren wenn irgendjemand eine referenz auf dem objekt hält die einfachste möglichkeit dafür zu sorgen dass es keine referenz mehr gibt ist dafür ist referenzen noch irgendwo rumliegen in einem knoten in einem harry explizit mit 0 zu überschreiben und das ist das was ich hier auch versuch konsequent zu machen wenn ich das nicht macht hat das erst bei keinen einfluss auf die korrektheit von dem programm
er stört mich oft nicht wenn da noch was drin steht aber es kann dafür sorgen dass ich unnötig viel speicher belege beziehungsweise grad nicht anderweitig verwenden kann also auch wenn ihr die speicherverwaltung und sarah geschenkt bekommt ist es durchaus sinnvoll sich zu überlegen wie man dem garbage collector ab und an bisschen unter die arme greifen kann eine ganz andere bemerkung noch weil das manchmal zu missverständnissen führt selbstverständlich kann ich in einem verein oder einer liste oder in emstek oder in der crew auch nullen oder 0 referenzen speichern das uns überhaupt gar kein problem und oft
auch sinnvoll sie irgendwie als markierungen zu verwenden bei der kuh macht man das oder können dass zb machen bei sogenannten breiten suche oder bei einem level oder börse von einem baum wenn man die verschiedenen ebenen oder die verschiedenen ringe in der breiten suche voneinander trennen wollen kommen noch drauf also hab keine angst vor der null referenz oft ist die böse für den gab es collector ist es eine chance zu sagen hier ist nichts mehr wir dürfen die aber tatsächlich auch wie normales dat und benutzen einfach nur um anzuzeigen hier ist grad nichts so und damit
beschließt man dieses erste kapitel zu listen also wir sequenzielle folgen von daten speichern und auf zählen wollen als ein abstraktes konzept als ein abstrakten datentyp wir haben konkrete implementierungen kennengelernt die einmal felder harris verwenden oder einfach bzw doppelt verkettete listen links auf englisch wir haben die traktoren kennengelernt die genau dieses durchlaufen auch nochmal abstrahieren die sich vor allem in java auch sehr schön verwenden lassen wir haben viele andere operationen angeschaut und uns überlegt was sie kosten haben ganz kurz auf die cover collections geschaut und hans stuck und crew mit hilfe von diesen listen datenstruktur mit
hilfe von feldern und verketteten listen implementiert ihr findet in der vorgeschlagenen literatur jeweils auch kapitel zu listen datenstruktur zum teil heißt die auch ein bisschen anders zum teil sind die auch ein bisschen anders implementiert ich würde euch insbesondere hinweisen auf die implementierung die im buch herunter sagt findet am da wird der trick durchexerziert das für die einfach und doppelt verketteten listen dass eine bzw auch das andere ende nicht einfach eine referenz sondern ein dummy knoten ist damit deshalb weil er nicht mitspielt das nicht bestandteil der liste das ist eine sehr elegante art und weise um
sich sonderfälle zu sparen sprich muss ich hätt um taylor tatsächlich verändern oder nicht ja muss ich natürlich aber es ist viel leichter wenn das ein knoten ist als wenn es eine referenz ist die außerhalb der liste liegt also das ist wirklich wert sich mal anzuschauen es hat auch nachteile aber es ist oft sehr elegant und sehr schön sorgt für ein fach sind gut als nächstes schauen wir uns bäume an das wird nicht viel komplizierter als wüssten wir verzweigen einfach ein bisschen mehr und da wo die liste immer nur in eine richtung geht lasst uns jetzt
zu dass ich dinge weiter verzweigen und dann schauen wir noch dass ich das entsprechend auf so dreht wie ein baum in der informatik maßmann freundin meistens von oben nach unten wachsen warum ich das hin gemalt habe das was man für die listen gemacht haben und was hier einfach war das können wir bei den bäumen gleich wieder brauchen das ist die verkettung die idee von der verkettung braucht man hier genauso wider und auch wenn ihr vielleicht einfach oder doppelt verkettete liste als datenstruktur selten noch mal selber implementieren müsst diese idee dinge wie listen miteinander zu verketten
die braucht ihr ständig und die ist so wichtig ihr müsst das auch selber machen und die müsste es auch können gut und damit sind wir fertig mit diesem ersten kapitel