[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.