>> [M奴zikas atska艈o拧anai]
Doug LLOYD: Nu labi.
T膩tad, ja j奴s tikko beidzis, ka video par atsevi拧姆i saist墨tiem sarakstiem 啪膿l
Es atst膩ju j奴s off uz mazliet cliffhanger.
Bet es esmu priec墨gs j奴s esat 拧eit, lai pabeigtu st膩sts par divk膩rt saist墨tiem sarakstiem.
>> T膩tad, ja j奴s atceraties no ka video, m膿s run膩j膩m
par to, k膩 atsevi拧姆i piesaist墨to saraksti dar墨t apmekl膿t m奴su sp膿ju
lai izskat墨tu inform膩ciju kur vair膩ki elementi
vai vien墨bu skaits, kas sarakstu var augt un sarauties.
Tagad m膿s varam tikt gal膩 ar kaut k膩 t膩, kur
m膿s nevar膿tu tikt ar to gal膩 ar mas墨viem.
>> Bet vi艈i cie拧 no viena kritiska ierobe啪ojums, kas
ir t膩, ka ar atsevi拧姆i-linked sarakstu, m膿s varam tikai k膩dreiz p膩rvietot
tikai vien膩 virzien膩 caur sarakst膩.
Un vien墨gais re膩lais st膩voklis kur, kas var k募奴t par probl膿mu
bija, kad m膿s cen拧amies izdz膿st vienu elementu.
Un mums nav pat apspriest, k膩 to izdar墨t ar atsevi拧姆i piesaist墨ta sarakst膩 pseudocode.
Tas noteikti ir veicams, bet tas var b奴t mazliet par probl膿mu.
T膩tad, ja jums atrast sev situ膩cij膩, kad
j奴s m膿模in膩t izdz膿st vienviet墨gas elementi no saraksta
vai tas b奴s nepiecie拧ams ka jums tiks sv墨trojot
single elementi no saraksts, j奴s var膿tu v膿l膿ties,
apsv膿rt iesp膿ju izmantot divk膩rt saist墨ts uzskait墨t nevis atsevi拧姆i piesaist墨ta sarakst膩.
T膩 k膩 divk膩rt, kas saist墨ti saraksti 募auj jums lai p膩rvietotos gan uz priek拧u un atpaka募
caur sarakstu, nevis tikai uz priek拧u caur list--
vienk膩r拧i pievienojot vienu papildu elementu m奴su strukt奴ru defin墨ciju
par divk膩rt saist墨ts saraksta mezgl膩.
>> Atkal, ja j奴s neesat gatavojas tikt sv墨trot atsevi拧姆us elementus
No list-- jo m膿s pievienojot papildu lauks m奴su strukt奴ras
defin墨ciju, pa拧i mezgliem par divk膩rt saist墨tiem sarakstiem
gribam b奴t liel膩ks.
Vi艈i gatavojas veikt up vair膩k baiti atmi艈as.
Un t膩p膿c, ja tas nav kaut kas J奴s esat dodas uz nepiecie拧am墨bu to dar墨t,
j奴s var膿tu izlemt, tas ir nav v膿rts tirdzniec墨bas off
j膩t膿r膿 papildu atmi艈as baiti nepiecie拧ams
par divk膩rt saist墨ta sarakst膩, ja j奴s neesat b奴s sv墨trot atsevi拧姆us elementus.
Bet vi艈i ar墨 for拧s citas lietas p膩r膩k.
>> T膩tad k膩 jau teicu, mums vienk膩r拧i ir pievienot viena lauka uz m奴su strukt奴ras
definition-- 拧o j膿dzienu atkritumu iepriek拧膿j膩 r膩d墨t膩ju.
T膩tad ar atsevi拧姆i piesaist墨ta sarakst膩, m膿s ir v膿rt墨ba un n膩kamo r膩d墨t膩ju,
t膩p膿c divk膩rt saist墨ts saraksts vienk膩r拧i ir veids, k膩 virz墨ties atpaka募, k膩 ar墨.
>> Tagad atsevi拧姆i piesaist墨to saraksts video, m膿s run膩j膩m
par tiem ir pieci no Galven膩s lietas, jums ir nepiecie拧ams, lai b奴tu
sp膿j dar墨t, lai str膩d膩tu ar saist墨tiem sarakstiem.
Un liel膩k膩 da募a no 拧iem, uz to, ka tas ir divk膩rt saist墨ts saraksts
nav 墨sti liels l膿ciens.
M膿s joproj膩m varat p膩rl奴kot, tikai virz膩s uz priek拧u no s膩kuma l墨dz beig膩m.
M膿s joproj膩m varam izveidot mezglu 膩r膩 no zila gaisa, diezgan daudz pa拧膩 veid膩.
M膿s varam izdz膿st sarakstus diezgan daudz pa拧膩 veid膩 too.
Tikai lietas, kas ir smalki da啪膩di,
tie拧膩m, ir ievietojot jaunos punktus fani sarakst膩,
un m膿s beidzot run膩jam par dz膿拧anu viens elements no saraksta, k膩 ar墨.
Atkal, diezgan daudz p膩r膿jie tr墨s, m膿s
netaisos run膩t par t膩m ties墨bas tagad, jo vi艈i vienk膩r拧i
募oti nelielas tweaks par idej膩m apsprieda kas atsevi拧姆i saist墨taj膩 sarakst膩 video.
>> T膩tad pie艈emsim ievietot jaunu mezglu par divk膩rt saist墨ta sarakst膩.
M膿s run膩j膩m par to izdar墨t atsevi拧姆i piesaist墨t膩s sarakstus, k膩 ar墨,
bet tur ir p膩ris extra nozveju ar divk膩rt saist墨tiem sarakstiem.
M膿s esam [? iet?] galv膩 no uzskait墨t 拧eit un da啪i patva募墨gi v膿rt墨ba,
un m膿s gribam, lai sa艈emtu jaunu galvu saraksta 膩r膩 no 拧墨s funkcijas.
Tie拧i t膩p膿c tas atgrie啪 dllnode zvaigzni.
T膩tad, k膩di ir so募i?
Tie ir, atkal, 募oti l墨dz墨gs lai atsevi拧姆i piesaist墨t膩s saraksti
ar vienu papildu papildus.
M膿s v膿lamies, lai pie拧姆ir telpu jauna mezglu un p膩rbaude, lai p膩rliecin膩tos, ka tas ir der墨gs.
M膿s v膿lamies, lai ie艈emtu 拧o mezglu up ar k膩da inform膩cija mums
gribu, lai taj膩.
P膿d膿j膩 lieta, mums ir nepiecie拧ams, lai do-- extra lieta, kas mums j膩dara, rather--
ir noteikt Iepriek拧膿jais r膩d墨t膩ju no vec膩s galvas sarakst膩.
Atcerieties, ka t膩p膿c, ka divk膩rt piesaist墨to sarakstus,
m膿s varam virz墨ties uz priek拧u un backwards-- kas
noz墨m膿, ka katrs mezgls faktiski nor膩da ar diviem citiem mezgliem, nevis tikai vienu.
Un t膩p膿c mums ir nepiecie拧ams noteikt vecais vad墨t膩js saraksta
nor膩d墨t atpaka募 uz jauno vad墨t膩ju piesaist墨tais saraksts, kas bija kaut kas
mums nebija ko dar墨t pirms.
Un t膩pat k膩 iepriek拧, m膿s vienk膩r拧i atgriezt r膩d墨t膩ju uz jauno vad墨t膩ju sarakst膩.
>> T膩tad, 拧eit ir saraksts.
M膿s v膿lamies, lai ievietotu 12 拧aj膩 sarakst膩.
Iev膿rojiet, ka diagramma ir nedaudz at拧姆ir墨gs.
Katrs mezgls ir tr墨s fields-- dati, un Next r膩d墨t膩js sarkan膩 kr膩s膩,
un iepriek拧膿jais r膩d墨t膩js zil膩 kr膩s膩.
Nekas n膩k pirms 15 mezglu, t膩p膿c t膩s Iepriek拧膿jais r膩d墨t膩js ir nulle.
Tas ir s膩kums saraksta.
Tur nekas pirms t膩.
Un nekas n膩k p膿c 10 mezglu, un t膩p膿c tas ir N膩kamais r膩d墨t膩js ir nulle, k膩 ar墨.
>> T膩tad pie艈emsim pievienot 12 拧im sarakstam.
Mums ir nepiecie拧ams [dzirdams] telpu mezgl膩.
M膿s ieliekam 12 iek拧pus膿 no t膩.
Un tad atkal, mums ir nepiecie拧ams, lai b奴tu patiesi Uzmanieties, lai izjauktu 姆膿di.
M膿s v膿lamies, lai p膩rk膩rtotu nor膩des, kas pareiz膩 sec墨b膩.
Un reiz膿m tas var膿tu mean-- jo m膿s redz膿sim 墨pa拧i
ar delete-- ka mums ir da啪i lieks nor膩des, bet tas ir OK.
>> T膩tad, ko m膿s v膿lamies dar墨t vispirms?
Es ieteiktu lietas, jums ir iesp膿jams
dar墨t ir j膩aizpilda nor膩des no 12 mezgla pirms j奴s pieskarties k膩ds cits.
T膩tad, kas ir 12 gatavojas nor膩d墨t uz n膩kamo?
15.
Kas n膩k pirms 12?
Nekas.
Tagad m膿s esam piepilda papildu inform膩cija 12
t膩p膿c tas ir iepriek拧膿jo, n膩kamo, un v膿rt墨bu.
>> Tagad m膿s varam b奴t 15-- 拧o papildu solis m膿s run膩j膩m about-- m膿s
var b奴t 15 punktu atpaka募 uz 12.
Un tagad m膿s varam virz墨ties uz galvas piesaist墨tais saraksts b奴t ar墨 12.
T膩tad tas ir diezgan l墨dz墨gs tam, ko m膿s dar墨ja ar atsevi拧姆i saist墨tiem sarakstiem,
iz艈emot papildu soli savieno veco galvu saraksta
atpaka募 uz jauno galvas sarakst膩.
>> Tagad beidzot dz膿st mezglu no saist墨t膩 saraksta.
T膩tad pie艈emsim, ka mums ir da啪as citas funkcijas,
ir atrast mezglu m膿s v膿lamies, lai izdz膿stu un mums ir devis r膩d墨t膩ju tie拧i
mezglu, ka m膿s v膿lamies, lai izdz膿stu.
Mums nav pat need-- teikt galva joproj膩m vis膩 pasaul膿 pasludin膩ts.
Mums nevajag galvu 拧eit.
Visa 拧墨 funkcija dara, ir, m膿s esam konstat膿ja r膩d墨t膩ju uz tie拧i mezglu m膿s
v膿las atbr墨voties no.
Pie艈emsim atbr墨voties no t膩.
Tas ir daudz viegl膩k ar divk膩rt saist墨tas sarakstus.
First-- tas ir faktiski tikai p膩ris lietas.
Mums ir nepiecie拧ams, lai noteiktu apk膩rt膿jo mezgli "nor膩des, lai vi艈i izlaist
mezglu m膿s v膿lamies izdz膿st.
Un tad m膿s varam izdz膿st 拧o mezglu.
T膩tad v膿lreiz, m膿s esam tikai iet cauri 拧eit.
M膿s esam ac墨mredzot nol膿ma, ka m膿s v膿lamies, lai izdz膿stu mezglu X.
Un atkal, ko es esmu darot here-- ko way--
ir visp膩r膿js gad墨jums priek拧likums mezgls, kas ir pa vidu.
Ir p膩ris papildu br墨din膩jumi, ka j奴s
nepiecie拧ams apsv膿rt, kad j奴s dz膿拧ot pats s膩kums saraksta
vai pa拧膩m beig膩m sarakst膩.
Tur ir p膩ris 墨pa拧s st奴ra lietas risin膩t tur.
>> T膩tad tas darbojas dz膿拧anas jebkuru mezglu vid奴 uz list-- vienu, kas
ir le模it墨ms r膩d墨t膩ju priek拧u un likum墨gs r膩d墨t膩js atpaka募,
likum墨ga iepriek拧膿jo un n膩kamo r膩d墨t膩js.
Atkal, ja j奴s str膩d膩jat ar galiem, tu
nepiecie拧ams apstr膩d膩t tiem nedaudz at拧姆ir墨gi,
un m膿s nebrauksim run膩t par to tagad.
Bet j奴s varat dro拧i izdom膩t, ko vajag
j膩dara tikai skatoties 拧o video.
>> T膩p膿c m膿s esam izol膿ti X. X ir mezgls m膿s v膿lamies, lai izdz膿stu no saraksta.
Ko m膿s dar膩m?
Pirmk膩rt, mums ir nepiecie拧ams, lai p膩rk膩rtotu 膧rpus nor膩des.
Mums ir nepiecie拧ams, lai p膩rk膩rtotu 9 ir blakus izlaist 13
un nor膩da uz 10-- kas ir tas, ko m膿s esam tikko dar墨ts.
Un mums ar墨 p膩rk膩rtot 10 iepriek拧膿jo
nor膩d墨t uz 9. viet膩, nor膩dot uz 13.
>> T膩tad atkal, tas bija diagramma, lai s膩ktu ar.
Tas bija m奴su 姆膿d膿.
Mums ir nepiecie拧ams, lai izlaistu virs 13, bet mums ir ar墨 saglab膩t
integrit膩te saraksta.
M膿s nev膿lamies zaud膿t jebk膩du inform膩cija vien膩 vai otr膩 virzien膩.
T膩p膿c mums ir nepiecie拧ams, lai p膩rk膩rtotu tad nor膩des uzman墨gi
t膩p膿c mums nav p膩rtraukumu 姆膿di visp膩r.
>> T膩tad, m膿s varam teikt, 9 n膩kamais r膩d墨t膩ju nor膩da uz to pa拧u vietu
Tr墨spadsmit Next r膩d墨t膩js nor膩da tie拧i tagad.
T膩p膿c, ka m膿s esam beidzot gatavojas v膿laties izlaist 13.
T膩tad, kur 13 punkti N膩kamais, jums gribu devi艈i nor膩d墨t tur viet膩.
T膩tad tas, ka.
Un tad, kad vien 13 punkti atpaka募 to, k膩ds n膩k pirms 13,
m膿s gribam 10 nor膩d墨t 13, ka t膩 viet膩.
Tagad pazi艈ojums, ja jums sekot bultas, m膿s varam nomest 13
bez faktiski nezaud膿jot inform膩ciju.
M膿s esam tur integrit膩ti saraksta, virz膩s uz priek拧u un atpaka募.
Un tad m膿s varam tikai sava no t墨r墨t to uz aug拧u mazliet
pavelkot sarakstu kop膩.
T膩tad m膿s p膩rk膩rtoja nor膩des uz vienu vai otru pusi.
Un tad m膿s atbr墨voja X mezglu, ko satur 13,
un mums nav p膩rtraukumu 姆膿di.
T膩tad mums bija laba.
>> Gal墨gais piez墨me 拧eit saist墨tas sarakstos.
T膩tad gan singly- un divk膩rt piesaist墨t膩s saraksti, k膩 m膿s esam redz膿ju拧i,
atbalsts patie拧膩m efekt墨va ievieto拧anas un dz膿拧anu elementiem.
J奴s varat diezgan daudz dar墨t t膩 past膩v墨g膩 laik膩.
Ko mums dar墨t, lai dz膿stu elements ir tikai otrais atpaka募?
M膿s p膩rvietots vienu r膩d墨t膩ju.
M膿s p膩rc膿l膩s citu r膩d墨t膩ju.
M膿s atbr墨vots X- veica tr墨s oper膩cijas.
Tas vienm膿r ir tr墨s darb墨bas, lai dz膿st 拧o node-- lai atbr墨votu mezglu.
>> K膩 m膿s ievietot?
Nu, m膿s esam tikai vienm膿r tacking uz s膩kumu
ja m膿s esam ievietojot efekt墨vi.
T膩p膿c mums ir nepiecie拧ams, lai rearrange-- atkar墨b膩 no t膩, ja tas ir
singly- vai divk膩rt piesaist墨to saraksts, mums var b奴t nepiecie拧ams veikt tr墨s
vai 膷etras oper膩cijas max.
Bet atkal, tas vienm膿r ir tr墨s vai 膷etri.
Tas nav svar墨gi, cik daudz elementi ir m奴su sarakst膩,
tas vienm膿r ir tr墨s vai 膷etri operations-- t膩pat k膩 sv墨tro拧ana vienm膿r
tr墨s vai 膷etras oper膩cijas.
Ir pien膩cis laiks nemain墨gs.
T膩tad tas ir tie拧膩m liels.
>> Ar blokiem, m膿s dar膩m kaut kas l墨dz墨gs ievieto拧anas k膩rto拧anas.
J奴s dro拧i vien atceraties, ka ievieto拧anas k膩rtot nav konstants laiks algoritmu.
Paties墨b膩 tas ir diezgan d膩rgi.
T膩tad tas ir daudz lab膩k par ievieto拧anas.
Bet k膩 jau min膿ju atsevi拧姆i piesaist墨t膩s sarakstu video,
m膿s esam ieguvu拧i negat墨vie ar墨 拧eit, vai ne?
M膿s esam zaud膿ju拧i sp膿ju nejau拧i piek募奴t elementus.
M膿s nevaram teikt, es gribu elements Number Four vai elementu skaits 10 no saist墨t膩 saraksta
t膩pat, ka m膿s varam dar墨t ar mas墨vu
vai m膿s varam vienk膩r拧i tie拧i indekss m奴su Array s elements.
>> Un t膩 m膿模ina atrast elements saist墨taj膩 list--
ja mekl膿拧ana ir important-- Tagad var veikt line膩ru laiku.
T膩 k膩 saraksts k募奴st gar膩ks, tas var veikt vienu papildu soli
par katru elementu sarakst膩 Lai pal墨dz膿tu atrast to, ko m膿s mekl膿jam.
T膩tad tur ir kompromisus.
Tur ir mazliet pro un con elements 拧eit.
>> Un divk膩rt saist墨ti saraksti nav p膿d膿j膩 veida datu strukt奴ru kombin膩cijas
ka m膿s run膩jam par, 艈emot visas pamata 膿ku
bloki C liekot kop膩.
Jo paties墨b膩, m膿s varam pat dar墨t lab膩k nek膩 拧is
izveidot datu strukt奴ru, kas j奴s var膿tu p膩rl奴kot
past膩v墨g膩 laiku too.
Bet vair膩k par to cit膩 video.
>> Es esmu Doug Lloyd.
Tas ir CS50.