[Daqq tal-mużika] Doug LLOYD: Kull dritt. Mela jekk inti lest li biss video fuq il-listi weħidhom marbuta sorry I xellug inti off fuq daqsxejn ta 'cliffhanger. Imma ninsab kuntenta int hawn biex jintemm l-istorja ta 'listi doppjament marbuta. 

Mela jekk inti recall minn li l-video, tkellimna dwar kif weħidhom-linked listi do jattendu l-abbiltà tagħna jittrattaw informazzjoni fejn in-numru ta 'elementi jew in-numru ta 'oġġetti fil lista tista 'tikber jew tiċkien. Aħna issa tista 'tittratta xi ħaġa bħal dik, fejn aħna ma setgħetx tittratta magħha l arrays. 

Iżda dawn isofru minn waħda limitazzjoni kritika li huwa li bil--linked weħidhom lista, nistgħu biss qatt timxi f'direzzjoni waħda permezz tal-lista. U l-unika sitwazzjoni reali fejn dak jista 'jsir problema kien meta konna jippruvaw tħassar element wieħed. U aħna lanqas biss jiddiskutu kif jagħmlu dan f'lista weħidhom-linked fil pseudocode. Huwa ċertament doable, iżda tista 'tkun daqsxejn ta' battikata. Mela jekk issib ruħek f'sitwazzjoni fejn int tipprova li jitħassar elementi singoli mil-lista jew li għaddej biex jkun meħtieġ li inti ser tkun tħassar elementi singoli mill il-lista, inti tista 'tixtieq li tikkunsidra tuża 'marbut doppjament lista minflok ta 'lista waħedhom-linked. Minħabba listi doppjament marbuta jippermetti li inti timxi kemm quddiem u lura permezz tal-lista minflok biss quddiem permezz tal-list-- biss billi jżid element wieħed addizzjonali definizzjoni istruttura tagħna għall-node lista doppjament-linked. 

Għal darb'oħra, jekk int mhux ser jiġu tħassar elementi singoli mill-list-- għaliex aħna qed żżid qasam extra għall-istruttura tagħna definizzjoni, il-lymph infushom għal listi doppjament marbuta ser ikunu akbar. Huma qed tmur biex tieħu up aktar bytes ta 'memorja. U għalhekk jekk dan mhux xi ħaġa int ser bżonn tagħmel, inti tista 'tiddeċiedi li huwa ma jiswew il-kummerċ off ikollhom jonfqu l-extra bytes ta 'memorja meħtieġa għal lista doppjament-linked jekk int ma se tkun tħassar elementi singoli. Iżda dawn qed wkoll jibred għal affarijiet oħra wkoll. 

So kif għidt, aħna biss għandhom iżidu Qasam wieħed għall-istruttura tagħna definition-- dan il-kunċett ta 'pointer Preċedenti. Allura ma 'lista waħdu-linked, aħna jkollu l-valur u l-pointer Sussegwentement, sabiex il-lista doppjament-linked biss għandu mod li jiċċaqalqu lura kif ukoll. 

Issa fil-weħidhom-linked video lista, tkellimna dwar dawn huma ħamsa l- affarijiet ewlenin li għandek bżonn biex tkun kapaċi tagħmel biex jaħdmu ma 'listi marbuta. U għal ħafna minn dawn, il-fatt li huwa lista doppjament-linked mhuwiex verament qabża kbira. Aħna xorta tista 'tfittex permezz bi ftit miexja 'l quddiem mill-bidu sat-tmiem. Aħna xorta jistgħu joħolqu node minn arja irqiq, pjuttost l-istess mod. Aħna tista 'tħassar listi pretty ħafna bl-istess mod wisq. L-uniċi affarijiet li huma sottili differenti, tassew, huma inseriti lymph ġodda fil-lista, u aħna ser finalment nitkellmu dwar tħassir element wieħed mil-lista kif ukoll. Għal darb'oħra, pretty ħafna l-tlieta l-oħra, aħna qed mhux ser jitkellmu dwarhom dritt issa għaliex qed biss tweaks minuri ħafna dwar l-ideat diskussi fil-video lista waħedhom-linked. 

Mela ejja daħħal node ġdid fi lista doppjament-linked. Aħna tkellimna dwar kif isir dan għal listi weħidhom-linked kif ukoll, iżda hemm koppja ta 'extra qabdiet ma 'listi doppjament marbuta. Aħna [? tgħaddi?] fir-ras tal- lista hawn u xi valur arbitrarja, u aħna rridu nġibu l-kap il-ġdid tal-lista minn din il-funzjoni. C'est pourquoi dan jirritorna stilla dllnode. Allura x'inhuma l-passi? Dawn huma, għal darb'oħra, simili ħafna għal listi weħidhom-linked b'żieda waħda żejda. Aħna rridu li talloka spazju għal ġdida node u jivverifika sabiex ikun ċert li huwa validu. Aħna rridu li timla dik node up kwalunkwe informazzjoni li għandna tixtieq li tqiegħed fiha. L-aħħar ħaġa li għandna bżonn biex do-- l Ħaġa extra rridu nagħmlu, rather-- huwa li jiffissaw l-pointer Preċedenti tal-kap antika tal-lista. Ftakar li minħabba listi ta doppjament marbuta, nistgħu nimxu 'l quddiem u backwards-- li ifisser li kull node fil-fatt punti għal żewġ punti strateġiċi oħrajn minflok waħda biss. U għalhekk għandna bżonn biex jiffissaw il-kap antika tal-lista għall-punt lura għall-kap il-ġdid tal il-lista marbuta, li kienet xi ħaġa aħna ma għandek tagħmel qabel. U bħal qabel, aħna biss ritorn pointer għall-kap il-ġdid tal-lista. 

