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