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