Allura hawnhekk lista. Aħna rridu li daħħal 12 fil din il-lista. Avviż li l-dijagramma hija kemmxejn differenti. Kull node fih tliet fields-- data, u werrej li Jmiss fil aħmar, u werrej li qabel blu. Xejn jasal quddiem il-node 15, hekk pointer Preċedenti tagħha huwa null. Hu l-bidu tal-lista. M'hemm xejn quddiemha. U xejn jiġi wara l-node 10, u dan huwa pointer li jmiss huwa null ukoll. 

Mela ejja żid 12 sa din il-lista. Għandna bżonn [inaudible] spazju għall-node. Npoġġux 12 ġewwa ta 'dan. U mbagħad, għandna bżonn biex ikunu verament attent li ma jiksru l-katina. Aħna rridu li rranġati mill-ġdid l- pointers fl-ordni korretta. U xi kultant li jistgħu mean-- kif Ser naraw partikolarment ma delete-- li nagħmlu jkollhom xi pointers żejda, iżda li OK. 

Mela xi do rridu nagħmlu ewwel? I jirrakkomanda l- affarijiet inti għandek probabbilment jagħmlu huma biex timla l-pointers tal-12 node qabel inti touch ħaddieħor. Allura x'inhu 12 se punt li jmiss? 15. Dak li jiġi qabel it-12? Xejn. Issa konna mimlija l- informazzjoni addizzjonali fi 12 għalhekk għandha Preċedenti, Sussegwentement, u l-valur. 

Issa nistgħu jkollhom 15-- dan extra pass konna nitkellmu about-- aħna jista 'jkollhom 15 punt lura sa 12. U issa nistgħu jimxu l-kap ta ' il-lista marbuta li wkoll ikunu 12. Allura huwa pjuttost simili għal dak li aħna kienu qed jagħmlu ma 'listi waħdu marbuta, ħlief għall-grad iżjed ta ' jgħaqqdu l-kap antika tal-lista Lura għall-kap il-ġdid tal-lista. 

Issa ejja finalment ħassar node minn lista marbuta. Mela ejja ngħidu li għandna xi funzjoni oħra li qed issib node aħna tixtieq li tħassar u tatna pointer għal eżattament l node li aħna tixtieq li tħassar. Aħna lanqas biss need-- jiġifieri l- ras għadu globalment iddikjarat. M'għandniex bżonn ras hawn. Kollha din il-funzjoni qed tagħmel hija aħna ħadthom sabet pointer għal eżattament l-node aħna tixtieq li jeħles ta '. Ejja jeħles minnu. Huwa ħafna aktar faċli ma listi doppjament-linked. First-- huwa attwalment biss ftit affarijiet. Jinħtieġ li tiffissa l-madwar pointers nodi "sabiex ikunu skip fuq l node irridu li tħassar. U allura nistgħu tħassar dik node. Għalhekk għal darb'oħra, aħna qed biss jmorru permezz ta 'hawn. Aħna apparentement iddeċidiet li irridu li jitħassar il-X. node U għal darb'oħra, dak li jien tagħmel here-- mill-way-- huwa każ ġenerali għal node li huwa fin-nofs. Hemm ftit ta ' caveats żejda li inti bżonn li jiġi kkunsidrat meta qed jitħassru -bidu nett tal-lista jew l-aħħar nett tal-lista. Hemm ftit speċjali każijiet kantuniera biex jittrattaw hemmhekk. 

Allura dan jaħdem għal tħassar kwalunkwe node fin-nofs tal-wieħed list-- li għandha pointer leġittimu quddiem u pointer leġittimu lura, Preċedenti u li jmiss pointer leġittimu. Għal darb'oħra, jekk int taħdem bit-trufijiet, inti bżonn biex jimmaniġġaw dawk kemmxejn differenti, u aħna mhux qed tmur biex jitkellmu dwar dan issa. Imma int tista 'probabbilment ċifra barra dak li jeħtieġ li jsir biss billi jaraw dan il-video. 

