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