[Music kucheza] DOUG LLOYD: zote haki. Hivyo kama wewe tu kumaliza kwamba video katika orodha moja moja-zilizounganishwa pole Mimi kushoto wewe mbali juu ya kidogo ya cliffhanger. Lakini mimi nina furaha uko hapa kumaliza hadithi ya orodha doubly-wanaohusishwa. Hivyo kama unakumbuka kutoka kuwa video, sisi aliyesema kuhusu jinsi moja moja-zilizounganishwa orodha kufanya kuhudhuria uwezo wetu kukabiliana na maelezo ambapo idadi ya vipengele au idadi ya vitu katika orodha inaweza kukua au kuogopa. Sasa tunaweza kukabiliana na kitu kama hicho, ambapo sisi hakuweza kukabiliana nayo na arrays. Lakini hawana wanakabiliwa na moja kiwango cha juu muhimu ambayo ni kwamba pamoja na mmoja--wanaohusishwa orodha, tunaweza milele tu hoja katika mwelekeo mmoja kupitia orodha. Na hali halisi tu ambapo ambazo zinaweza kuwa tatizo Ilikuwa wakati sisi walikuwa wakijaribu kufuta kipengele moja. Na hatukuwa hata kujadili jinsi ya kufanya hivyo katika orodha moja moja-zilizounganishwa katika pseudocode. Ni hakika doable, lakini inaweza kuwa kidogo ya Hassle. Hivyo kama wewe mwenyewe kupata katika hali ambapo wewe ni kujaribu kufuta mambo moja kutoka kwenye orodha au ni kwenda inatakiwa kuwa wewe utakuwa kufuta mambo moja kutoka orodha, unaweza kutaka kufikiria kutumia mara mbili-wanaohusishwa orodha badala ya orodha moja moja-zilizounganishwa. Kwa sababu orodha doubly-wanaohusishwa kuruhusu kwa hoja mbele na nyuma wote kupitia orodha badala ya tu mbele kupitia list-- tu kwa kuongeza kipengele moja ya ziada kwa mfumo wetu ufafanuzi kwa mara mbili-wanaohusishwa orodha nodi. Tena, kama wewe si kwenda kwa kuwa kufuta vipengele moja kutoka list-- kwa sababu sisi ni kuongeza uwanja wa ziada kwa mfumo wetu ufafanuzi, nodes wenyewe kwa orodha doubly-wanaohusishwa ni kwenda kuwa kubwa. Wao ni kwenda kuchukua up ka zaidi ya kumbukumbu. Na hivyo kama hii si kitu wewe ni kwenda haja ya kufanya, unaweza kuamua ni si thamani biashara mbali kwa kuwa na kutumia ziada ka ya kumbukumbu inahitajika kwa orodha doubly-wanaohusishwa kama wewe si kwenda kuwa kufuta mambo moja. Lakini wao uko pia baridi kwa mambo mengine pia. Hivyo kama nilivyosema, sisi tu na kuongeza shamba moja ili mfumo wetu definition-- wazo hili ya pointer Kabla. Hivyo, pamoja na orodha moja moja-zilizounganishwa, sisi kuwa na thamani na ujao pointer, hivyo orodha doubly-wanaohusishwa tu ana njia ya hoja nyuma pia. Sasa katika moja moja-zilizounganishwa orodha ya video, sisi aliyesema kuhusu hizi ni tano ya mambo kuu unahitaji kuwa uwezo wa kufanya kazi na orodha wanaohusishwa. Na kwa zaidi ya haya, ukweli kuwa ni orodha doubly-wanaohusishwa ni kweli si kuruka kubwa. Bado tunaweza kutafuta njia na tu kusonga mbele kuanzia mwanzo hadi mwisho. Bado tunaweza kujenga nodi nje ya hewa nyembamba, pretty much njia hiyo hiyo. Tunaweza kufuta orodha pretty njia ile ile pia. Mambo tu kwamba ni subtly tofauti, kweli, ni kuingiza nodes mpya katika orodha, na tutaweza hatimaye majadiliano juu ya kufuta kipengele moja kutoka kwenye orodha pia. Tena, pretty much wengine watatu, tuko si kwenda kuzungumza kuhusu wao sasa hivi kwa sababu wao ni tu tweaks madogo sana juu ya mawazo yaliyojadiliwa katika moja moja-zilizounganishwa orodha video. Basi hebu kuingiza nodi mpya ndani ya orodha doubly-wanaohusishwa. Kuongelea kufanya hivyo kwa mmoja--wanaohusishwa orodha kama vizuri, lakini kuna michache ya ziada upatikanaji wa samaki na orodha doubly-wanaohusishwa. Tuko [? kupita?] katika kichwa cha orodha hapa na baadhi thamani holela, na tunataka kupata kichwa mpya ya orodha nje ya kazi hii. Hiyo ni kwa nini kuirudisha nyota dllnode. Hivyo hatua ni nini? Wao ni, tena, ni sawa kwa moja moja-zilizounganishwa orodha na kuongeza moja ya ziada. Tunataka kutenga nafasi kwa mwezi nodi na kuangalia kwa kuhakikisha ni halali. Tunataka kujaza kwamba nodi up kwa taarifa zozote sisi wanataka kuweka ndani yake. Jambo la mwisho tunahitaji do-- Jambo ziada tunahitaji kufanya, rather-- ni kurekebisha pointer Kabla ya kichwa na umri wa orodha. Kumbuka kwamba kwa sababu orodha ya mara mbili-wanaohusishwa, tunaweza kusonga mbele na backwards-- ambayo maana yake ni kwamba kila node kweli anasema kwa nodes nyingine mbili badala ya moja tu. Na hivyo tunahitaji kurekebisha kichwa zamani ya orodha kwa kumweka nyuma kwa mkuu mpya wa orodha wanaohusishwa, ambayo ilikuwa ni kitu hatukuwa na kufanya kabla. Na kama kabla, sisi tu kurudi pointer kwa mkuu mpya wa orodha. Hivyo hapa ni orodha. Tunataka kuingiza 12 katika orodha hii. Taarifa kwamba mchoro ni tofauti kidogo. Kila nodi ina tatu fields-- data, na pointer Next katika nyekundu, na pointer Kabla ya bluu. Kitu huja kabla ya 15 nodi, hivyo pointer wake Kabla ni null. Ni mwanzo wa orodha. Kuna kitu kabla yake. Na hakuna kitu huja baada ya 10 nodi, na hivyo ni Ifwatayo pointer ni null vilevile. Basi hebu kuongeza 12 kwa orodha hii. Tunahitaji [inaudible] nafasi kwa ajili ya nodi. Sisi kuweka 12 ndani yake. Na kisha tena, tunahitaji kuwa kweli makini kwa kuvunja minyororo. Tunataka upya kuyatumia katika mpangilio sahihi. Na wakati mwingine ambao unaweza mean kama tutaweza kuona hasa na delete-- kwamba sisi kufanya kuwa na baadhi kutokuwa na maana kuyatumia, lakini hiyo ni sawa. Basi je, tunataka kufanya kwanza? Napenda kupendekeza mambo unapaswa pengine kufanya ni kujaza kuyatumia ya 12 nodi kabla ya kugusa mtu yeyote mwingine. Kwa hiyo kile ni 12 kwenda kwa uhakika na baada ya hapo? 15. Nini huja kabla ya 12? Chochote. Sasa tumekuwa kujazwa maelezo ya ziada katika 12 hivyo ina Kabla, Next, na thamani. Sasa tunaweza kuwa 15-- hii ya ziada hatua sisi walikuwa wanazungumza about-- sisi unaweza kuwa na 15 hatua nyuma 12. Na sasa tunaweza kusonga kichwa cha orodha wanaohusishwa na pia kuwa 12. Hivyo ni pretty sawa na kile sisi walikuwa wakifanya na orodha moja moja-zilizounganishwa, isipokuwa kwa hatua za ziada ya kuunganisha kichwa na umri wa orodha nyuma kwa mkuu mpya wa orodha. Sasa hebu hatimaye kufuta nodi kutoka orodha wanaohusishwa. Hivyo hebu sema tuna baadhi ya kazi nyingine ambazo ni kutafuta nodi sisi unataka kufuta naye ametupa pointer hasa nodi kwamba tunataka kufuta. Hatuwezi hata need-- kusema kichwa bado ni duniani alisema. Hatuna haja ya kichwa hapa. Wote kazi hii ni kufanya ni tumekuwa kupatikana pointer nodi sisi hasa wanataka kujikwamua. Hebu kujikwamua ni. Ni rahisi sana kwa doubly-wanaohusishwa orodha. First-- ni kweli michache tu mambo. Sisi tu haja ya kurekebisha jirani nodes 'kuyatumia ili waweze ruka juu nodi sisi unataka kufuta. Na kisha tunaweza kufuta nodi. Hivyo tena, tunakwenda tu kupitia hapa. Tuna inaonekana aliamua kwamba tunataka kufuta nodi X. Na tena, nini mimi nina kufanya here-- na way-- ni kesi ya jumla kwa nodi ulio katikati. Kuna michache ya tahadhari za ziada kwamba wewe haja ya kufikiria wakati wewe ni kufuta mwanzo wa orodha au mwisho wa orodha. Kuna michache ya pekee kona kesi ya kukabiliana na pale. Hivyo hii kazi kwa kufuta nodi yoyote katikati ya moja list-- kwamba ina pointer halali mbele na pointer halali nyuma, halali Kabla na Next pointer. Tena, kama wewe ni kufanya kazi na mwisho, wewe haja ya kushughulikia wale kidogo tofauti, na sisi siyo kwenda kwa majadiliano juu ya kwamba sasa. Lakini pengine unaweza kufikiri nini mahitaji kufanywa tu kwa kuangalia hii video. Hivyo tumekuwa kutengwa X. X ni nodi tunataka kufuta kutoka kwenye orodha. Tufanye nini? Kwanza, tunahitaji upya nje kuyatumia. Tunahitaji upya 9 ya karibu na ruka juu 13 na hatua kwa 10-- ambayo ni kile ambacho tumefanya tu. Na sisi pia haja ya upya 10 wa awali kwa uhakika na 9 badala ya akizungumzia 13. Hivyo tena, hii ilikuwa mchoro kuanza na. Hii ilikuwa ni mlolongo wetu. Tunahitaji ruka juu 13, lakini tunahitaji pia kuhifadhi uadilifu wa orodha. Hatutaki kupoteza yoyote habari katika mwelekeo aidha. Kwa hiyo, tunahitaji upya kuyatumia kwa uangalifu hivyo hatuna kuvunja minyororo wakati wote. Hivyo tunaweza kusema 9 Next pointer anazungumzia sehemu moja kuwa kumi na tatu Next pointer anasema hivi sasa. Kwa sababu tuko hatimaye atataka ruka juu 13. Hivyo popote pointi 13 ijayo, wanataka tisa kwa uhakika kuna badala yake. Hivyo hiyo ni kwamba. Na kisha popote pointi 13 nyuma kwa, chochote huja kabla ya 13, tunataka 10 kwa uhakika kwa kuwa badala ya 13. Sasa angalia, kama wewe kufuata mishale, tunaweza kuacha 13 bila ya kweli ya kupoteza taarifa yoyote. Tumekuwa naendelea uadilifu wa orodha, kusonga wote mbele na nyuma. Na kisha tunaweza aina tu ya safi it up kidogo kwa kuunganisha orodha pamoja. Kwa hiyo sisi upya kuyatumia upande. Na kisha sisi huru X nodi kwamba zilizomo 13, na hatukuwa kuvunja minyororo. Hivyo tulifanya vizuri. Mwisho kumbuka hapa katika orodha wanaohusishwa. Hivyo wote singly- na doubly-wanaohusishwa orodha, kama tumeona, msaada kweli ufanisi kuingizwa na kufutwa kwa vipengele. Unaweza pretty much kufanya hivyo kwa wakati mara kwa mara. Je, sisi kufanya kufuta kipengele tu ya pili iliyopita? Sisi wakiongozwa pointer moja. Sisi wakiongozwa pointer mwingine. Sisi huru X-- alichukua shughuli tatu. Ni daima inachukua shughuli tatu kwa kufuta kwamba node-- kwa bure nodi. Je, sisi kuingiza? Naam, tuko tu siku zote bisho juu ya mwanzo kama sisi ni kuingiza kwa ufanisi. Kwa hiyo, tunahitaji rearrange-- kutegemea kama ni singly- au mara mbili-wanaohusishwa orodha, tupate haja ya kufanya tatu au shughuli nne max. Lakini tena, mara nyingi ni tatu au nne. Haijalishi jinsi wengi mambo ni katika orodha yetu, mara nyingi ni watatu au wanne operations-- kama kufutwa daima tatu au nne shughuli. Ni wakati wa mara kwa mara. Hivyo hiyo ni kubwa kweli kweli. Na arrays, tunafanya kitu kama kuingizwa aina. Pengine unakumbuka kwamba kuingizwa aina si mara kwa mara wakati algorithm. Ni kweli pretty ghali. Hivyo hii ni mengi zaidi kwa ajili ya kuingiza. Lakini kama nilivyoeleza katika mmoja--wanaohusishwa orodha video, sisi tumepewa upande wa chini hapa pia, sawa? Tumekuwa kupoteza uwezo wa nasibu kupata vipengele. Hatuwezi kusema, nataka kipengele namba nne au kipengele namba 10 ya orodha wanaohusishwa njia ile ile ambayo tunaweza kufanya hivyo kwa safu au tunaweza tu moja kwa moja ripoti ndani ya kipengele safu yetu. Na hivyo kujaribu kupata kipengele katika list-- wanaohusishwa kama kutafuta ni important-- Huenda sasa kuchukua muda linear. Kama orodha anapata tena, ni inaweza kuchukua hatua moja zaidi kwa kila kipengele moja katika orodha katika Ili kupata nini sisi ni kuangalia kwa. Hivyo kuna awamu ya pili ya biashara. Kuna kidogo ya wanaounga mkono na con kipengele hapa. Na orodha doubly-wanaohusishwa si aina ya mwisho ya muundo wa data macho kwamba tutaweza majadiliano juu, kuchukua jengo yote ya msingi vitalu ya C kuweka pamoja. Kwa sababu kwa kweli, tunaweza hata kufanya vizuri zaidi kuliko huu kujenga muundo data kwamba unaweza kuwa na uwezo wa kutafuta njia ya katika wakati mara kwa mara pia. Lakini zaidi juu ya kwamba katika video nyingine. Mimi nina Doug Lloyd. Hii ni CS50.