Allura konna iżolati X. X huwa l-node aħna tixtieq li tħassar mil-lista. X'nagħmlu? L-ewwel, għandna bżonn li rranġati mill-ġdid l pointers barra. Għandna bżonn li rranġati mill-ġdid 9 Next biex skip fuq 13 u l-punt li 10-- li huwa dak li aħna ħadthom biss isir. U jeħtieġ ukoll li rranġati mill-ġdid 10 Preċedenti għall-punt sa 9 minflok tipponta lejn 13. 

Għalhekk għal darb'oħra, din kienet l- dijagramma biex jibdew bihom. Dan kien katina tagħna. Għandna bżonn li skip fuq 13, iżda għandna bżonn li tippriserva wkoll l-integrità tal-lista. Aħna ma jridux jitilfu xi informazzjoni f'kull direzzjoni. Għalhekk għandna bżonn li rranġati mill-ġdid l pointers b'attenzjoni hekk aħna ma jqassmux il-katina fil-livelli kollha. 

Allura nistgħu ngħidu 9 ta pointer li jmiss jinnota l-istess post li tlettax Next pointer punti dritt issa. Għaliex aħna qed eventwalment tmur jridu skip fuq 13. Allura fejn 13-il punt li jmiss, inti tixtieq disa punt hemmhekk minflok. Allura dak li. U mbagħad kull fejn 13-il punt lura li, tkun xi tkun taqa qabel it-13, irridu 10 punt li li minflok 13. Issa avviż, jekk inti ssegwi l-vleġeġ, nistgħu qatra 13 mingħajr ma attwalment ma jitilfu xi informazzjoni. Imxejna miżmuma l-integrità tal-lista, miexja kemm quddiem u lura. U allura nistgħu biss sort tal inaddfu up ftit billi tiġbed il-lista flimkien. Allura aħna rranġat mill-ġdid l- pointers fuq kull naħa. U allura aħna meħlusa X l node dik li tinsab 13, u aħna ma jiksru l-katina. Allura għamilna tajjeb. 

Nota finali hawn fuq listi marbuta. Allura kemm singly- u doppjament-linked listi, kif aħna stajt tidher, appoġġ inserzjoni verament effiċjenti u t-tħassir ta 'elementi. Tista 'pretty ħafna jagħmlu fil-ħin kostanti. What did għandna nagħmlu biex tħassar element ftit tieni ilu? Aħna mċaqalqa pointer wieħed. Aħna mċaqalqa pointer ieħor. Aħna meħlusa X-- ħadet tliet operazzjonijiet. Huwa dejjem jieħu tliet operazzjonijiet għall iħassar dik node-- li jeħles node. 

Kif nistgħu daħħal? Well, aħna qed biss dejjem klassifikazzjoni hija stabbilita fuq il-bidu jekk aħna qed ddaħħal effiċjenti. Għalhekk għandna bżonn li rearrange-- jiddependi fuq jekk huwa a singly- jew doppjament-linked lista, nistgħu bżonn tagħmel tliet jew erba 'operazzjonijiet max. Iżda għal darb'oħra, huwa dejjem tlieta jew erba '. Ma jimpurtax kemm elementi huma fil-lista tagħna, huwa dejjem tlieta jew erba operations-- bħad-tħassir huwa dejjem tlieta jew erba 'operazzjonijiet. Wasal iż-żmien kostanti. Allura dak verament kbir. 

Bil arrays, aħna kienu qed jagħmlu xi ħaġa bħal sort inserzjoni. You probabbilment tfakkar li inserzjoni sort mhix algoritmu żmien kostanti. Huwa fil-fatt pjuttost għoljin. Allura dan huwa ħafna aħjar biex ikunu inseriti. Imma kif semmejt fil- video lista waħdu-linked, konna ltqajna żvantaġġ hawnhekk ukoll, id-dritt? Imxejna tilfu l-kapaċità li saltwarjament aċċess elementi. Ma nistgħux ngħidu, nixtieq element numru erbgħa jew in-numru element 10 ta 'lista marbuta bl-istess mod li nistgħu tagħmel dan ma 'firxa jew nistgħu biss direttament indiċi fis element array tagħna. 

U hekk jippruvaw isibu element fil-list-- marbut jekk tiftix huwa important-- jistgħu b'hekk ħin lineari. Peress li l-lista gets itwal, dan jista 'jieħu pass addizzjonali wieħed għal kull element wieħed fil-lista fl Sabiex issib dak li aħna qed tfittex. Allura hemm kompromessi. Hemm daqsxejn ta 'pro u element con hawn. 

U listi doppjament li huma konnessi ma jkunux l- aħħar tip ta 'kombinazzjoni istruttura tad-data li aħna ser nitkellmu dwar, tieħu l-bini bażika blokki ta 'C' l-tqegħid flimkien. Minħabba fil-fatt, nistgħu anki tagħmel aħjar minn dan biex tinħoloq struttura data li inti tista 'tkun kapaċi li tfittex fi żmien kostanti wisq. Iżda aktar fuq li fil-video ieħor. 

Jien Doug Lloyd. Dan huwa CS50.