[Musik spiller] DOUG LLOYD: Okay. Så hvis du lige blevet færdig, at video på enkeltvis forbundne lister sorry Jeg forlod dig ud på en lidt af en cliffhanger. Men jeg er glad for du er her for at afslutte historien om dobbelt forbundne lister. 

Så hvis du husker fra at video, vi talte om, hvordan enkeltvis forbundne lister gør deltage i vores evne at behandle oplysninger hvor antallet af elementer eller antallet af elementer i en liste kan vokse eller skrumpe. Vi kan nu håndtere noget lignende, hvor vi ikke kunne håndtere det med arrays. 

Men de lider af en kritisk begrænsning som er, at med en enkelt-koblet liste, kan vi kun nogensinde flytte i en enkelt retning gennem listen. Og den eneste virkelige situation hvor der kan blive et problem var, da vi forsøgte at slette et enkelt element. Og vi ikke engang diskutere, hvordan man gør det i et enkelt-linket liste i pseudokode. Det er helt sikkert gennemførligt, men det kan være lidt af en besværet. Så hvis du finder dig selv i en situation, hvor du forsøger at slette enkelte elementer fra listen eller det vil blive krævet at du vil være at slette enkelte elementer fra listen, kan du overveje at anvende en dobbelt-bundet listen i stedet for en enkelt-linket liste. Fordi dobbelt forbundne lister giver dig mulighed at flytte både forlæns og baglæns gennem listen i stedet for lige fremad gennem list-- bare ved at tilføje en ekstra element til vores struktur definition for den dobbelt-linkede liste node. 

Igen, hvis du ikke kommer til at være at slette enkelte elementer fra list-- fordi vi tilføjer et ekstra felt til vores struktur definition, knudepunkterne selv for dobbelt-hægtede lister vil være større. De kommer til at tage op flere bytes hukommelse. Og så hvis dette ikke er noget du får brug for at gøre, du kan beslutte, det er ikke værd at afvejningen nødt til at bruge de ekstra bytes hukommelse kræves for en dobbelt-linked liste, hvis du ikke er vil være at slette enkelte elementer. Men de er også køligt til andre ting også. 

Så som jeg sagde, vi bare nødt til at tilføje én enkelt felt til vores struktur definition-- dette begreb af en tidligere pointer. Så med en enkelt-linket liste, vi har værdi og næste pointer, så den dobbelt-linkede liste har blot en måde at bevæge sig baglæns så godt. 

Nu i enkelt-bundet Listen video, vi talte om disse er fem af de vigtigste ting, du skal være kan gøre for at arbejde med hægtede lister. Og for de fleste af disse er den omstændighed, at det er en dobbelt-linked liste er egentlig ikke et stort spring. Vi kan stadig søge gennem ved blot bevæger sig fremad fra start til slut. Vi kan stadig skabe et knudepunkt ud af blå luft, temmelig meget på samme måde. Vi kan slette lister temmelig meget på samme måde også. De eneste ting, er subtilt anderledes, virkelig, indsætter nye noder i listen, og vi vil endelig taler om sletning et enkelt element fra listen samt. Igen, temmelig meget de tre andre, men vi er ikke kommer til at tale om dem lige nu, fordi de er bare meget mindre tweaks på de ideer, diskuteret i enkelt-linkede liste video. 

