[Speel van musiek] DOUG LLOYD: Alle reg. So as jy klaar net dat video op enkel-geskakelde lyste jammer Ek het jou af op 'n bietjie van 'n fotonische lewe. Maar ek is bly dat jy hier is om te voltooi die verhaal van dubbel-geskakelde lyste. So as jy onthou uit dat die video, het ons gepraat oor hoe enkel-gekoppelde lyste te doen by te woon ons vermoë om te gaan met inligting waar die aantal elemente of die aantal items in 'n lys kan groei of krimp. Ons kan nou hanteer iets soos dat, waar ons kon nie dit hanteer met skikkings. Maar hulle het ly aan een kritieke beperking wat is dat met 'n enkel-gekoppelde lys, kan ons net ooit beweeg in 'n enkele rigting deur die lys. En die enigste werklike situasie waar wat 'n probleem kan raak was toe ons probeer om verwyder 'n enkele element. En ons het nie eens bespreek hoe om dit te doen in 'n enkel-geskakelde lys in pseudokode. Dit is beslis uitvoerbaar nie, maar dit kan 'n bietjie van 'n probleem te wees. So as jy jouself in 'n situasie waar jy probeer om te verwyder enkele elemente uit die lys of dit gaan nodig wees dat jy sal die verwydering enkele elemente van die lys, kan jy wil oorweeg om 'n dubbel-gekoppelde lys plaas van 'n enkel-geskakelde lys. Omdat dubbel-geskakelde lyste toelaat beide vorentoe en agtertoe beweeg deur die lys plaas van net vorentoe deur die list-- net deur die toevoeging van 'n ekstra element om ons struktuur definisie vir die dubbel-geskakelde lys knoop. Weereens, as jy nie van plan om enkele elemente verwydering uit die list-- omdat ons die toevoeging 'n ekstra veld om ons struktuur definisie, die nodes hulself vir dubbel-geskakelde lyste gaan groter wees. Hulle gaan neem meer grepe van die geheue. En so as dit is nie iets jy gaan nodig om te doen, jy kan besluit dit is nie die moeite werd die handel af om die ekstra spandeer grepe van die geheue benodig vir 'n dubbel-geskakelde lys as jy nie gaan skrap enkele elemente. Maar dit is ook koel vir ander dinge ook. So as ek gesê het, het ons net om by te voeg 'n enkele veld om ons struktuur definition-- hierdie idee van 'n vorige wyser. So met 'n enkel-geskakelde lys, ons het die waarde en die Volgende pointer, so die dubbel-geskakelde lys het net 'n manier om agteruit beweeg as well. Nou in die enkel-gekoppelde lys video, het ons gepraat oor hierdie is vyf van die belangrikste dinge wat jy nodig het om te wees in staat wees om te doen om te werk met geskakelde lyste. En vir die meeste van hierdie, die feit dat dit 'n dubbel-geskakelde lys is nie regtig 'n groot sprong. Ons kan nog steeds deur soek deur net vorentoe beweeg van begin tot einde. Ons kan nog steeds skep 'n node uit lug, pretty much dieselfde manier. Ons kan lyste mooi verwyder baie dieselfde manier ook. Die enigste dinge wat is subtiel verskillende, regtig, is die invoeging nuwe nodes in die lys, en ons sal uiteindelik praat oor die verwydering van 'n enkele element van die lys as well. Weereens, pretty much die ander drie, ons is nie gaan om te praat oor hulle nou, want hulle is net baie klein tweaked op die idees bespreek in die enkel-geskakelde lys video. So laat voeg 'n nuwe node in 'n dubbel-geskakelde lys. Ons het gepraat oor hierdie vir doen enkel-geskakelde lyste, asook, maar daar is 'n paar ekstra vang met dubbel-geskakelde lyste. Ons is [? verby?] in die kop van die lys hier en 'n paar arbitrêre waarde en ons wil hê dat die nuwe hoof kry van die lys van hierdie funksie. Dit is waarom dit gee 'n dllnode ster. So, wat is die stappe? Hulle is, weer, baie soortgelyk om enkel-geskakelde lyste met 'n ekstra toevoeging. Ons wil ruimte ken vir 'n nuwe knoop en check om seker te maak dit is geldig. Ons wil hê dat die node vul met alles wat inligting wat ons wil in dit te sit. Die laaste ding wat ons nodig het om die do-- ekstra ding wat ons nodig het om te doen, rather-- is om die vorige wyser los van die ou hoof van die lys. Onthou dat, omdat van dubbel-geskakelde lyste, kan ons vorentoe beweeg en backwards-- wat beteken dat elke node eintlik wys twee ander nodes in plaas van net een. En so het ons nodig het om te los die ou hoof van die lys agteruit verwys na die nuwe hoof van die geskakelde lys, wat iets ons het nie om voor te doen. En soos voorheen, het ons net terug n wyser na die nuwe hoof van die lys. So hier is 'n lys. Ons wil voeg 12 in hierdie lys. Let daarop dat die diagram is effens anders. Elke node drie fields-- bevat data, en 'n Volgende wyser in rooi, en 'n Vorige wyser in blou. Niks kom voor die 15 node, so sy vorige wyser is null. Dit is die begin van die lys. Daar is niks voor dit. En niks kom nadat die 10-knoop, en so dit is Volgende wyser is null as well. So laat voeg 12 tot hierdie lys. Ons moet [onhoorbaar] ruimte vir die knoop. Ons het 12 binnekant van dit. En dan weer, moet ons werklik versigtig wees om nie die ketting breek. Ons wil die herrangskik wysers in die korrekte volgorde. En soms wat kan mean-- soos ons sal sien veral met delete-- dat ons het 'n paar oorbodig wysers, maar dit is OK. So wat wil ons eerste om te doen? Ek sou aanbeveel die dinge wat jy moet waarskynlik doen om die wysers van die 12 vul node voordat jy raak enigiemand anders. So, wat is 12 volgende gaan wys? 15. Wat kom voor 12? Niks nie. Nou het ons die vol bykomende inligting in 12 so dit het Vorige, Volgende, en waarde. Nou kan ons '15-- hierdie ekstra stap ons about-- ons praat kan 15 punt terug na 12 hê. En nou kan ons die hoof van beweeg die geskakelde lys om ook 12. So dit is redelik soortgelyk aan wat ons besig was met enkel-geskakelde lyste, behalwe vir die ekstra stap van die koppeling van die ou hoof van die lys terug na die nuwe hoof van die lys. Nou laat uiteindelik verwyder 'n knoop van 'n geskakelde lys. So kom ons sê ons het 'n ander funksie wat is om 'n node ons wil verwyder en het ons 'n wyser gegee om presies te die knoop wat ons wil verwyder. Ons weet nie eens need-- sê die hoof is nog steeds globaal verklaar. Ons het die hoof nie hier nodig. Alle hierdie funksie te doen, is ons het het 'n wyser presies die knoop ons wil ontslae te raak. Kom ons kry ontslae te raak van dit. Dit is 'n baie makliker met dubbel-geskakelde lyste. First-- dit is eintlik net 'n paar dinge. Ons moet net los die omliggende wysers nodes 'sodat hulle slaan oor die knoop ons wil verwyder. En dan kan ons dit node verwyder. So weer, ons is maar net gaan deur hier. Ons het blykbaar besluit dat ons wil die node X. verwyder En weer, wat ek doen here-- deur die way-- is 'n algemene saak vir 'n node wat in die middel. Daar is 'n paar van ekstra voorbehoude dat jy nodig om te oorweeg wanneer jy die verwydering van die begin van die lys of die einde van die lys. Daar is 'n paar van die spesiale hoek gevalle te hanteer is daar. So dit werk vir die verwydering van enige node in die middel van die een wat list-- het 'n wettige wyser vorentoe en 'n wettige wyser agtertoe, wettige Volgende en Vorige wyser. Weereens, as jy werk met die punte, wat jy moet daardie hanteer effens anders, en ons is nie van plan om praat oor wat nou. Maar jy kan waarskynlik uit te vind wat nodig net gedoen word deur te kyk na hierdie video. Dus het ons geïsoleer X. X is die node Ons wil verwyder uit die lys. Wat doen ons? Eerstens moet ons om te herrangskik buite wenke. Ons moet herrangskik 9 se volgende oor te slaan oor 13 en punt om 10-- wat is wat ons net gedoen het. En ons moet ook herrangskik 10 se Vorige om te wys op 9 in plaas van wys na 13. So weer, dit was die diagram om te begin met. Dit was ons ketting. Ons moet spring oor 13, maar ons moet ook bewaar die integriteit van die lys. Ons wil nie enige verloor inligting in enige rigting. So moet ons herrangskik die wysers versigtig sodat ons nie die ketting breek nie. So kan ons 9 se Volgende wyser sê wys na dieselfde plek dat dertien se Volgende wyser wys nou. Want ons is uiteindelik gaan wil slaan oor 13. So waar 13 punte Volgende, moet jy wil nege wys daar plaas. So dit is nie. En dan waar 13 punte agter om, ongeag kom voor 13, ons wil 10 te wys om in plaas van 13. Nou sien, as jy volg die pyle, kan ons drop 13 sonder enige inligting eintlik verloor. Ons het die integriteit van die lys gehou, beweeg beide vorentoe en agtertoe. En dan kan ons net soort van skoon dit 'n bietjie deur saam te trek in die lys. Sodat ons herrangskik die wysers aan weerskante. En dan het ons bevry X die node wat 13 vervat, en ons het nie breek die ketting. So ons het 'n goeie. Finale boodskap hier op geskakelde lyste. Sodat beide singly- en dubbel-gekoppelde lyste, soos ons gesien het, ondersteuning regtig doeltreffende invoeging en skrap elemente. Jy kan pretty much doen dit in konstante tyd. Wat het ons te doen het om te verwyder 'n element net 'n tweede gelede? Ons het verhuis een wyser. Ons het verhuis ander wyser. Ons bevry X-- het drie operasies. Dit vind altyd drie operasies om dat node-- verwyder om 'n knoop te bevry. Hoe weet ons plaas? Wel, ons is net altyd rygwerk op die begin as ons doeltreffend te voeg. So moet ons rearrange-- afhangende van of dit 'n singly- of dubbel-gekoppelde lys, kan ons nodig het om te doen drie of vier operasies max. Maar weereens, dit is altyd drie of vier. Dit maak nie saak hoeveel elemente is in ons lys, dit is altyd drie of vier operations-- net soos skrap is altyd drie of vier bedrywighede. Dit is konstante tyd. So dit is regtig baie goed. Met skikkings, ons doen iets soos invoeging soort. Jy onthou seker dat invoeging soort is nie 'n konstante tyd algoritme. Dit is eintlik redelik duur. So, dit is 'n baie beter vir die inbring. Maar soos ek in die genoemde enkel-geskakelde lys video, ons het 'n nadeel het ook hier, reg? Ons het die vermoë om te verloor lukraak toegang elemente. Ons kan nie sê, ek wil element nommer vier of element nommer 10 van 'n geskakelde lys dieselfde manier wat ons kan doen met 'n verskeidenheid Of ons kan net direk indeks in ons verskeidenheid element se. En so probeer om 'n te vind element in 'n gekoppelde list-- As soek is important-- kan nou lineêre tyd. As die lys langer kry, is dit dalk een addisionele stap vir elke enkele element in die lys in om uit te vind wat ons soek. So is daar handel offs. Daar is 'n bietjie van 'n pro en con element hier. En dubbel-geskakelde lyste is nie die laaste soort data struktuur kombinasie dat ons sal praat oor, neem al die basiese bou blokke van C 'n plaas saam. Want in werklikheid, kan ons selfs beter as dit doen om 'n struktuur te skep wat data jy dalk in staat wees om te soek deur in konstante tyd ook. Maar meer oor dit in 'n ander video. Ek is Doug Lloyd. Dit is CS50.