>> [Muzikos grojimo]
Doug LLOYD: Visos dešinę.
Taigi, jei jūs ką tik baigė, kad Vaizdo atskirai susijusių sąrašus atsiprašau
Aš palikau tave off tiek iš Įspūdingos filmą.
Bet aš džiaugiuosi esate čia baigti iš dvigubai susijusių sąrašus istorija.
>> Taigi, jei jūs prisimenate iš kad vaizdo, mes kalbėjome
apie tai, kaip atskirai susietų sąrašai padaryti dalyvauti mūsų gebėjimą
susidoroti su informacijos kur daugybė elementų
arba daiktų skaičius sąrašas gali augti arba mažėti.
Dabar mes galime susidoroti su kažkas panašaus, kad, kai
mes negalėjo susidoroti su juo su matricomis.
>> Bet jie kenčia nuo vieno kritiškai apribojimas, kuris
yra tai, kad su pavieniui susietų sąrašas, mes galime tik kada nors perkelti
viena kryptimi per sąrašo.
Ir tik reali situacija kai tai gali tapti problema
buvo, kai mes stengiamės ištrinti vieną elementą.
Ir mes net nebuvo aptarti, kaip tai padaryti į vieną susietos sąrašą Pseudocode.
Tai tikrai vykdytinas, tačiau jis gali būti šiek tiek vargo.
Taigi, jei jums rasti sau tokioje situacijoje, kai
Jūs bandote ištrinti Vienviečiai elementai iš sąrašo
arba ji vyksta būti reikalaujama kad jums bus ištrinti
Vienviečiai elementai iš sąrašas, galbūt norėsite
apsvarstyti naudojant dvigubai susietų sąrašą, o ne pavieniui susietos sąrašą.
Kadangi dvigubai susiję sąrašai leidžia jums judėti į priekį ir atgal abu
per vietoj sąrašą tik pirmyn per list--
tiesiog pridedant vieną papildomą elementą mūsų struktūros apibrėžimą
už dvigubai susiję sąrašas mazgas.
>> Vėlgi, jei jūs nesiruošia būti ištrinti atskirus elementus
nuo list--, nes mes įtraukiame papildomas laukas mūsų struktūra
apibrėžimas, patys mazgai už dvigubai susijusių sąrašus
ketinate būti didesnis.
Jie ketina imtis iki daugiau baitų atminties.
Ir todėl, jei tai nėra kažkas jūs ketinate reikia padaryti,
jūs galite nuspręsti, kad tai neverta kompromisą
turėti išleisti papildomų baitųatminties reikalingas
už dvigubai susietą sąrašą, jei nesate bus ištrinant pavienius elementus.
Bet jie taip pat kietas kitų dalykų taip pat.
>> Taigi, kaip jau sakiau, mes tiesiog pridėti vienas lauke mūsų struktūra
definition-- šią sąvoką ankstesnio rodyklę.
Taigi su atskirai susietos sąrašą, mes turi vertę ir kitą rodyklę,
todėl dvigubai susietų sąrašas tiesiog turi būdas judėti atgal, taip pat.
>> Dabar atskirai susietų Sąrašas vaizdo, mes kalbėjome
apie tai yra penki iš Pagrindiniai dalykai, kuriuos reikia
gali padaryti dirbti su susijusių sąrašus.
Ir dauguma šių, tuo kad tai dvigubai susietų sąrašas
tikrai nėra didelis šuolis.
Mes vis dar galite ieškoti tiesiog juda į priekį nuo pradžios iki pabaigos.
Mes vis dar galime sukurti mazgas iš plonas oro, beveik tas pats kelias.
Mes galime ištrinti sąrašus gana tas pats per daug.
Vieninteliai dalykai, kurie yra subtiliai skiriasi,
tikrai, yra įterpiant naujus mazgus į sąrašą,
ir mes pagaliau kalbėti apie išbraukiant vienas elementas iš sąrašo, taip pat.
Vėlgi, gana daug kiti trys, mes
nesiruošia kalbėti apie juos dabar, nes jie tiesiog
labai nedideli patobulinimai apie idėjas aptarti į vieną susietos sąrašo video.
>> Taigi leiskite įterpti naują viršūnę į dvigubai susietą sąrašą.
Mes kalbėjome apie tai daryti atskirai susietų sąrašus, taip pat,
bet ten yra papildoma pora pagauna su dvigubai susijusių sąrašus.
Mes [? artimųjų?] į galvą sąrašas čia, o kai savavališkai vertė,
ir mes norime gauti naują galvą išeinamajame šios funkcijos sąrašą.
Štai kodėl ji grąžina dllnode žvaigždė.
Taigi, kas yra žingsniai?
Jie yra, vėl, labai panašios į vieną susietų sąrašus
su vienu papildomu to.
Mes norime, kad skiria erdvę nauja mazgas ir įsitikinkite, kad jis galioja.
Mes norime užpildyti šią mazgas iki su kokia informacija, kurią mes
norite įdėti į jį.
Paskutinis dalykas, kurį mes turime do-- Papildomas dalykas, mes turime daryti, rather--
yra nustatyti Ankstesnis žymiklį senosios galvos sąrašo.
Atminkite, kad, nes iš dvigubai susiję sąrašus,
mes galime judėti į priekį ir backwards-- kuris
reiškia, kad kiekvienas mazgas iš tikrųjų nurodo kitų dviejų mazgų, o ne tik vieną.
Ir todėl mes turime nustatyti senas vadovas sąrašo
atkreipti atgal į naują vadovas susietą sąrašą, kuris buvo kažkas
mes neturėjome padaryti anksčiau.
Ir, kaip ir anksčiau, mes tiesiog grįžti žymiklį į naują galvos sąrašo.
>> Taigi čia sąrašas.
Mes norime įterpti 12 į šį sąrašą.
Atkreipkite dėmesį, kad schema yra šiek tiek kitoks.
Kiekvienas mazgas yra trys fields-- duomenys, o Kitas žymeklis raudonai,
ir Ankstesnis žymeklis mėlynai.
Nieko ateina prieš 15 mazgas, todėl jos Ankstesnis žymeklis yra niekinis.
Tai iš sąrašo pradžioje.
Nėra nieko prieš jį.
Ir nieko ateina po 10 mazgą ir todėl Toliau žymeklis yra niekinis, taip pat.
>> Taigi leiskite pridėti 12 prie šio sąrašo.
Mums reikia [nesigirdi] erdvės mazgo.
Mes įdėti 12 viduje ji.
Ir tada vėl, mes turime būti labai atsargūs, ne nutraukti grandinę.
Mes norime pertvarkyti rodykles teisinga tvarka.
Ir kartais, kad gali mean-- kaip mes ypač pamatyti
su delete--, kad mes turime kai nereikalingas patarimų, bet tai normalu.
>> Taigi, ką mes norime padaryti pirmiausia?
Norėčiau rekomenduoti Ką reikia tikriausiai
padaryti yra užpildyti iš 12 patarimų mazgas prieš paliesti kas nors kitas.
Taigi, kas yra 12 ketina atkreipti dėmesį į toliau?
15.
Kas ateina anksčiau 12?
Nieko.
Dabar mes užpildyta Papildomas informacija 12
todėl ji turi Ankstesnis Toliau, ir vertę.
>> Dabar mes galime turėti 15-- šis papildomas žingsnis mes kalbame about-- mes
gali turėti 15 punktą atgal į 12.
Ir dabar mes galime judėti į galvą susietą sąrašą taip pat 12.
Taigi tai gana panašus į tai, ką mes veikėte su atskirai susijusių sąrašus,
išskyrus papildomą žingsnį jungiantis senąjį galvą sąrašo
atgal į naujos galvos sąrašo.
>> Dabar galime pagaliau ištrinti mazgas iš susietos sąrašą.
Taigi tarkime, mes turime kai kitas funkcijas,
yra rasti mazgas mes norime ištrinti ir davė mums žymeklį tiksliai
mazgas, kad mes norime ištrinti.
Mes net need-- pasakyti galva vis dar yra pasaulyje deklaruoti.
Mums nereikia galvą čia.
Visa tai funkcija daro tai mes rado žymeklį tiksliai mazgas mes
norite atsikratyti.
Leiskite atsikratyti jos.
Tai daug lengviau su dvigubai susijęs sąrašus.
First-- tai tikrai tik pora dalykų.
Mes tiesiog reikia nustatyti aplinkinių mazgai "patarimų, kad jie praleisti
mazgas norime ištrinti.
Ir tada mes galime ištrinti tą mazgą.
Taigi dar kartą, mes tiesiog išgyvena čia.
Mes, matyt, nusprendė, kad mes norime ištrinti mazgo X
Ir vėl, ką aš daro here-- pagal way--
yra bendras atveju dėl mazgas, kad yra viduryje.
Yra daug pora balsas įspėjimų, kad jūs
reikia apsvarstyti, kai jūs ištrinti pati pradžia sąrašo
arba labai galas sąrašo.
Yra specialios pora kampiniai atvejai susidoroti su ten.
>> Taigi tai veikia išbraukusi visą mazgą viduryje į list-- vienas, kad
turi teisėtą žymeklį į priekį ir teisėtas žymeklis atgal,
teisėtas Ankstesnių ir ateinančių žymeklis.
Vėlgi, jei jūs dirbate su galuose, jums
reikia tvarkyti tuos šiek tiek kitaip,
ir mes neketiname kalbėti apie tai dabar.
Bet jūs tikriausiai galite išsiaiškinti, ką reikia
būti padaryta tiesiog žiūrėti šį vaizdo įrašą.
>> Taigi mes izoliuoti X. X yra mazgas mes norime ištrinti iš sąrašo.
Ką mes darome?
Pirma, mums reikia pertvarkyti Išorinės patarimų.
Mums reikia pertvarkyti 9 artimiausi praleisti per 13
ir taškas 10-- kuris yra tai, ką mes ką tik padaryti.
Ir mes taip pat turime pertvarkyti 10 ankstesnės
atkreipti 9 vietoj nukreipta į 13.
>> Taigi dar kartą, tai buvo Diagramoje pradėti.
Tai buvo mūsų grandinė.
Turime praleisti 13 bet mes turime taip pat išsaugoti
iš sąrašo vientisumą.
Mes nenorime prarasti bet informacija bet kuria kryptimi.
Taigi mums reikia pertvarkyti Į patarimų atidžiai
todėl mes negalime nutraukti grandinę ne visiems.
>> Taigi, mes galime pasakyti, 9 Next žymiklį nurodo į tą pačią vietą
kad trylikos Next rodyklė nurodo dabar.
Kadangi mes galų gale ketinate norite praleisti 13.
Taigi, kur 13 taškų Toliau, jums noriu devyni vietoj atkreipti ten.
Taigi tai, kad.
Ir tada, kur 13 taškų atgal kad, nepaisant ateina prieš 13
mes norime 10 taškas į tas, kad vietoj 13.
Dabar pastebėsite, jei jums sekti strėlės, mes galime nukristi 13
be faktiškai praranda bet kokią informaciją.
Mes įnirtingai sąrašo vientisumą, juda pirmyn ir atgal.
Ir tada mes galime tiesiog tarsi nuo išvalyti jį truputį
traukiant sąrašą kartu.
Taigi, mes pertvarkytas patarimų iš abiejų pusių.
Ir tada mes išlaisvino X mazgas, kad pateiktos 13,
ir mes nenutraukė grandinę.
Taigi mes padarėme gerai.
>> Paskutinė pastaba čia susijusius sąrašus.
Taigi tiek singly- ir dvigubai susietų sąrašus, kaip mes matėme,
parama tikrai efektyvus įterpimo ir išbraukta iš elementų.
Jūs galite labai daug padaryti jis nuolat laiko.
Ką mes turime daryti, kad ištrinti elementas tik prieš antros?
Mes persikėlė vieną žymeklį.
Mes persikėlė kitą žymeklį.
Mes išlaisvino X-- paėmė tris operacijas.
Jis visada trunka tris operacijas į ištrinti tą node-- nemokamai mazgas.
>> Kaip mes įterpti?
Na, mes tiesiog visada Spręsti pradžioje
jei mes įdėti efektyviai.
Taigi, mes turime rearrange-- priklausomai, jei tai
singly- arba dvigubai susietų sąrašą, gali tekti padaryti tris
ar keturis operacijos maks.
Bet vėl, tai visada trys ar keturi.
Nesvarbu, kiek elementai yra mūsų sąraše,
tai visada trys ar keturi operations-- kaip išbraukta visada
trys ar keturi operacijos.
Tai pastovus laikas.
Taigi tai tikrai puikus.
>> Su masyvų, mes darome kažkas panašaus įterpimo rūšiuoti.
Jūs tikriausiai prisimena, kad įterpimą rūšiuoti nėra pastovus laikas algoritmas.
Tai tikrai gana brangus.
Taigi tai yra daug geriau įterpti.
Bet, kaip minėjau atskirai susietų sąrašas vaizdo įrašą,
mes turime trūkumų čia pat, tiesa?
Mes prarado gebėjimą atsitiktinai prieiti elementų.
Mes negalime pasakyti, noriu elementas Number Four ar elementas skaičius 10 susietą sąrašą
taip pat, kad mes galime padaryti, kad masyvo
ar mes galime tik tiesiogiai puslapis į mūsų masyvas anketa elementas.
>> Ir taip bando rasti elementas, susietą list--
jei paieška important-- dabar gali imtis linijinį laiką.
Kadangi sąrašas pailgėja, tai gali užtrukti vieną papildomą žingsnį
už kiekvieną elementą sąraše tam kad rasti ką mes ieškome.
Taigi prekybos kompromisai.
Yra daug pro tiek ir pa elementas čia.
>> Ir dvigubai susiję sąrašai nėra paskutinis rūšies duomenų struktūros derinys
kad mes kalbame apie, atsižvelgiant į visus pagrindinius pastatą
blokai C komponavimas.
Nes iš tiesų, mes galime net padaryti geriau nei tai
sukurti duomenų struktūrą, kuri Jums gali būti suteikta galimybė ieškoti
nuolat laiko taip pat.
Bet daugiau apie tai kitoje vaizdo.
>> Aš Doug Lloyd.
Tai CS50.