Så lad os indsætte en ny knude i en dobbelt-bundet listen. Vi talte om at gøre dette til enkeltvis-linked lister så godt, men der er et par ekstra fangster med dobbelt-hægtede lister. Vi er [? passerer?] i spidsen for liste her og nogle arbitrær værdi, og vi ønsker at få den nye leder af listen ud af denne funktion. Det er derfor, den returnerer en dllnode stjerne. Så hvad er de skridt? De er, igen, meget lignende til enkeltvis forbundne lister med en ekstra tilsætning. Vi vil allokerer plads til en ny node og kontrol for at sikre, at det er gyldigt. Vi ønsker at udfylde denne node op med de oplysninger, vi ønsker at lægge i det. Det sidste, vi har brug for at do-- den ekstra ting, vi skal gøre, rather-- er at fastsætte den Forrige pointer af den gamle leder af listen. Husk, at fordi af dobbelt forbundne lister, vi kan komme videre og backwards-- som betyder, at hvert knudepunkt faktisk peger til to andre knudepunkter i stedet for kun én. Og så er vi nødt til at fastsætte den gamle leder af listen til at pege bagud til den nye leder af den linkede liste, hvilket var noget Vi behøvede ikke at gøre før. Og som før, vi bare returnere en pointer til den nye leder af listen. 

Så her er en liste. Vi vil indsætte 12 ind i denne liste. Bemærk, at diagrammet er lidt anderledes. Hvert knudepunkt indeholder tre fields-- data, og en næste pointer i rødt, og et Forrige pointer i blåt. Intet kommer før 15 node, så dens Forrige pointer er null. Det er begyndelsen af ​​listen. Der er ikke noget, før det. Og intet kommer efter 10 node, og så det er næste pointer er null så godt. 

Så lad os tilføje 12 til denne liste. Vi har brug for [uhørligt] plads til node. Vi sætter 12 inde i den. Og så igen, er vi nødt til at være virkelig Pas på ikke at bryde kæden. Vi ønsker at omarrangere pejlemærker i den rigtige rækkefølge. Og nogle gange, der kan mean-- som vi vil se særligt med delete-- at vi har nogle redundante pegepinde, men det er OK. 

Så hvad gør vi ønsker at gøre først? Jeg vil anbefale ting bør du sandsynligvis gøre er at udfylde pointerne af 12 node, før du rører nogen anden. Så hvad der 12 kommer til at pege på næste? 15. Hvad kommer før 12? Ingenting. Nu har vi fyldt den ekstra information i 12 så det har Forrige, Næste, og værdi. 

Nu kan vi få 15-- denne ekstra skridt vi talte om-- vi kan have 15 point tilbage til 12. Og nu kan vi flytte lederen af den linkede liste også være 12. Så det er temmelig svarer til, hvad vi gjorde med enkeltvis forbundne lister, bortset fra det ekstra trin af forbinder den gamle leder af listen tilbage til den nye leder af listen. 

Lad os nu endelig slette en knude fra en sammenkædet liste. Så lad os sige, vi har en anden funktion, er at finde en node, vi ønsker at slette og har givet os en pointer til præcis node, som vi ønsker at slette. Vi behøver ikke engang need-- sige det hoved er stadig globalt erklæret. Vi har ikke brug hovedet her. Alt dette funktion gør, er at vi har fundet en pointer til præcis knudepunktet vi ønsker at slippe af med. Lad os slippe af med det. Det er meget nemmere med dobbelt-bundet lister. First-- det er faktisk blot et par ting. Vi skal bare ordne det omgivende knudepunkters pointers så de springe over node, vi ønsker at slette. Og så kan vi slette denne node. Så igen, vi bare går igennem her. Vi har tilsyneladende besluttet, at vi ønsker at slette node X. Og igen, hvad jeg er gør her-- ved way-- er et generelt tilfældet for en node, der er i midten. Der er et par af ekstra advarsler, som du nødt til at overveje, når du sletter begyndelsen af ​​listen eller meget slutningen af ​​listen. Der er et par særligt corner tilfælde at behandle der. 

Så det virker for at slette enhver node i midten af ​​list-- en, har en legitim pointer fremad og en legitim pointer baglæns, legitim Forrige og Næste pointer. Igen, hvis du arbejder med enderne, du nødt til at håndtere dem lidt anderledes, og vi vil ikke tale om det nu. Men du kan nok regne ud, hvad der skal skal gøres lige ved at se denne video. 

