[MIZIK jwe] Doug Lloyd: Tout dwat. Se konsa, si ou jis fini ki videyo sou lis separeman ki lye regrèt Mwen te kite ou nan sou yon ti jan nan yon cliffhanger. Men, mwen kontan ou isit la a fini istwa a nan lis doubl-lye. 

Se konsa, si ou sonje soti nan ki videyo, nou te pale sou ki jan separeman ki lye lis fè ale nan kapasite nou fè fas ak enfòmasyon kote ki kantite eleman oswa nimewo a nan atik ki nan yon lis ka grandi oswa retresi. Nou kapab kounye a fè fas ak yon bagay tankou sa, kote nou pa t 'kapab fè fas ak li ak ranje. 

Men, yo soufri soti nan yon limit kritik ki se ke ak yon separeman ki lye lis, nou ka sèlman janm avanse pou pi nan yon direksyon ki sèl nan lis la. Ak sèlman sitiyasyon an reyèl kote ki ka vin tounen yon pwoblèm te lè nou t ap eseye efase yon eleman sèl. Apre sa, nou pa t 'menm diskite sou ki jan fè li nan yon lis separeman ki lye nan pseudocode. Li se sètènman pratik, men li kapab yon ti jan nan yon konplikasyon. Se konsa, si ou jwenn tèt ou nan yon sitiyasyon kote w ap eseye efase eleman sèl nan lis la oswa li k ap pase yo gen obligasyon ki ou pral efase eleman yon sèl soti nan lis la, ou ta ka vle yo konsidere l sèvi avèk yon doubl-lye lis olye pou yo yon lis separeman-lye. Paske lis doubl-lye pèmèt ou pou avanse pou pi tou de anvwa ak bak nan lis la olye pou yo jis pou pi devan nan list-- nan jis yo ajoute yon eleman siplemantè nan definisyon estrikti nou an pou doubl-lye lis ne la. 

Yon fwa ankò, si ou pa ap ale nan dwe efase eleman sèl soti nan list-- a paske nou ap ajoute yon jaden anplis nan estrikti nou an definisyon, nœuds yo tèt yo pou lis doubl-lye yo pral yo dwe pi gwo. Yo ap pral pran moute plis bytes nan memwa. Se konsa, si sa a se pa yon bagay w ap ale nan bezwen fè, ou ta ka deside li a pa vo komès la koupe gen yo ap depanse siplemantè a bytes nan memwa mande pou yon lis doubl-lye si ou pa ap ale nan dwe efase eleman sèl. Men, yo ap tou fre pou lòt bagay tou. 

Se konsa, jan mwen te di, nou jis gen ajoute yon sèl jaden sèl nan estrikti nou an definition-- nosyon sa a a yon konsèy anvan yo. Se konsa, avèk yon lis separeman ki lye, nou gen valè a ak konsèy la Apre sa, se konsa lis la doubl-lye jis gen yon fason pou avanse pou pi bak kòm byen. 

Koulye a, nan-lye a separeman lis videyo, nou te pale sou sa yo, se senk nan la bagay prensipal ou bezwen yo dwe kapab fè yo travay avèk lis lye. Se pou pi fò nan sa yo, lefèt ke li nan yon lis doubl-lye se pa reyèlman yon gwo sote. Nou ka toujou rechèch nan pa jis vanse nan kòmanse fini. Nou ka toujou kreye yon ne soti nan lè mens, bèl anpil menm jan an. Nou ka efase lis bèl anpil menm jan an tou. Bagay sa yo sèlman ki se subtile diferan, reyèlman, yo mete nouvo nœuds nan lis la, epi n ap finalman pale sou efase yon eleman sèl nan lis la kòm byen. Yon fwa ankò, bèl anpil twa lòt yo, nou ap pa ale nan pale de yo kounye a paske yo ap jis reglaj trè minè sou ide yo diskite nan separeman ki lye lis videyo a. 

Se konsa nou insert yon nouvo ne nan yon lis doubl-lye. Nou te pale de fè sa pou separeman ki lye lis kòm byen, men gen nan yon koup nan siplemantè atrap ak lis doubl-lye. Nou [? pase?] nan tèt la nan la lis isit la ak kèk valè abitrè, epi nou vle jwenn tèt la nouvo nan lis la soti nan fonksyon sa a. Se poutèt sa li retounen yon etwal dllnode. Se konsa, sa yo se etap yo? Yo se, ankò, trè menm jan separeman ki lye lis ak yon sèl de sa siplemantè. Nou vle repati espas pou yon nouvo ne ak chèk a asire w li nan ki valid. Nou vle yo ranpli ki ne moute ak tou sa enfòmasyon nou vle mete nan li. Bagay la pase nou bezwen do-- nan bagay siplemantè nou bezwen fè, rather-- se yo ranje konsèy la Previous nan tèt la fin vye granmoun nan lis la. Sonje ke paske bay lis doubl-lye, nou ka avanse pou pi devan ak backwards-- ki vle di ke chak ne aktyèlman pwen nan de lòt nœuds olye pou yo jis yon sèl. Se konsa, nou bezwen ranje tèt la fin vye granmoun nan lis la A ak pwen bak nan tèt nan nouvo nan lis la lye, ki te yon bagay nou pa t 'dwe fè anvan. Apre sa, tankou anvan, nou jis retounen yon konsèy nan tèt la nouvo nan lis la. 

