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