[MUSIC PLAYING] DOUG LLOYD: Bütün hüququ. Belə ki, yalnız ki, başa əgər story bağlı siyahıları sorry video Mən sizə off tərk bir cliffhanger bit. Amma siz başa çatdırmaq üçün buradayıq sevindim ikiqat bağlı siyahıları hekayə. Siz geri əgər Belə ki, video, danışdıq story bağlı haqqında siyahıları qabiliyyəti iştirak etmək məlumat ilə məşğul burada elementlərin sayı və ya maddələr sayı siyahısı inkişaf və ya shrink. Biz indi ilə məşğul ola bilər kimi bir şey, burada biz serialların ilə məşğul bilmədi. Lakin onlar bir əziyyət yoxdur tənqidi məhdudiyyət hansı bir story bağlıdır ki, siyahısı, biz yalnız heç hərəkət edə bilər siyahısını bir istiqamətdə. Və yalnız real vəziyyət burada bir problem ola bilər zaman biz çalışdıqlarını bir element silin. Və biz hətta bunu necə müzakirə etməyib pseudocode bir story bağlı siyahı var. Bu, əlbəttə ki, doable, lakin bir əngəl bir az ola bilər. Siz özünüzü tapmaq əgər bir vəziyyət Silmək çalışdığınız siyahıdan bir elementləri və ya tələb olacaq Siz silmə etmək lazımdır ki, vahid elementləri siyahısı, istədiyiniz bilər istifadə üçün ikiqat bağlı əvəzinə story bağlı siyahı edin. Ikiqat bağlı siyahıları sizə imkan verir, çünki irəli və geri, həm də hərəkət etmək əvəzinə siyahısını yalnız irəli siyahısı ilə Yalnız bir əlavə element əlavə Bizim strukturu anlayışına ikiqat bağlı siyahı node üçün. Yenə fikrində deyilik əgər bir elementləri silmə etmək list-- biz əlavə edirik, çünki Bizim strukturuna əlavə sahə müəyyən qovşaqlarının özləri ikiqat bağlı siyahıları üçün böyük olacaq. Onlar etmək olacaq yaddaş daha bayt qədər. Və əgər bir şey deyil Siz nə etmək lazımdır olacaq Siz bu qərar qəbul edə bilər off dəyər ticarət əlavə sərf etmək yaddaş bytes tələb bir ikiqat bağlı siyahısı üçün siz değilseniz gedən bir elementləri silmə olunacaq. Amma onlar da, sərin istəyirik çox başqa şeylər üçün. Dediyim kimi, biz yalnız əlavə etmək üçün var Bizim strukturu bir sahədə Bu anlayışı definition bir Əvvəlki göstərici. Bir story bağlı siyahı ilə, belə ki, biz , dəyər və Next göstərici var belə ikiqat bağlı siyahı yalnız var bir yol, eləcə də geri hərəkət etmək. İndi story bağlı siyahısı video, danışdıq Bu barədə beş var olmaq üçün lazım olan əsas şey edə bağlı siyahıları ilə işləmək üçün nə etmək. Və bu ən fakt bir ikiqat bağlı siyahı var ki, həqiqətən böyük jump deyil. Biz hələ sadəcə vasitəsilə axtarış edə bilərsiniz başdan irəliləyir son. Biz hələ bir node yaratmaq bilər nazik hava, olduqca çox eyni şəkildə. Biz olduqca siyahıları düzəlişlər edə bilərsiniz çox eyni şəkildə. təkcə ki, , subtly müxtəlif həqiqətən, daxil edilir siyahısına yeni qovşaqlarının, və nəhayət, biz silmə haqqında danışmaq lazımdır eləcə də siyahıdan bir element. Yenə olduqca çox digər üç, biz istəyirik onlar haqqında danışmaq niyyətində deyil İndi onlar yalnız istəyirik, çünki ideyaları çox kiçik tweaks müzakirə story bağlı siyahı video. Belə ki, yeni bir node daxil imkan bir ikiqat bağlı siyahısına daxil. Biz bunu danışdıq həmçinin siyahıları story bağlı, lakin əlavə bir neçə var ikiqat bağlı siyahıları ilə olarsınız. Biz [mi? keçən?] rəhbəri burada sadalamaq və bəzi ixtiyari dəyəri, və biz yeni baş almaq istəyirəm Bu funksiya həyata siyahısı. Bir dllnode ulduz qaytarır görə. Belə ki, addımlar hansılardır? Onlar yenə, çox oxşardır siyahıları story bağlı üçün bir əlavə əlavə ilə. Biz yeni üçün yer ayırıb istəyirəm node və çek etibarlı var əmin olun. Biz bu node doldurmaq istəyirəm hər hansı məlumat, biz bu qoymaq istəyirik. son şey Biz nə etmək lazımdır Biz nə etmək lazımdır əlavə şey rather-- Əvvəlki göstərici düzeltmek üçün Siyahıya köhnə rəhbəri. Unutmayın ki, çünki bir ikiqat bağlı siyahıları, biz irəli hərəkət edə bilər və backwards-- hansı hər node həqiqətən işarə o deməkdir ki, digər iki qovşaqlarının əvəzinə yalnız bir. Və belə ki, biz düzeltmek lazımdır siyahı köhnə baş yeni rəhbəri geri qeyd etmək bir şey idi bağlı siyahısı, biz əvvəl nə etmək yox idi. Və əvvəlki kimi, biz yalnız bir qayıtmaq siyahısı yeni rəhbəri göstərici. Belə ki, burada bir siyahısı. Biz bu siyahıda 12 əlavə etmək istəyirəm. Diagram Qeyd edək ki, qədər fərqlidir. Hər bir node üç sahələri var məlumat və qırmızı bir Next pointer, və mavi bir Əvvəlki göstərici. Heç bir şey, 15 node əvvəl gəlir belə ki, onun Əvvəlki göstərici null edir. Bu siyahıda başlanğıcı var. Əvvəl bir şey yoxdur. Və heç bir şey, 10 node sonra gəlir və belə ki, Next göstərici həmçinin null deyil. Belə ki, bu siyahıya 12 əlavə edək. Biz node üçün [işitilemez] yer lazımdır. Biz bu 12 içini qoydu. Və sonra, biz, həqiqətən olmaq lazımdır Ehtiyatlı zəncir qırmaq deyil. Biz yenidən istəyirəm Düzgün qaydada göstəricilər. Və bəzən mean-- bilər biz xüsusilə görəcəksiniz kimi delete-- ilə bəzi var ki, lazımsız göstəricilərinə, amma ki, OK. Beləliklə, biz ilk nə istəyirsiniz? Tövsiyə edirəm şeyi yəqin ki, olmalıdır Bunu 12 göstəricilərinə doldurmaq üçün node Siz başqa heç kimə toxunmaq əvvəl. Belə ki, nə 12 növbəti qeyd etmək gedir? 15. Nə 12 əvvəl gəlir? Heç bir şey. İndi biz dolu etdik 12 əlavə məlumat belə ki, Əvvəlki, Next, və dəyəri var. İndi biz ola bilər 15-- bu əlavə biz biz about-- söhbət addım geri 12 15 nöqtəsi ola bilər. İndi biz rəhbəri hərəkət edə bilər bağlı siyahı 12 olmalıdır. Belə ki, olduqca oxşar nə biz story bağlı siyahıları ilə etdiklərini, əlavə addım istisna olmaqla siyahısı köhnə baş birləşdirən siyahısı yeni rəhbəri geri. İndi nəhayət silmək imkan bir bağlı siyahı bir node. Belə ki, biz deyək bəzi digər funksiyası biz silmək üçün bir node tapmaq olunur və dəqiq bizə bir göstərici verdi biz silmək üçün node. Biz hətta demək need-- deyil baş hələ qlobal elan edilir. Biz burada baş ehtiyac yoxdur. Bütün bu funksiya edir biz deyil dəqiq node biz bir pointer tapıldı xilas etmək istəyirik. Bunun xilas edək. Bu ilə bir çox asandır siyahıları ikiqat bağlı. Bu həqiqətən First-- yalnız bir neçə şeyi. Biz yalnız ətraf düzeltmek lazımdır Bölmələri "göstəricilərinə onlar üzərində keçmək ki, node biz silmək istəyirəm. Və sonra biz bu node silə bilərsiniz. Belə ki, yenə, biz yalnız burada keçir edirik. Biz yəqin ki qərarına gəldik biz node X. silmək üçün Və yenə, mən nə edirəm yolla tərəfindən burada bunu Bir üçün ümumi haldır ortada olduğunu node. Bir neçə var əlavə caveats ki, Siz silmə etdiyiniz zaman hesab etmək lazımdır siyahısı əvvəldən və ya siyahıdan çox sonu. Xüsusi bir neçə var künc hallarda ilə məşğul. Belə ki, bu hər hansı bir node silmə üçün çalışır list-- bir ortasında ki, irəli qanuni göstərici var və geri qanuni pointer, qanuni əvvəlki və sonrakı göstərici. Yenə siz çalışırıq, əgər bitir ilə, bu idarə etmək lazımdır bir az fərqli, və biz fikrində deyilik İndi ki, haqqında danışmaq. Amma yəqin ki, edə bilərsiniz lazımdır nə anlamaq bu video seyr yalnız ediləcək. Beləliklə, biz təcrid etdik X. X node edir biz siyahıdan silmək istəyirəm. Biz nə etməliyəm? Birincisi, biz yeniden lazımdır kənarda göstəricilər. Biz yeniden lazımdır 9 növbəti 13 üzərində keçmək və nöqtə 10-- olan biz yalnız etdik nə. Və biz də lazımdır 10-nin Əvvəlki yenidən əvəzinə 13 işarə 9 qeyd etmək. Belə ki, yenə bu idi ilə başlamaq üçün diagram. Bu, bizim zəncirvari idi. Biz 13-dən çox keçmək lazımdır lakin biz də qorumaq lazımdır siyahısı bütövlüyü. Biz hər hansı bir itirmək istəmirəm ya istiqamətdə məlumat. Beləliklə, biz yeniden lazımdır göstəricilərinə diqqətlə belə ki, biz bütün zəncir qırmaq deyil. Beləliklə, biz 9 Next göstərici demək olar eyni yerə işarə ki, on üç Next pointer indi göstərir. Biz nəhayət istəyirik, çünki 13 üzərində keçmək istəyirəm olacaq. Belə ki, hər yerdə 13 bal Sonra, doqquz əvəzinə orada qeyd etmək istəyirəm. Belə ki, ki, var. Və sonra hər yerdə 13 xalla geri üçün, 13 əvvəl gəlir nə olursa olsun, biz qeyd etmək istəyirəm 10 ki, yerinə 13. Təqib əgər İndi, qeyd oxlar, biz 13 açılır həqiqətən hər hansı bir məlumat itirmədən. Biz siyahısı bütövlüyünü saxlanılır etdik irəli və geri, həm də hərəkət. Və sonra biz yalnız sort edə bilərsiniz bir az onu təmizləmək birlikdə siyahısını çəkərək. Belə ki, biz yenidən hər tərəfdən göstəricilər. Və sonra biz X azad 13 olan node, və biz zəncir qırmaq vermədi. Beləliklə, biz yaxşı idi. Burada bağlı siyahıları Final qeyd. Belə ki, singly- həm də ikiqat bağlı siyahıları, biz gördük kimi, dəstək həqiqətən səmərəli etmək və elementlərin silinməsi. Siz olduqca çox edə bilərsiniz daimi vaxt bu. Biz silmək üçün nə etmək var idi bir element əvvəl yalnız bir ikinci? Biz bir pointer köçürülüb. Biz başqa göstərici köçürülüb. Biz X-- üç əməliyyatları aldı azad. O, həmişə üç əməliyyatları edir bir node azad ki, node silin. Biz necə daxil edə bilərəm? Yaxşı, biz yalnız həmişə istəyirik əvvəlində haqqında tacking biz səmərəli daxil edirsinizsə. Beləliklə, biz rearrange-- lazımdır bu əgər asılı olaraq bir singly- və ya ikiqat bağlı siyahısı, biz üç nə etmək lazımdır bilər və ya dörd əməliyyatları max. Ancaq yenə də, bu, həmişə üç və ya dörd var. Bu neçə etməz elementləri, bizim siyahıda var həmişə üç və ya dörd operations-- var yalnız silinməsi həmişə kimi üç və ya dörd əməliyyatları. Bu daimi vaxt var. Belə ki, həqiqətən böyük. Diziler ilə, biz bunu durub sort kimi bir şey. Siz yəqin ki, durub geri sort daimi vaxt alqoritm deyil. Bu, həqiqətən, olduqca bahalı. Belə ki, bu daxil bir çox daha yaxşıdır. Amma qeyd olunduğu kimi siyahısı video story bağlı, Biz burada bir İşin mənfi tərəfi odur var, çox sağ etdik? Biz imkanı itirdik təsadüfi elementləri daxil. Biz element sayı dörd istəyirsinizsə, deyə bilmərəm bir bağlı siyahı və ya element sayı 10 Eyni şəkildə biz bir sıra ilə bunu və ya biz yalnız birbaşa index bilərsiniz Bizim serialın element daxil. Və belə bir tapmaq üçün çalışırıq bağlı list-- element axtarış important-- əgər İndi xətti müddət bilər. Siyahısı artıq olur ki, bu bir əlavə addım bilər siyahıda hər bir element üçün order biz aradığınız nə tapa bilərsiniz. Belə ki, ticarət off var. Bir pro bir az var burada con element. Və ikiqat bağlı siyahıları deyil data structure birləşməsi son cür Biz haqqında danışmaq lazımdır ki, bütün əsas bina alaraq C blokları bir birlikdə qoyulması. Əslində, biz, çünki hətta bu daha yaxşı bir data strukturu yaratmaq üçün Siz vasitəsilə axtarış edə bilər daimi vaxt çox. Amma başqa video ki, daha çox. Mən Doug Lloyd edirəm. Bu CS50 edir.