herzlich willkommen zur vorlesung algorithmen und datenstrukturen im ersten kapitel beschäftigen wir uns mit listen sind sie einfache datenstruktur listet uns einfach eine folge von daten so dass jeder eintrag in der liste einen nachfolger hat spricht die einträge sind linear oder sequenziell hintereinander angeordnet von einem zum nächsten zum nächsten zum nächsten natürlich jeder eintragen nachfolger wird man es immer beim letzten angelangt und die liste ist zu ende was wollen mit den listen machen welche operationen wollen wir auch den listen anwenden wir wollen die einträge auf zellen oder durchlaufen das heißt auf zellen in der reihenfolge in
der sie in der liste stehen wäre das können dann können wir natürlich auch die liste durchsuchen ob ein bestimmter eintrag teil der liste ist holen und das ist genau die sequenzielle suche aus dem wintersemester wird und laufen einfach alle einträge der reihe nach und sind fertig wenn man den eintrag gefunden die man suchen beziehungsweise wissen eintrag ist nicht in der liste die suche erfolglos wenn man am ende der liste angelangt sind ohne den eintrag zu finden was jetzt neu ist wir wollen die listen auch noch manipulieren können das heißt wir wollen in die listen einträge
einfügen und löschen und zwar einmal an bestimmten positionen nämlich am anfang und am ende der liste aber nach möglichkeit auch einer beliebigen position das sind ganz unterschiedliche operationen je nachdem wo ich einfügen möchte mit unterschiedlichen kosten je nachdem welche datenstruktur wir verwenden werden um die liste tatsächlich zu implementieren was kann man mit so einer liste machen welche anwendungen gibt es da auf der einen seite können wir natürlich den abstrakt und daten titel ist die nach außen wintersemester kennen implementieren da hat man müsste rekord eve unterteilt oder konstruiert je nachdem welche richtung man das sieht in
dem er in het den ersten teil und tail den rest der liste unterschieden kann wir wollen hier insbesondere die datenstrukturen stack und crew mit hilfe von listen implementieren das wären am ende von diesem kapitel machen den stack und die crew kann mir auch im winter schon kennengelernt wie kommunisten implementieren wir haben grundsätzlich zwei möglichkeiten listen zu implementieren und zwar einmal können wie die listen alsfelder in java als er es sehen das können wir schon zumindest zum teil mit rsa schon gearbeitet oder wir können die listen als sogenannte verkettete listen oder linkliste implementieren das wird neu
in diesem kapitel wir wollen anfangen damit dass wir listen alsfelder implementieren das heißt wir nehmen uns ein und sagen dieses ergebnis jetzt eine liste schauen wir uns mal an wie das aussehen könnte hallo wir nehmen uns eine ring ich nenne das einfach data nachher folie auch so heißen einträgen diese einträge kann ich nummerieren von 0 bis 12 schavan die schöne eigenschaft als wie das perrey seine länge auch kennt das heißt die länge von diesen wird dann einfach weiter punkten sein so und im prinzip so wie jetzt schon fertig jetzt eine liste der schönheitsfehler an dieser
liste ist die hat eben genau in einträge endlich die n einträge in den ring und das irgendwie nicht so schön dass wir das halt machen ist wir führten zusätzliches attribut 1 anderseits sei es ist einfach nur ein integer und die idee ist wir wollen unterscheiden zwischen der länge des rx also diese men oder dienen das sagt uns wie viele einträge kann in diesem jahr den platz bzw welche kapazität hatten das race wie viel kann ich maximal drin unter und dementsprechend wollen wir dass gerade auch kapazität wo ich beim englischen city nennen also wir unterscheiden zwischen
der kapazität wie viele einträge haben den potenziell platz und der eigenschaft wie viele einträge habe ich den aktuell nr drinnen sah man dann hier die ersten drei einträge belegen dann wird man sagen sei es ist 3113 ist karsais einmal als größe das airways bzw länge unserer liste auffassen wir können aber auch sagen sei es zeigt auf den nächsten freien eintrag das heißt wenn wir jetzt hinten anfügen wollen in dem essay und unsere kapazität groß genug ist dann wird man einfach hier neuen eintrag rein machen und sei es um 1 erhöhen schon lange hinten eingefügt wunderbar
so das reicht uns natürlich noch nicht was uns hier fehlt ist dass die kapazität irgendwann erschöpft dass das heißt wir würden liste implementieren wir müssten uns vorher entscheiden wie groß darf denn diese liste werden und könnten dann immer wieder hinten ein fühlen was wir deshalb machen ist wir definieren und zusätzlich noch eine methode die nämlich ries 1 die mir die größe des arrays festlegt wenn ich hinten anflüge würde das heißt es wird immer um eins größer aber vielleicht wollen wir nicht nur hinten anfügen vielleicht wollen wir das einmal insgesamt vergrößern schabbat sondern pseudo quote mit
leichten park seien java dazwischen sowas soll resize machen resize soll das auf eine gewisse größe bringen das heißt sei es gleich entsetzen aber vorher muss man schauen ob wir tatsächlich platz für in einträge hand das heißt ob tatsächlich kleiner ist als kapazität in diesem fall setzen einfach sei es auch hin schreibt sie gerade extra ein bisschen umständlich ersten fall hier ansonsten ja muss manchmal ansonsten ansonsten muss man das bury vergrößern dafür machen es wir holen uns einfach neues von der größe die verbraucher dann kopieren wir die daten am ursprünglichen airdata industrie das würde hier bedeuten
wir kopieren nur die daten die wir tatsächlich drin stehen haben als in den palast drei so und danach sorgen wir dafür dass unser airdata auf den speicher zeigt den ort hier mit data zwei geholt also im prinzip genauso wie wir es uns in java denken nur dass ich jetzt keinen java code geschrieben und ganz am ende müssen wir natürlich uns auch wieder sagen dass das heißt sein sein ich habe gesagt dass ein bisschen umständlich tatsächlich können wir das ganze bisschen eleganter schreiben sei es gleich en gilt immer in beiden fällen in einem fall müsse man
was machen im anderen ich also wäre es gerade geschickter wenn wir geschrieben hätten ein kleiner kapazität dann und nur dann muss man vergrößert dass er größer ist das was hier steht das macht mir immer und egal ob der größe musste nicht danach setzt man auf das entsprechende m und aber jetzt kann man unseren eine beliebige größe zu ordnen wenn man jetzt tatsächlich mal überlegen wir wollen immer wieder hinten anfügen selling wir machen das mit einer funktion oder methode die nicht buschbeck dann möchte ich einfach ein eintrag iks hinten anfügen was mache ich dann ich mache
das perry um 1 größer und fügt den eintrag dann an der richtigen stelle an wo ist die richtige stelle die aktuelle größe sei es zeigt mir auf die stelle wo einfügen kann die merke ich mir einfach danach begrüße ich dass herr und jetzt schließlich sage ich dass der eintrag angestellte jedes gleich fix sein soll vorsicht resize ändert das attribut sei es deswegen musste ich mir das hier merken das ist quasi die alte größe und nachdem resize ausgeführt worden ist habe ich eine neue in dem fall um 1 größere länge des paris wenn man das jetzt
einmal machen und wir fangen mit einem lingen null an dann wären wir in der delling 1 dann die zwei der länge 3 und so weiter und zog ihren und dann sehen wir in jedem schritt jedes mal wenn man hier das einfügen haben wir ein resize wo wir tatsächlich in diese mast hier sind das heißt wir müssen jedes mal um kopieren im ersten schritt einen eintrag in 22 anträge im dritten drei einträge sprich wenn einträgen mit push back einfügen dann können wir leicht zählen dann haben wir kosten von wovon in quadrath 1234 25 wieder war unser
geschirr zum informel wir haben quadratischen aufwand das ist natürlich nicht schön deswegen versuche das ganze jetzt nochmal zu verbessern und zwar wir verabschieden uns davon dass resize dafür zuständig ist dass es zu vergrößern [Musik] sondern wir unterscheiden zwischen ries und eine methode ihnen hier und server was soll wie serv machen réserve schaut dass auf jeden fall genug kapazität da heißt also verändert die kapazität von unserem also wie viele einträge kann ich denn maximal speichern sprich wie das eis nicht ändern gut aber ich will ja immer noch meinte rey in der größe ändern können als wir
brauchen trotzdem die methode resize die short plus jetzt ein bisschen anders aus wie zwei sam soll was machen soll hinten entschuldigung platz in ihr schaffen also gegebenenfalls hinten was anhängen dazu brauchen wir auf jeden fall eine kapazität von händen also buch meint wir wissen auch weil wir das gemacht haben bist unser er kann auf jeden fall mindestens ein training erhalten und danach setzt mein fach sein fertig also was wir gemacht dann ist wir haben die methode resize verteilt eine methode wie sie die kapazität schafft und resize schließlich die dafür sorgt dass sei es auch wieder
geändert wird wenn man genau hinschauen dann habe eigentlich gar nichts verändert wir haben nur aus einer methode 2 gemacht wobei die erste die zweite aufruf und was hier fehlt wird hierbei resize schließlich machten und also wenn eigentlich noch nichts gewonnen gewinnen tut man jetzt dadurch dass wir hier beim reservieren nicht unbedingt ein einträge besser wir sondern dass wir hier statt entsagen wir wollen entweder n einträge aber mindestens und schreibe jetzt mal doppelt so viele wie wir bisher als kapazität haben so was ist der unterschied würden wir immer wieder mit push päckchen anhängen dann hätten wir
länge von 1 von 2 kontra eine länge von 4 sowie das vorher gemacht haben dann länge von 51 2 45 nach unserem alten china nach dem neuen schema hätten eine länge von 1 jetzt verdoppeln wir haben die länge von 24 verdoppelt haben die länge von 4 wir verdoppeln unsere ringe von 8 und so weiter sprich unser harry wächst jetzt exponentiell in der länge in der kapazität aber wir wissen schon exponentielles wachstum ist meistens was was man nicht haben wollen weil das sind sehr schnelles wachstum das in dem fall hilft uns aber dieses exponentielle wachstum von
unserem warum schauen wir uns das bild von gerade eben noch mal an also wollen insgesamt einmal buschbeck einfügen also einmal hinten was an sary anhängen und wir fangen an mit dem herr der ringe 1 um einen eintrag eingefügt für die nächsten eintrag verdoppeln wird die größte jetzt haben wir zwei einträge also insgesamt 2 1 geübt beim dritten eintrag müssen wir wieder verdoppeln jetzt haben die kapazität von 4 und können jetzt hier den dritten und den vierten eintrag einfügen wenn man den fünften eintrag einfügen wollen verdoppeln wir wieder jetzt haben eine länge von 8 kapazität von
8 und wir können die einträge 5678 einführen und so weiter und so fort also was ich hier gezählt habe auf der linken seite das war die kapazität was ich hier auf der rechten seite gezählt habe das sind die kooperationen als eine 2 3 4 5 6 7 8 8 x buschbeck aber wir haben nur eins zwei drei vier mal speicher holen müssen und wenn man beim ersten mal sagen das hat man schon und sowie holt dann aber von hier nach da am 1 nach 2 von 2 nach vier von vier nach 8 und kopieren müssen
aber dazwischen nicht noch mal ein zwischenschritt wenn jetzt hier auch nochmal ein fügen wollten den 19.11 zwölfter eintrag und so weiter dann haben wir jetzt verriet mit 16 einträgen und hier könnten die einträge 9 10 bis 16 unterbringen das heißt wir haben nochmal acht bush becks machen können ohne dass irgendetwas um kopiert wird also immer nur von hier nach da von hier nach da und je nach da von hier nach da wird neuer speicher geholt und kopiert das kopieren tut uns weh weil beim kopieren muss man durch alle einträge die wir schon in der liste
haben durch und sein die neue liste einschreiben schauen wir uns das noch mal ein bisschen genauer an und ist man rechnen danach sagt mir wir haben einträge die wir in unseren every speichern wollen zum beispiel in den wald buschbeck machen der einfachheit halber schreibt mir mal das ende zweier potenzieller klein erst zwei hoch großen welchem aufwand haben wir wenn man tatsächlich annehmen dass wir einmal lospech aufrufen wollen naja wir müssen auf jeden fall einmal was machen das heißt jedes dieser putsch becks ist mir auf und geh gleich eins bis es aber bestimmte kosten um den
eintrag überhaupt ins einzustellen vorausgesetzt wir haben genug kapazität wir nennen diese kosten einfach mal 10.000 dessen konstante ich habe die summe geschrieben weil die summe ist ja im prinzip so wie wir uns das hier denken einmal buschbeck in der schleife tatsächlich ist der ausdruck natürlich ganz einfach wenn ich einmal über eine konstante summiert dann ist das nichts anderes wie 10 0 x jetzt kommen aber noch die kosten dazu für das vergrößern und umkopieren also für das was in der wismut passiert wie serv erinnern uns dies hat nur dann arbeit wenn die kapazität zu niedriges das
heißt einmal in riesa in buschbeck resize und den resize wie serv aufrufen dann machen die meist dann waren viele aufrufe gar nix wir dann sehen was das die meisten sind weil wir genug kapazität haben immer nur wenn man's kapazität fehlt dann passiert tatsächlich was man jetzt müssen wir schauen wie oft passiert dass jedes mal dann wenn unsere kapazität erschöpft dass wenn man zur nächsten zweier potenz gehen wenn man die kapazität verdoppeln müssen jetzt um ihren auch hier wieder auf von gleich null an dem talent racing warum bis ja und jetzt bis groß en warum gleich
zwei hoch großen das heißt 2 x 2 x 2 und so weiter also haben wir das verdoppeln genau drin wie oft müssen verdoppeln naja wenn entlein in zwei hoch großen ist was mit gross einmal verdoppeln wir fangen bei 20 bei einem eingang an und wenn uns jedes mal verdoppeln auch wieder eine konstante mal die anzahl einträge die wir kopieren müssen kostet dann sind das die konstante c1 mal wie viele einträge nuzman kopieren na ja in der ersten stufe sind das zwei mal zwei mal zwei und das im alter zwei hoch nie gut schau mal was
hier steht das sind sie eins mal gleich 0 2 hoch 01 2010 21 24 plus und so weiter bis zwei hoch großen viele einträge so eine summe aber vielleicht schon ein bisschen 1bis 2j 480 16 und so weiter +2 hoch angeschlossen angeben als zwei hoch 1 1 - 1 wer nachlesen will geometrische reihen so wir haben hier stehen ist gleich 10 09 m plus 1mal 2 hoch und plus1 ich ziehe eine 2 aus 2 x 2 21 wieder abziehen ist gleich mit 60 100 x 11 x 2 x 22 c 1 x 2 hoch großen
es wieder kleinen minus si 1 x 1 und jetzt immer eigentlich fertig weil was wir hier sehen ist das kommt ihr linear fuhr das heißt das ganze ist das können wir aus dem wintersemester [Musik] also fasst noch einmal zusammen mit push back kostet uns ein aufwand von o von n wenn wir beim reservieren immer wieder die kapazität verdoppeln oder wenn wir beim reservieren dafür sorgen dass unser in der kapazität exponentiell schnell wächst das heißt dieses exponentielle wachstum ist hier gar nicht schlimm warum wir wachsen ja gar nicht so oft hören wann hammer genug speicher und
jetzt machen wir noch einen anderen trick wenn uns einmal push back i know von n gelingt was sind dann die kosten für einmal buschbeck na ja das wäre dann einfach hoch von in geteilt durch andy aufpassen wie ich das hier schreibe ich setze lieber noch mal an von n geteilt durch n und das im insgesamt kosten von 1 oder konstante kosten sprich wenn wir so implementieren wir uns ausgedacht haben das wächst exponentiell in der welt in der länge dann hat diese push back operation immer wieder hinten was anhängen im schnitt kosten von o von 1
und das ist nicht nur so dass das sind schnitt ist sondern wir können garantieren dass das im schnitt konstante kosten sind was man uns angeschaut haben ist was passiert für einmal einfügen dann daraus einfach den durchschnitt genommen das heißt auch wir haben die sogenannten amortisierten kosten oder den amortisierten aufwand von push back berechnet es ist natürlich trotzdem noch eine art mittel amortisiert bedeutet hier fast alle aufrufe von push back gehen konstanter zeit also da passiert nicht mehr als das hier aber einige brauchen trotzdem länger da muss ich kopieren aber das sind eben nicht viel das
passiert immer nur wenn wir verdoppeln müssen und das wird passiert nicht besonders oft deswegen sind die amortisierten kosten schließlich niedrig und konstant aufpassen müssen wir das war trotzdem weil wir uns nicht darauf verlassen können nämlich genau mit zellen kann es natürlich immer passieren dass ein coach beck mal deutlich länger braucht einige eben diesem aufwand tatsächlich durchexerzieren müssen das soll die grundidee von unseren listen alsfelder sein und jetzt schauen wir uns das ganze nochmal auf den folien an was wir machen wollen ist wir wollen eine klasse vector implementieren und den namen habe ich angelehnt an die
klasse std vector aus der siedlung standard bibliothek in japan gibt es was ähnliches dort ist der begriff üblicherweise rail ist es ist aber tatsächlich das gleiche wir speichern in unserer klasse verschiedene attribute einmal die daten selber so wie gerade auch die kapazität des feldes die muss man aber nicht speichern das ist einfach nur die länge und settings aber wir speichern uns als attribut die tatsächliche größe der liste also wie wie der einträge habe ich denn gerade drinnen gespeichert welche operationen wollen wir haben gerade eben haben wir nun über push back gesprochen hinten anfügen wir haben
uns zwei hilfs methoden noch konstruiert resize vergrößern für buschbeck aber immer um eins vergrößert und resize hat wieder die surf aufgerufen gerufen und kapazität zu schaffen also diese drei kennen wir schon machen wir da weiter wo es einfach ist wenn man push back machen dann können auch ob beck machen also den letzten eintrag wieder löschen und was jetzt noch dazukommt ist wir wollen eintrag einer beliebigen position auch einfügen können mit hilfe von inside am index- und wir wollen auch einer beliebigen position index löschen können und schließlich wir wollen auch einen beliebigen eintrag in eine andere
position zugreifen können wir werden für alle listen datenstrukturen diese operationen und noch ein paar mehr implementieren einige davon zum beispiel sind explizit auf das re zugeschnitten wir werden sehen die machen zum beispiel für die verkettete liste so nicht unbedingt sinn alles was ich gerade aufgeschrieben habe schauen wir uns jetzt als java code wenigstens kurz an alles was sie auf den folien seht sind ausschnitte aus dem beispielcode als ihr könnt euch einfach den beispiel code anschauen und hat er die komplette klasse es ist eins zu eins dieser ausschnitt also wir implementieren die klasse vector die soll
einträge vom typ t oder der klasse b speichern da hier schon kleinen vorgriff die soll interface treppe implementieren zu den literaturen kommen noch wir haben ein attribut data und werden attribut sei es nicht wundern ich verwende ihr zyklus konvention hier nicht java konvention alle attribute die privat sind den verpassten unterstrich am ende einfach nur um klarzustellen dass es privat das sieht außen niemand wir fangen an mit dem leeren errang halte ich es überhaupt keinen speicher hinterlegt einfach die neue referenz dann haben wir auch tatsächlich sei es gleich null das ist das was unser standard konstrukte
und konstruiert sei es liefert einfach das attribut eis zurück und kapuze tief liefert uns länge des arrays vorsicht nachdem er starten mit einem leeren muss man die feine unterscheidung machen aber dessen länge wie abfragen können gute nicht wird nicht dann gebe einfach die null als kapazität zurück so die methode at ist für das ganz leicht die gibt uns einfach den eaton eintrag zurück allerdings ja wir wollen natürlich keine fehler machen wir wollen schauen ob diese idee eintrag auch existiert ihr wisst dass ein ja was ohne index out of bounds exception bekommt wenn ja auf den
falschen index oder ungültigen index zugreift oder den verwendet in unserem sektor da müssen wir aufpassen weil wir haben eine kapazität das heißt wir haben kapazität viele gültige indizes aber tatsächlich verwenden wir nur sei es viele einträge das heißt wenn das hier unser dass es verwendet dass es verwendet das ist verwendet die anderen beiden mich das heißt es ist hier 3 dann werden gültige index der index 0 den x1 der index 2 der index drei und vier jeweils aber nicht das heißt wir müssen sicherstellen dass dieser index die hier zwischen 0 und 13 ist den test
in java ee macht dem müssen wir hier nochmal ein bisschen schärfer machen und schauen dass wir zwischen null und seis -1 sind also sich ausschließlich k3 gesagt hatte in dem fall zwischen null und zwei sind und das machen wir hier mit mir hilfsfunktion jack jack ist ganz einfach die nimmt den index überprüft den und gibt dem index zurück wenn er gültig war und wenn er ungültig war dann wirft sie eine ausnahme eine exception auf das heißt bricht den aktuellen programm fluss ab diese hilfs methode ist deswegen ganz nett weil ich kann die einfach hier reinschreiben
die gibt den index zurück wenn er okay war und bricht ab mit der exception wenn nicht okay ist das heißt meine at methode ist ganz leicht und ich kann an anderer stelle auch dass jack gegebenenfalls nochmal verwenden so die methode research die macht auch genau das was wir gerade gesprochen dann wenn die kapazität kleiner ist als die anzahl einträge die ich haben möchte dann und nur dann muss ich was machen da schaue ich mir vorher an wie viele einträge möchte ich denn vorsicht wir fangen hier mit lehrern race an und ich sage es macht keinen
sinn der größe 1 oder 2 mir zu verschaffen unsere airways haben immer eine mindestgröße gehen wir noch mal zurück was man 16 weil es einfach keinen großen wert macht bei kleinen er es zu viel zu sparen ist kostet uns nur das umkopieren also unsere hat immer mindestens eine größe 16 und ab dann wird immer verdoppelt zu 32 64 usw naja ich sehen das wird nicht verdoppelt das geht dann ein kleines bisschen langsamer also wenn die kapazität kleiner ist dann werde ich ein neues harry am anlegen dann kopiert meine daten von null bis ausschließlich in dieses
neue ring und für alle restlichen daten sorge ich dafür dass dann 0 drin stellt ich initialisiert also mein neues hervor sieht ja was macht das für mich also diese beiden zahlen bräuchte ich eigentlich nicht ich schreibe trotzdem rein weil für die leute die ci plus programmieren dann muss ich das tatsächlich machen wenn ich zwischen den beiden sprachen hin und her wechsel der coach sieht fast genauso aus dann kommt man relativ leicht durcheinander deswegen alle initialisierung mache ich hier tatsächlich nochmal mit auch wenn ja wird es machen würde und danach sorge ich dafür dass meine ray
tatsächlich das area sowie serv kopiert die alten einträge so was macht jetzt resize an der stelle habe ich ein kleines bisschen anders gemacht als gerade eben cerf hat gerade eben tatsächlich verdoppelt hier schaue ich dass ich in resize das exponentielle wachstum hat spielt keine rolle wo ich das an der stelle macht card habe ich mich leichter getan es so zu erklären also réserve sorgt dafür dass ich tatsächlich platz für exakten einträge habe resize sorgt dafür dass sich n einträge verwenden kann wenn meine kapazität nicht reicht also wenn das end größer ist als die aktuelle kapazität
dann rufe ich surf auf aber nicht zwingend mit dem n sondern mit dem maximum aus dem n und was was sich exponentiell wachsen lasse gerade eben habe ich verdoppelt ich lasse nicht ganz so schnell wachsen sondern nehmen entschuldigung die neue kapazität immer als drei halbe also anderhalb mal die alte kapazität an der aussage von gerade heben ändert sich nichts der vector wächst trotzdem exponentiell in der kapazität bloß nicht ganz so schnell an den amortisierten kosten ändert sich an der stelle auch nichts vorsicht an einer stelle muss man trotzdem ein bisschen aufpassen wenn man hier egal
ob man mal drei halbe nehmen hier müssen wir noch drei halbe mit integriertem ethik rechnen das heißt ich muss schauen dass da nichts falsch abgerundet wird wir haben am anfang gegebenenfalls eine kapazität von 0 und 0 mal irgendwas bleibt natürlich 0 deswegen steht hier die plus1 um dafür zu sorgen dass es auf jeden fall größer wird auch am anfang so jetzt ein fall den wir noch nicht betrachtet haben was passiert wenn ich mein kleiner machen einmal an der darstellung im speicher soll sich erstmal gar nichts ändern das heißt ich fresse wir immer mehr und mehr
speicher mineiro wächst immer in der kapazität aber die kapazität soll die schrumpfen ist ein bisschen fraglich ob das gut ist ich halte an der stelle für gut allerdings wäre es noch besser die klasse vector zu erweitern um eine methode die für dafür sorgt dass der vector tatsächlich auch in der kapazität strümpfen kann zumindest dann wenn ich das will das fehlt tatsächlich gerade das heißt wir schrumpfen nicht aber wenn man die kapazität entschuldigung wenn man die größe kleiner machen also wenn das von dem ries kleiner ist als die aktuelle größe was machen wir dann dann über
schreibe ich alle einträge die in meinem race sind aber eben nicht mehr drin sein soll mit 0 es muss ich an der stelle auch nicht unbedingt machen kann sehr einfach stehen lassen da wo sie sind dieses überschreiben mit 0 sorgte aber dafür dass der garbage collector eine chance hat diese einträge was immer dahinter sich verbeugen hat tatsächlich auch freizugeben umgekehrt wird man das ganze in c++ schreiben zb wäre es an der stelle noch komplizierter dann müsste man soll dafür sorgen dass die entsprechenden strukturen aufgerufen werden also das was hier steht ist ja eine freundliche erinnerung
daran dass ich diese einträge die ich nicht mehr brauche weil ich das airrail verkleinerung dem sei es einfach kleiner macht das mit ihnen irgendwas noch passieren soll hier gebe ich dem garbage collector songs beziehen bevor ich sei es dann tatsächlich auf einsätze einmal nämlich vergrößern einmal in den ich verkleinert und ich habe hier zwei fälle es gibt noch einen dritten wenn sich nicht geändert hat dann passiert gar nichts naja man kann nicht sei es auch wieder gleichsetzen damit hat push back genauso implementiert wie man es gerade eben gemacht haben alte größe märkten nehme gleich als
indexende dafür sorgen dass man einst größer werden resize hochdorf auf aber da passiert eben nur was wenn ich tatsächlich kapazität brauche und danach setzte ich den eintrag an der stelle in auf das was ich einfügen möchte und wir haben genau den effekt das ganze hat konstante kosten dann bin ich nichts machen muss und lineare kosten immer dann wenn ich um kopieren muss wenn meine kapazität zu klein ist das passiert aber nicht oft das passiert nur logarithmisch oft inn en und ihren nachgerechnet amortisiert wenn ich über alles mittel bleibe ich bei konstanten kosten jetzt fehlen noch
ein paar andere operationen wir wollen an einer beliebigen stelle was einfügen naja wenn wir was einfügen wollen müssen wir auf jeden fall vergrößern wir wollen einen eintrag einfügen also müssen wir uns unser harry auf jeden fall um 1 wachsen wir müssen schauen ob dieser index endgültiger index ist und ja was müssen wir dann machen dann müssen wir platz schaffen wir müssen also die einträge die rechts von dem stehen sollen auch um 1 nach rechts schieben und das ist im prinzip schleife ganz ähnlich wie das bei in sessions und auch geschrieben also wir schieben alles was
vorher kommt um 1 nach rechts dann haben einen freien platz und an den kragen platzt fügt man unser unseren neuen eintrag 1 wie oft müssen wir da verschieben ja das kommt drauf an an welchem index wir einfügen wenn wir das ganze mitteln dann müssen wir mittel immer bis zur hälfte der siz einträge laufen das heißt diese funktion in satt hat auf jeden fall linearen aufwand die funktion talkback die soll den letzten eintrag aus de merry einfach löschen dazu benutze ich an der stelle auch wieder diese hilfsfunktion jack die soll schauen ob es den letzten eintrag
überhaupt gibt an den letzten eintrag gibt es wenn es wenigstens den index 0 gibt also wenn man nicht mehr ist wenn ja wird auch wieder exception aufgeworfen wenn ein passiert hier gar nichts und ich verringere einfach sei es um 1 das ist ein pre income and das passiert zuerst und danach wird er an der stelle auf null gesetzt auch wieder um den kollektor chance zu bieten einer beliebigen stelle löschen ist wieder ein bisschen komplizierter ich muss schauen ob der index gründlicher gültig ist ich muss dieses mal nach links schieben also der eintrag die nicht löschen
will ist sozusagen die lücke die ich will und so habe ich dann ganz rechts an der stelle sei es einen eintrag doppelt nach dem schieben gegenüber schreibe ich mit 0 auch wieder mit dem gab es korrekturen chance zweck herzugeben top-act läuft auf jeden fall in konstanter zeit ab er passierte fast gar nichts der ace hat wieder linearen aufwand weil ich verschieben muss im mittel sei es halbe viele einträge wenn man noch mal zusammenfassen die unterschiedlichen operationen haben jetzt ja unterschiedlichen aufwand sei es ab fragen geht in von einst seien von uns attribut abgeraten auf einem
beliebigen eintrag zu greifen auf den eintrag im index das geht von ary auch im ofen 1 muss einfach nur data zurückgeben nachdem ich den index für gültig erklärt hab auch schon gemacht buschbeck ist von einst die meiste zeit aber falls nicht genug kapazität ist habe ich kosten von von n wir haben gesehen dass wir im mittel bzw genauer amortisiert tatsächlich konstante kosten haben für unsere rechnung haben immer wieder verdoppelt hier in der implementierung vor anderhalb ich wer nachlesen will das gibt einen ganz netten beitrag von andrew koenig damals ging es um den std vector in
der zyklus plus standard library wo über verschiedene faktoren diskutiert wurde an der halt mal bzw goldener schnitt mal ist gegebenenfalls eine bessere wahl wir wissen will warum kann hier nachlesen die implementierungen die ich kenne die verdoppeln tatsächlich ja aber es ist egal es muss irgendwas sein was größer ist als einst damit wir ein exponentielles wachstum haben so dass wir eben nicht wirklich oft vergrößern müssen damit ist dieser sonderfall ich muss mehr kapazität schaffen im mittel vernachlässigbar ganz vernachlässigt weise natürlich nicht weil wir nicht in der welt leben wo man den mittleren fall haben sondern es
kann eben konkret mal sein dass wir verdoppeln müssen wenn ich das vorher weiß wie kurs bei murray werden könnte dann ist es ganz gut vorher einmal bis 11 aufzurufen und dafür zu sorgen dass das erinnern schon mal die richtige kapazität hat in jedem fall haben alle methoden die einer beliebigen position das einfügen und löschen und deswegen einträge verschieben müssen den aufwand von ufern in also den aufwand der linear ist in der anzahl einträge im und damit sind wir mit diesem ersten teil fertig und schauen uns im nächsten teil andy murray mit hilfe von verketteten listen
darstellen kann