Så vi har isoleret X. X er node Vi ønsker at slette fra listen. Hvad gør vi? Først har vi brug for at omarrangere de udvendige pointere. Vi er nødt til at omarrangere 9 næste at springe over 13 og pege på 10-- hvilke er det, vi lige har gjort. Og vi har også brug for omarrangere 10 s Forrige at pege på 9 i stedet for at pege på 13. 

Så igen, var det diagram til at begynde med. Dette var vores kæde. Vi er nødt til at springe over 13, men vi skal også bevare integriteten af ​​listen. Vi ønsker ikke at miste nogen information i begge retninger. Så vi er nødt til at omarrangere pegepinde omhyggeligt så vi ikke bryder kæden overhovedet. 

Så vi kan sige 9 s næste pointer peger på det samme sted at tretten Next pointer peger lige nu. Fordi vi er i sidste ende vil ønsker at springe over 13. Så uanset hvor 13 point næste, du vil ni at pege der i stedet. Så det er det. Og så uanset hvor 13 point tilbage til, hvad der kommer før den 13., vi ønsker 10 til punkt til at i stedet for 13. Bemærk nu, hvis du følger pilene, kan vi slippe 13 uden faktisk at miste nogen oplysninger. Vi har holdt integriteten af ​​listen, flytte både fremad og bagud. Og så kan vi bare slags af rense det en lille smule op ved at trække listen sammen. Så vi omarrangeres pejlemærker på begge sider. Og så har vi befriet X den node, der indeholdt 13, og vi ikke bryde kæden. Så vi gjorde det godt. 

Sidste bemærkning her på hægtede lister. Så både singly- og dobbelt-bundet lister, som vi har set, støtte virkelig effektiv indsættelse og sletning af elementer. Du kan stort set gøre den i konstant tid. Hvad gjorde vi nødt til at gøre for at slette et element blot et sekund siden? Vi flyttede en pointer. Vi flyttede en anden pointer. Vi befriede X-- tog tre operationer. Det tager altid tre operationer til slette node-- at frigøre en node. 

Hvordan vi indsætter? Nå, men vi er bare altid tacking på begyndelsen hvis vi indsætter effektivt. Så vi er nødt til at rearrange-- afhængigt af om det er en singly- eller dobbelt-bundet liste, kan vi nødt til at gøre tre eller fire operationer max. Men igen, det er altid tre eller fire. Det er ligegyldigt, hvor mange elementer er i vores liste, det er altid tre eller fire operations-- ligesom deletion er altid tre eller fire operationer. Det er konstant tid. Så det er virkelig stor. 

Med arrays, vi gør noget indsættelse slags. Du husker formentlig, at indsættelse sortering er ikke en konstant tid algoritme. Det er faktisk temmelig dyrt. Så dette er meget bedre til at indsætte. Men som jeg nævnte i enkelt-sammenkædet liste video, vi har fået en ulempe også her, ikke? Vi har mistet evnen til at tilfældigt adgang elementer. Vi kan ikke sige, jeg ønsker element nummer fire eller element nummer 10 i en sammenkædet liste på samme måde, som vi kan gøre det med et array eller vi kan bare direkte indeks ind i vores arrayets element. 

Og så forsøge at finde en element i en lænket list-- hvis søgning er important-- kan nu tage lineær tid. Da listen bliver længere, det kan tage et yderligere trin for hver enkelt element i listen i for at finde, hvad vi leder efter. Så der er trade offs. Der er lidt af en pro og con element her. 

Og dobbelt forbundne lister er ikke den sidste slags datastruktur kombination at vi vil snakke om, tager alle de grundlæggende bygning blokke af C en at sammensætte. Fordi i virkeligheden, kan vi selv gøre det bedre end dette at skabe en datastruktur, du måske være i stand til at søge gennem i konstant tid også. Men mere om det i en anden video. 

Jeg er Doug Lloyd. Det er CS50.