Se konsa, isit la nan yon lis. Nou vle insert 12 nan lis sa a. Remake dyagram nan se yon ti kras diferan. Chak ne gen twa fields-- done, ak yon konsèy Next nan wouj, ak yon konsèy Previous nan ble. Pa gen anyen vini anvan 15 ne la, se konsa Previous konsèy li yo se nil. Li nan nan konmansman an nan lis la. Pa gen anyen anvan li. E pa gen anyen vini apre 10 ne la, ak se konsa li a Next konsèy se nil kòm byen. 

Se konsa, kite a ajoute 12 a lis sa a. Nou bezwen [fèbl] espas pou ne la. Nou mete 12 andedan nan li. Lè sa a, ankò, nou bezwen yo dwe reyèlman atansyon pa kraze chèn lan. Nou vle ordonne a endikasyon yo nan lòd ki kòrèk la. Epi pafwa ki ta ka mean-- kòm nou pral wè patikilyèman ak delete-- ke nou fè gen kèk endikasyon redondants, men sa a OK. 

Se konsa, sa nou vle fè an premye? Mwen ta rekòmande pou a bagay ou ta dwe pwobableman fè yo ranpli endikasyon yo nan 12 an ne anvan ou manyen okenn moun lòt bagay. Se konsa, sa se 12 ale nan lonje dwèt sou vin apre a? 15. Ki sa ki vini anvan 12? Pa gen anyen. Koulye a, nou te plen nan enfòmasyon anplis nan 12 se konsa li gen Previous, Apre sa, ak valè. 

Koulye a, nou ka gen 15-- sa a siplemantè etap nou te pale sou- nou ka gen 15 pwen tounen nan 12. Epi, koulye a nou kapab deplase tèt la nan lis la lye nan tou pou 12. Se konsa, li a trè menm jan ak sa nou t ap fè ak lis separeman-lye, eksepte pou etap anplis ki konekte tèt la fin vye granmoun nan lis la do nan tèt nan nouvo nan lis la. 

Koulye a, kite a finalman efase yon ne nan yon lis lye. Se konsa nou di nou gen kèk lòt fonksyon ki se pou nou jwenn yon ne nou vle efase e li te ban nou yon konsèy nan egzakteman ne a ke nou vle efase. Nou pa menm need-- di nan tèt se toujou globalman deklare. Nou pa bezwen tèt isit la. Tout fonksyon sa a ap fè se nou te jwenn yon konsèy nan egzakteman nou an ne vle debarase m de. Se pou yo debarase m de li. Li se yon anpil pi fasil ak doubl-lye lis. First-- li la aktyèlman jis yon koup bagay sa yo. Nou jis bezwen ranje ki antoure a endikasyon nœuds 'sa yo ke yo sote sou ne a nou vle efase. Lè sa a, nou ka efase ke ne. Se konsa, ankò, nou ap jis ale atravè tout isit la. Nou te aparamman deside ke nou vle efase X. nan ne Epi ankò, ki sa mwen se fè isit lan-- pa way-- nan se yon ka jeneral pou yon ne se sa ki nan mitan yo. Gen yon koup nan opozisyon siplemantè ke ou bezwen konsidere lè w ap efase kòmansman la anpil nan lis la oswa nan fen la anpil nan lis la. Genyen yon koup nan espesyal ka kwen fè fas ak la. 

Se konsa, sa ap travay pou efase nenpòt ne nan mitan an nan yon sèl nan list-- ki gen yon konsèy pou pi devan lejitim ak yon konsèy lejitim bak, lejitim Previous ak pwochen konsèy. Yon fwa ankò, si w ap travay ak pwent yo, ou bezwen okipe moun yon ti kras yon fason diferan, epi nou pa ap ale nan pale sou sa koulye a. Men, ou kapab pwobableman figi konnen sa ki bezwen yo dwe fè jis pa gade videyo sa a. 

