>> [MUSIC SPILLE]
DOUG LLOYD: All right.
Så hvis du nettopp ferdig som video på enkeltvis-lenkede lister beklager
Jeg forlot deg av på en litt av en cliffhanger.
Men jeg er glad for at du er her for å fullføre historien om dobbelt-lenkede lister.
>> Så hvis du husker fra som video, vi snakket
om hvordan enkeltvis bundet lister gjør delta på vår evne
å forholde seg til informasjon hvor antallet elementer
eller antall elementer i en liste kan vokse eller krympe.
Vi kan nå håndtere noe sånt, der
vi kunne ikke håndtere det med arrays.
>> Men de har lider av én kritisk begrensning som
er det med en enkeltvis bundet listen, kan vi bare noensinne flytte
i én retning gjennom listen.
Og den eneste virkelige situasjonen hvor det kan bli et problem
var da vi prøvde å slette en enkelt element.
Og vi hadde ikke engang diskutere hvordan vi skal gjøre det i en enkeltvis-lenket liste i pseudokode.
Det er absolutt gjennomførbart, men det kan være litt av en problemfri.
Så hvis du finner deg selv i en situasjon der
du prøver å slette enkeltelementer fra listen
eller det kommer til å være nødvendig at du skal slette
enkeltelementer fra listen, kan det være lurt
vurdere å bruke en dobbelt-linked liste i stedet for en enkeltvis-lenket liste.
Fordi dobbelt-lenkede lister tillate deg å flytte både forover og bakover
gjennom listen i stedet for bare frem gjennom list--
bare ved å legge en ekstra element til vår struktur definisjon
for dobbelt-lenket liste node.
>> Igjen, hvis du ikke kommer til å være å slette enkeltelementer
fra list-- fordi vi legger et ekstra felt til vår struktur
definisjon, nodene selv for dobbelt-lenkede lister
kommer til å bli større.
De kommer til å ta opp flere byte med minne.
Og så hvis dette ikke er noe du kommer til å trenge å gjøre,
du kan bestemme det er ikke verdt trade off
å måtte bruke ekstra byte minne kreves
for en dobbelt-lenket liste hvis du ikke er kommer til å være å slette enkeltelementer.
Men de er også kult for andre ting også.
>> Så som jeg sa, vi må bare legge til én enkelt felt i vår struktur
definition-- denne oppfatningen av en tidligere pekeren.
Så med en enkeltvis-lenket liste, vi har verdien og Neste pekeren,
så dobbelt-lenket liste bare har en måte å bevege seg bakover også.
>> Nå i det enkeltvis bundet liste video, vi snakket
om disse er fem av viktigste tingene du trenger å være
i stand til å gjøre for å jobbe med koblede lister.
Og for de fleste av disse, det faktum at det er en dobbelt-lenket liste
er egentlig ikke et stort hopp.
Vi kan fortsatt søke gjennom etter bare fremover fra start til slutt.
Vi kan fortsatt lage en node ut av tynn luft, ganske mye på samme måte.
Vi kan slette lister pen mye på samme måte også.
De eneste tingene som er litt forskjellig,
egentlig, setter inn nye noder i listen,
og vi vil endelig snakke om sletting ett element fra listen også.
Igjen, ganske mye de tre andre, vi er
ikke kommer til å snakke om dem akkurat nå, fordi de er bare
meget mindre tilpasninger på de ideer diskutert i enkeltvis-lenket liste video.
>> Så la oss sette inn en ny node inn i en dobbelt-lenket liste.
Vi snakket om å gjøre dette for enkeltvis bundet lister også,
men det er et par ekstra fanger med dobbelt-lenkede lister.
Vi er [? passerer?] i hodet av liste her og litt vilkårlig verdi,
og vi ønsker å få den nye sjefen av listen ut av denne funksjonen.
Det er derfor det returnerer en dllnode stjerne.
Så hva er fremgangsmåten?
De er, igjen, svært lik til enkeltvis bundet lister
med en ekstra tillegg.
Vi ønsker å tildeler plass for en ny node og sjekk for å sikre at det er gyldig.
Vi ønsker å fylle det node opp med den informasjonen vi
ønsker å legge i det.
Det siste vi trenger å do-- den ekstra ting vi trenger å gjøre, rather--
er å fikse Forrige pekeren av den gamle hodet av listen.
Husk at på grunn av dobbelt-lenkede lister,
vi kan gå videre og backwards-- som
betyr at hver node faktisk peker til to andre noder i stedet for bare én.
Og så må vi fikse den gamle hodet av listen
å peke bakover til den nye sjefen for den lenket liste, som var noe
vi trengte ikke å gjøre før.
Og som før, vi bare returnere en Peker til ny leder av listen.
>> Så her er en liste.
Vi ønsker å sette 12 inn i denne listen.
Legg merke til at diagrammet er litt annerledes.
Hver node inneholder tre fields-- data, og en Neste peker i rødt,
og et Forrige peker i blått.
Ingenting kommer før 15 node, så sin Forrige pekeren er null.
Det er begynnelsen av listen.
Det er ikke noe før det.
Og ingenting kommer etter 10 node, og så det er Neste pekeren er null også.
>> Så la oss legge 12 til denne listen.
Vi trenger [uhørbart] plass til noden.
Vi satt 12 på innsiden av det.
Og så igjen, må vi være veldig Pass på å ikke bryte kjeden.
Vi ønsker å omorganisere pekere i riktig rekkefølge.
Og noen ganger at kanskje mean-- som vi skal se spesielt
med delete-- at vi har noen redundante pekere, men det er OK.
>> Så hva gjør vi ønsker å gjøre først?
Jeg vil anbefale ting du bør nok
gjøre er å fylle pekere til 12 node før du berører noen andre.
Så hva er 12 kommer til å peke på neste?
15.
Hva kommer før 12?
Ingenting.
Nå har vi fylt ekstra informasjon i 12
så det har Forrige, Neste, og verdi.
>> Nå kan vi ha 15-- denne ekstra skrittet vi snakket om-- vi
kan ha 15 poeng tilbake til 12.
Og nå kan vi bevege hodet den lenket liste til også å være 12.
Så det er ganske likt det vi gjorde med enkeltvis-lenkede lister,
med unntak for det ekstra trinnet koble den gamle hodet av listen
tilbake til ny leder av listen.
>> La oss nå endelig slette en node fra en lenket liste.
Så la oss si at vi har noen annen funksjon som
er å finne en node vi ønsker å slette og har gitt oss en peker til nøyaktig
noden som vi ønsker å slette.
Vi trenger ikke engang need-- si Hodet er fremdeles globalt erklært.
Vi trenger ikke hodet her.
All denne funksjonen gjør er vi har funnet en peker til nøyaktig noden vi
ønsker å bli kvitt.
La oss bli kvitt det.
Det er mye enklere med dobbelt bundet lister.
First-- det er faktisk bare et par ting.
Vi trenger bare å fikse det omliggende noder 'pekere slik at de hoppe over
noden vi ønsker å slette.
Og så kan vi slette denne noden.
Så igjen, vi bare går gjennom her.
Vi har tydeligvis bestemt seg for at vi vil slette noden X.
Og igjen, hva jeg er gjør her-- av måte--
er en generell sak for en node som er i midten.
Det er et par av ekstra begrensninger som du
må vurdere når du sletter Helt i begynnelsen av listen
eller helt på slutten av listen.
Det er et par spesielle hjørne saker å forholde seg til det.
>> Så dette fungerer for å slette noen node i midten av den ene som list--
har en legitim peker fremover og en legitim peker bakover,
legitim Forrige og Neste pekeren.
Igjen, hvis du jobber med endene, du
trenger for å håndtere de litt annerledes,
og vi ikke kommer til å snakke om det nå.
Men du kan sannsynligvis finne ut hva som må
gjøres bare ved å se denne videoen.
>> Så vi har isolert X. X er node vi vil slette fra listen.
Hva skal vi gjøre?
Først må vi omorganisere utsiden pekere.
Vi trenger å omorganisere 9 neste å hoppe over 13
og peker på 10-- som er det vi nettopp har gjort.
Og vi må også omorganisere 10s Forrige
til å peke til 9 i stedet for å peke på 13.
>> Så igjen, dette var den diagram til å begynne med.
Dette var vår kjede.
Vi trenger å hoppe over 13, men vi må også bevare
integriteten av listen.
Vi ønsker ikke å miste noen Informasjonen i begge retninger.
Så vi trenger å omorganisere pekere nøye
slik at vi ikke bryte kjeden i det hele tatt.
>> Så vi kan si 9 Next pekeren peker til samme sted
at tretten Next pekeren peker akkurat nå.
Fordi vi er slutt skal du ønsker å hoppe over 13.
Så uansett hvor 13 poeng neste, du Vil ni til punkt der i stedet.
Så det er det.
Og så uansett hvor 13 poeng tilbake til, det som kommer før 13,
vi ønsker 10 å peke til at i stedet for 13.
Nå legger merke til, hvis du følger pilene, kan vi slippe 13
uten egentlig å miste informasjon.
Vi har holdt integriteten av listen, flytting både forover og bakover.
Og så kan vi bare liksom av rydde opp litt
ved å trekke listen sammen.
Så vi omorganisert pekere på hver side.
Og da er vi frigjort X den node som inneholdt 13,
og vi ikke bryte kjeden.
Så vi gjorde det bra.
>> Endelig notat her på lenkede lister.
Så både singly- og dobbelt bundet lister, som vi har sett,
support virkelig effektiv innsetting og sletting av elementer.
Du kan stort sett gjøre det i konstant tid.
Hva gjorde vi må gjøre for å slette et element bare et sekund siden?
Vi flyttet én pekeren.
Vi flyttet en annen pekeren.
Vi frigjort X- tok tre operasjoner.
Det tar alltid tre operasjoner til slett at node-- å frigjøre en node.
>> Hvordan setter vi?
Vel, vi er bare alltid vinne på begynnelsen
hvis vi setter effektivt.
Så vi må rearrange-- avhengig av om det er
en singly- eller dobbelt bundet liste, kanskje vi trenger å gjøre tre
eller fire operasjoner max.
Men igjen, det er alltid tre eller fire.
Det spiller ingen rolle hvor mange elementene er på vår liste,
det er alltid tre eller fire operations-- akkurat som sletting er alltid
tre eller fire operasjoner.
Det er konstant tid.
Så det er virkelig flott.
>> Med arrays, ble vi gjør noe som innsetting sort.
Du husker sikkert at innsetting sorter er ikke en konstant tid algoritme.
Det er faktisk ganske dyrt.
Så dette er mye bedre for å sette inn.
Men som jeg nevnte i enkeltvis-lenket liste video,
vi har en ulemper her også, ikke sant?
Vi har mistet evnen til å tilfeldig tilgang elementer.
Vi kan ikke si, jeg ønsker element nummer fire eller element nummer 10 av en lenket liste
På samme måte som vi kan gjøre det med en rekke
Eller vi kan bare direkte index inn i vårt utvalg er element.
>> Og så prøver å finne en element i en koblet list--
dersom søker er important-- kan nå ta lineær tid.
Som listen blir lengre, det kan ta ett ekstra trinn
for hvert enkelt element i listen i For å finne det vi leter etter.
Så det er avveininger.
Det er litt av en pro og con element her.
>> Og dobbelt-lenkede lister er ikke den siste slags datastruktur kombinasjon
at vi skal snakke om, tar alle de grunnleggende bygge
blokker av C en sette sammen.
Fordi faktisk, kan vi gjøre det enda bedre enn dette
for å opprette en datastruktur som du kan være i stand til å søke gjennom
i konstant tid også.
Men mer om det i en annen video.
>> Jeg er Doug Lloyd.
Dette er CS50.