>> [MUSIK SPELA]
DOUG LLOYD: Okej.
Så om du precis avslutat att video på enstaka-länkade listor sorry
Jag lämnade dig ut på en bit av en cliffhanger.
Men jag är glad att du är här för att avsluta berättelsen om dubbelt-länkade listor.
>> Så om du minns från att video, vi pratade
om hur enstaka bunden listor gör delta i vår förmåga
att ta itu med uppgifter där antalet element
eller antalet artiklar i en lista kan växa eller krympa.
Vi kan nu ta itu med något liknande, där
Vi kunde inte ta itu med det med arrayer.
>> Men de lider av en kritisk begränsning som
är att med en enstaka bunden lista, kan vi bara någonsin flytta
i en enda riktning genom listan.
Och det enda verkliga situationen där detta kan bli ett problem
var när vi försökte radera ett enskilt element.
Och vi inte ens diskutera hur man gör det i en enkelt-länkad lista i pseudokod.
Det är förvisso genomförbart, men Det kan vara lite av ett besvär.
Så om du befinner dig i en situation där
du försöker ta bort enskilda element från listan
eller det kommer att krävas att du kommer att ta bort
enskilda element från listan, kanske du vill
överväga att använda en dubbelbunden lista istället för en enstaka-länkad lista.
Eftersom dubbelt-länkade listor låter dig att flytta både framåt och bakåt
igenom listan i stället för bara framåt genom list--
bara genom att lägga en extra inslag till vår struktur definition
för det två gånger länkad lista nod.
>> Återigen, om du inte kommer att att ta bort enskilda element
från list-- eftersom vi lägger ett extra fält till vår struktur
definition, noderna själva för dubbelt-länkade listor
kommer att bli större.
De kommer att ta upp fler byte minne.
Och så om detta inte är något du kommer att behöva göra,
du kan besluta att det är inte värt avvägning
att behöva spendera extra byte av minne som krävs
för en dubbelbunden listan om du inte kommer att radera enskilda element.
Men de är också coolt för andra saker också.
>> Så som sagt, vi måste bara lägga ett enda fält till vår struktur
definition-- detta begrepp av en tidigare pekare.
Så med en enkelt-länkad lista, vi har värdet och nästa pekaren,
så de två gånger länkad lista har bara ett sätt att gå bakåt också.
>> Nu i den ensamma bundna videolistan, vi pratade
om dessa är fem av viktigaste saker du behöver vara
kunna göra för att arbeta med länkade listor.
Och för de flesta av dessa, det faktum att det är en dubbelbunden listan
är egentligen inte ett stort hopp.
Vi kan fortfarande söka igenom genom att bara framåt från början till slut.
Vi kan fortfarande skapa en nod ur tunn luft, ungefär samma sätt.
Vi kan ta bort listor ganska ungefär på samma sätt också.
De enda saker som är subtilt annorlunda,
verkligen, sätter nya noder i listan,
och vi kommer slutligen tala om att ta bort en enda element från listan också.
Igen, ganska mycket de andra tre, vi är
kommer inte att tala om dem just nu eftersom de är bara
mycket små tweaks på de idéer diskuteras i enstaka bundna videolistan.
>> Så låt oss sätta en ny nod in i ett dubbelt-länkad lista.
Vi pratade om att göra detta för enskilt bundna listor samt,
men det finns ett par extra fångster med dubbel-länkade listor.
Vi är [? passerar?] i huvudet av lista här och några godtyckligt värde,
och vi vill få ny chef av förteckningen av denna funktion.
Det är därför det returnerar en dllnode stjärna.
Så vad är stegen?
De är, igen, mycket liknande att ensamma länkade listor
med ett extra tillägg.
Vi vill allokerar utrymme för en ny nod och kontroll för att se till att det är giltigt.
Vi vill fylla den noden upp med den information vi
vill sätta i det.
Det sista vi behöver do-- den extra sak som vi måste göra, rather--
är att fastställa föregående pekaren av den gamla chef för listan.
Kom ihåg att eftersom av dubbelt-länkade listor,
vi kan gå vidare och backwards-- vilka
betyder att varje nod som faktiskt pekar till två andra noder i stället för bara en.
Och så måste vi fixa den gamla chef på listan
att peka bakåt till ny chef för den länkade listan, vilket var något
Vi behövde inte göra innan.
Och som tidigare, vi bara tillbaka en pekare till ny chef för listan.
>> Så här är en lista.
Vi vill infoga 12 i den här listan.
Lägg märke till att diagrammet är något annorlunda.
Varje nod innehåller tre fields-- data och en nästa pekare i rött,
och en Föregående pekaren i blått.
Ingenting kommer före 15 noden, så dess Föregående pekare är noll.
Det är början av listan.
Det finns inget innan det.
Och ingenting kommer efter 10 noden, och så det är nästa pekare är noll också.
>> Så låt oss lägga 12 till denna lista.
Vi behöver [OHÖRBAR] utrymme för noden.
Vi lägger 12 inne i den.
Och sen igen, måste vi vara riktigt noga med att inte bryta kedjan.
Vi vill ordna pekare i rätt ordning.
Och ibland som kan mean-- som vi kommer att se särskilt
med delete-- att vi har några redundanta pekare, men det är OK.
>> Så vad vill vi göra först?
Jag skulle rekommendera saker du bör förmodligen
göra är att fylla pekare av 12 nod innan du rör någon annan.
Så vad är 12 kommer att peka på nästa?
15.
Vad kommer före den 12?
Ingenting.
Nu har vi fyllt extra information i 12
så det har Föregående, Nästa och värde.
>> Nu kan vi ha 15-- denna extra steg vi talade about-- vi
kan ha 15 poäng tillbaka till 12.
Och nu kan vi flytta chefen för länklistan också vara 12.
Så det är ganska likt det vi gjorde med ensamma-länkade listor,
med undantag för det extra steget att ansluter gamla chef på listan
tillbaka till ny chef för listan.
>> Nu äntligen bort en nod från en länkad lista.
Så låt oss säga att vi har någon annan funktion som
är att hitta en nod vi vill radera och har gett oss en pekare till exakt
noden som vi vill ta bort.
Vi vet inte ens need-- säga Huvudet är fortfarande globalt deklareras.
Vi behöver inte huvudet här.
Allt detta funktionen gör är att vi har hittade en pekare till exakt noden vi
vill bli av med.
Låt oss bli av med det.
Det är mycket enklare med dubbelt länkade listor.
First-- det är faktiskt bara ett par saker.
Vi behöver bara fixa det omgivande noder "pekare så att de hoppa över
noden vill vi ta bort.
Och då kan vi ta bort den noden.
Så återigen, vi bara gå igenom här.
Vi har uppenbarligen bestämt att Vi vill ta bort noden X.
Och återigen, vad jag gör här-- av way--
är ett allmänt fall för en nod som är i mitten.
Det finns ett par extra varningar som du
måste tänka på när du raderar början av listan
eller slutet av listan.
Det finns ett par special hörn fall att ta itu med det.
>> Så detta fungerar för att ta bort någon nod i mitten av den list-- en som
har ett legitimt pekare framåt och en legitim pekare bakåt,
legitima Föregående och Nästa pekare.
Återigen, om du arbetar med ändarna, du
behöver för att hantera de något annorlunda,
och vi kommer inte att prata om det nu.
Men du kan förmodligen räkna ut vad som behöver
göras bara genom att titta på den här videon.
>> Så vi har isolerat X. X är noden Vi vill ta bort från listan.
Vad gör vi?
Först måste vi ordna utanför pekare.
Vi måste ordna 9 nästa för att hoppa över 13
och pekar på 10-- som är vad vi just har gjort.
Och vi måste också ordna 10 s Föregående
att peka på 9 stället för att peka till 13.
>> Så återigen, var detta diagram för att börja med.
Detta var vår kedja.
Vi måste hoppa över 13, men vi måste också bevara
integriteten av listan.
Vi vill inte förlora någon informationen i endera riktningen.
Så vi behöver för att ordna pekarna noggrant
så att vi inte bryter kedjan alls.
>> Så vi kan säga 9 Next pekare pekar på samma ställe
att tretton Next pekaren pekar just nu.
Eftersom vi är så småningom kommer att vilja hoppa över 13.
Så var 13 poäng nästa, du vill nio peka dit istället.
Så det är det.
Och sedan överallt där 13 poäng tillbaka till allt som kommer före den 13,
vi vill 10 till punkt till att i stället för 13.
Nu märker, om du följer pilarna, kan vi släppa 13
utan att förlora någon information.
Vi har hållit integritet listan, flytta både framåt och bakåt.
Och då kan vi bara sorts av städa upp lite
genom att dra i listan tillsammans.
Så vi ordnas om pekare på vardera sidan.
Och sedan befriade vi X nod som innehöll 13,
och vi inte bryta kedjan.
Så vi gjorde bra.
>> Sist här på länkade listor.
Så både singly- och dubbelt bunden listor, som vi har sett,
stöd verkligen effektiv införing och borttagning av element.
Du kan ganska mycket göra den i konstant tid.
Vad gjorde vi måste göra för att ta bort ett element bara en sekund sedan?
Vi flyttade en pekare.
Vi flyttade en annan pekare.
Vi befriade X-- tog tre operationer.
Det tar alltid tre verksamheten till ta bort den node-- att befria en nod.
>> Hur ska vi sätta?
Tja, vi är bara alltid tacking på början
om vi sätter i ett effektivt sätt.
Så vi behöver rearrange-- beroende på om det är
en singly- eller dubbelbundna listan kan vi behöva göra tre
eller fyra operationer max.
Men återigen, det är alltid tre eller fyra.
Det spelar ingen roll hur många elementen är i vår lista,
det är alltid tre eller fyra operations-- precis som raderingen är alltid
tre eller fyra operationer.
Det är konstant tid.
Så det är riktigt bra.
>> Med arrayer, gjorde vi något liknande insättningssortering.
Ni minns säkert att inför sortera är inte en konstant tidsalgoritm.
Det är faktiskt ganska dyrt.
Så det här är en mycket bättre för införande.
Men som jag nämnde i enskilt-länkad lista video,
vi har en avigsida här också, eller hur?
Vi har förlorat förmågan att slumpmässigt tillgång element.
Vi kan inte säga, jag vill elementnummer fyra eller elementnummer 10 av en länkad lista
på samma sätt som vi kan göra det med en array
eller vi kan bara direkt index i vår samling är element.
>> Och så försöker hitta en elementet i en länkad list--
Om du söker är important-- Nu kan ta linjär tid.
Eftersom listan blir längre, det kan ta ett ytterligare steg
för varje enskilt element i listan i För att hitta det vi letar efter.
Så det finns kompromisser.
Det är lite av ett proffs och con inslag här.
>> Och dubbelt-länkade listor är inte sista typ av datastruktur kombination
att vi ska tala om, med all den grundläggande bygg
block av C en sätta ihop.
Eftersom i själva verket kan vi ens göra bättre än så här
att skapa en datastruktur som du skulle kunna söka igenom
i konstant tid också.
Men mer om det i en annan video.
>> Jag är Doug Lloyd.
Detta är CS50.