Se konsa, nou te izole X. X se ne la nou vle efase nan lis la. Ki sa nou fè? Premyèman, nou bezwen ordonne pwent yo deyò. Nou bezwen ordonne 9 nan pwochen nan sote sou 13 ak pwen nan 10-- ki se sa nou te jis fè. Apre sa, nou menm tou nou bezwen ordonne 10 nan Previous A ak pwen nan 9 olye pou yo montre nan 13. 

Se konsa, ankò, sa a te nan dyagram yo kòmanse avèk yo. Sa a te chèn nou an. Nou bezwen sote sou 13, men nou bezwen tou prezève entegrite nan nan lis la. Nou pa vle pèdi nenpòt enfòmasyon nan nenpòt direksyon. Se konsa, nou bezwen ordonne endikasyon yo avèk anpil atansyon se konsa nou pa kraze chèn lan nan tout. 

Se konsa, nou ka di 9 nan Next konsèy lonje dwèt nan plas la menm ki Next trèz nan konsèy lonje dwèt kounye a. Paske nou ap evantyèlman ale nan vle sote sou 13. Se konsa, tout kote 13 pwen a, ou vle nèf nan pwen gen pito. Se konsa, sa a, se sa. Lè sa a, tout kote 13 Apre sa, pwen tounen a, kèlkeswa sa ki vini anvan 13, nou vle 10 A ak pwen ak sa yo ki olye pou yo 13. Koulye a, remake, si w swiv flèch yo, nou ka lage 13 san yo pa aktyèlman pèdi nenpòt enfòmasyon. Nou te kenbe entegrite nan nan lis la, k ap deplase tou de devan dèyè. Lè sa a, nou kapab jis sòt a netwaye li moute yon ti jan pa rale lis la ansanm. Se konsa, nou rearanje nan endikasyon sou chak bò. Lè sa a, nou libere X la ne ki genyen 13, epi nou pa t 'kraze chèn lan. Se konsa, nou te fè bon. 

Final nòt isit la sou lis lye. Se konsa, tou de singly- ak doubl-lye lis, menm jan nou te wè, sipò reyèlman efikas ensèsyon ak sipresyon nan eleman. Ou ka bèl anpil fè li nan tan konstan. Ki sa nou dwe fè yo efase yon eleman jis yon dezyèm de sa? Nou te deplase yon sèl konsèy. Nou te deplase yon lòt konsèy. Nou libere X-- pran twa operasyon yo. Li toujou pran twa operasyon yo efase ki node-- libere yon ne. 

Ki jan nou Insert? Bon, nou ap jis toujou tacking sou nan konmansman an si nou ap mete efikasite. Se konsa, nou bezwen rearrange-- tou depann de si li nan yon singly- oswa doubl-lye lis, nou ta ka bezwen fè twa oswa kat operasyon max. Men, ankò, li la toujou twa oswa kat. Li pa enpòtan konbyen eleman yo nan lis nou an, li toujou twa oswa kat operations-- jis tankou sipresyon se toujou twa oswa kat operasyon yo. Li lè konstan. Se konsa, sa ki nan vrèman gwo. 

Avèk ranje, nou t ap fè yon bagay tankou sòt ensèsyon. Ou pwobableman sonje ke ensèsyon sòt se pa yon algorithm tan konstan. Li nan aktyèlman trè chè. Se konsa, sa a se yon anpil pi bon pou mete. Men, jan mwen mansyone nan la separeman ki lye lis videyo, nou te gen yon inconvénient isit la tou, dwa? Nou te pèdi kapasite nan aksè owaza eleman. Nou pa ka di, mwen vle nimewo eleman kat oswa nimewo eleman 10 nan yon lis lye menm jan an ke nou kapab fè sa ak yon etalaj oswa nou ka jis endèks dirèkteman nan eleman etalaj nou an. 

Se konsa, ap eseye jwenn yon eleman nan yon list-- lye si chache se important-- ka kounye a pran tan lineyè. Kòm lis la vin pi long, li ta ka pran yon sèl etap plis pou chak eleman yon sèl nan lis la nan lòd yo jwenn sa nou ap chèche pou. Se konsa, gen nan konpwomi komès. Genyen yon ti jan nan yon pro ak eleman kon isit la. 

E li bay lis doubl-lye yo pa nan kalite sot pase a nan estrikti done konbinezon ke nou pral pale sou, pran tout bilding lan debaz blòk nan C yon mete ansanm. Paske an reyalite, nou kapab menm fè pi byen pase sa a yo kreye yon estrikti done ki ou ka kapab fè rechèch nan nan tan konstan tou. Men, plis sou sa nan yon lòt videyo. 

Mwen se Doug Lloyd. Sa a se CS50.