[За възпроизвеждане на музика] Дъг LLOYD: Добре. Така че, ако току-що завърши, че видео по единично-свързани списъци съжалявам Аз сте спрели на малко на Катерачът. Но се радвам, че сте тук, за да продължи историята на двойно по-свързани списъци. 

Така че, ако си спомняте от че видео, ние говорихме за това как поединично-свързана списъци посещават нашата способност да се справят с информация където броят на елементите или броя на елементите в списък може да расте или се свива. Сега можем да се справим с нещо подобно, където не бихме могли да се справим с него с масиви. 

Но те не страдат от едно критична ограничение, че е с единично свързан списък, ние можем само да се движат в една посока през списъка. И единствената реална ситуация когато това може да стане проблем беше, когато се опитвахме да изтриете отделен елемент. А ние дори не обсъждат как да го направя в поединично-свързан списък в Псевдокод а. Това със сигурност е постижимо, но тя може да бъде малко на една караница. Така че, ако откриете себе си при положение, която се опитвате да изтриете единични елементи от списъка или това ще се изисква че ще бъдат изтриване единични елементи от в списъка, може да искате да обмисли възможността за използване на двойно по-свързано изброят вместо на единично-свързан списък. Заради двойно по-свързани списъци ви позволяват да се движи напред, назад и отзад в списъка вместо само напред през list-- просто чрез добавяне на един допълнителен елемент до нашата дефиниция структура за двойно по-свързан списък възел. 

Отново, ако не започваш да се изтриваме единични елементи от list-- защото сме добавяне допълнително поле за нашата структура определение, самите възли за двойно по-свързани списъци ще бъде по-голям. Те ще вземат до повече байта памет. И така, ако това не е нещо, започваш да трябва да направите, може да решите, че е не си струва търговията на разстояние да се наложи да прекарат допълнителни байта памет, изисквани за двойно по-свързан списък, ако не сте Ще бъдат изтриване единични елементи. Но те са също така хладно за други неща също. 

Така че, както казах, ние просто трябва да добавите едно единствено поле за нашата структура definition-- това понятие Предишна на показалеца. Така че с единично-свързан списък, ние имат стойност и Next показалеца, така че двойно по-свързан списък просто има начин да се движи назад, както добре. 

Сега в поединично-свързана списък на видео, ние говорихме за това са пет от Основните неща, които трябва да бъдат в състояние да направи, за да работи с свързани списъци. И за повечето от тях, фактът, че това е двойно по-свързан списък не е наистина голям скок. Все още можем да се търси чрез само с се движат напред от началото до края. Все още можем да се създаде един възел от нищото, почти по същия начин. Ние можем да изтриете списъци доста по същия начин, също. Единствените неща, които са едва доловимо различен, Наистина, поставяте нови възли в списъка, и ние най-накрая ще говорим за изтриване един елемент от списъка, както добре. Отново доста много другите трима, ние сме Няма да говорим за тях точно сега, защото те са просто много малки ощипвам на идеите, обсъдени в поединично-свързан списък видеото. 

Така че нека да вмъкнете нов възел в двойно по-свързан списък. Ние говорихме за това това за поединично-свързани списъци, както и, но има няколко допълнителни хваща с двойно по-свързани списъци. Бяха [? минаваща?] в главата на избройте тук и някои произволна стойност, и ние искаме да получите най-новата глава на списъка от тази функция. Ето защо тя се връща на dllnode звезда. Така че какви са стъпките? Те са, отново, много подобен на единично свързан списъци с едно допълнително добавяне. Искаме да заделя пространство за нов възел и проверка, за да се уверите, че е валиден. Искаме да запълни този възел нагоре всякаква информация, която ние Искам да сложа в него. Последното нещо, което ние трябва да do-- на допълнително нещо, което трябва да направим, rather-- е да се определи Предишна показалеца на стария начело на списъка. Не забравяйте, че поради двойно-свързани списъци, можем да продължим напред и backwards-- които означава, че всеки възел действително точки до двама други възли, вместо само един. И така, ние трябва да се определи старата началото на списъка да посочи назад към новия ръководител на на свързан списък, който беше нещо ние не трябва да направите преди. И както и преди, ние просто се върне указател към новия ръководител на списъка. 

Така че тук е списък. Искаме да въведете 12 в този списък. Забележете, че диаграмата е малко по-различен. Всеки възел съдържа три fields-- данни, както и Next показалка в червено, Предишна и показалеца в синьо. Нищо не идва преди 15 възела, така че си Previous показалка е нищожна. Това е началото на списъка. Няма нищо преди това. И нищо не идва след 10 възела и така че това е Next показалка е нищожна, както добре. 

Така че нека да добавите 12 към този списък. Ние се нуждаем [недоловим] пространство за възела. Ние събрахме 12 вътре в него. И след това отново, ние трябва да бъдем наистина Внимавайте да не се прекъсне веригата. Искаме да пренаредите указатели в правилния ред. И понякога, че може mean-- както ще видим по-специално с delete--, че ние имаме някаква съкратените указатели, но това е ОК. 

Така че това, което искаме да направим първо? Бих препоръчал неща, които вероятно направя, трябва да попълните указателите от 12-те възел, преди да докосне някой друг. Така че това, което се случва 12 да сочи към следващия? 15. Онова, което идва преди 12? Нищо. Сега сме напълни допълнителна информация в 12 така че има Previous, Next, и стойност. 

Сега ние можем да имаме 15-- това допълнително стъпка ние говорим about-- ние може да има 15 точка обратно към 12. И сега можем да се движим главата на свързания списък да бъде също 12. Така че това е доста подобен на това, което ние правехме с единично-свързани списъци, с изключение на допълнителна стъпка на свързващ старата начело на списъка Обратно към новия ръководител на списъка. 

Сега нека най-накрая изтрийте един възел от свързан списък. Така че нека да кажем, че имаме някаква друга функция, която е намирането на възел искаме да изтриете и ни е дал указател към точно възела, който ние искаме да изтриете. Ние дори не need-- изречете главата е все още в световен мащаб обявена. Ние не се нуждаем главата тук. All тази функция се прави е ние сме намерено указател към точно WE възел искате да се отървете от. Нека да се отървете от него. Това е много по-лесно с двойно-свързани списъци. First-- това е всъщност само на няколко неща. Ние просто трябва да се определи обкръжението указатели възли, така че те прескачам възела искаме да изтриете. И тогава ние можем да изтриете този възел. Така че отново, ние просто преживява тук. Ние очевидно са решили, че ние искаме да изтриете X. възел И отново, това, което аз съм прави here-- от way-- е общ случай за възел, който е в средата. Има няколко на допълнителни уговорки, които сте трябва да се помисли, когато сте изтриване самото начало на списъка или в самия край на списъка. Има няколко специални ъглови случаи да се справят с там. 

Така че това работи за изтриване на всеки възел в средата на list-- този, който има законен показалеца напред и законна показалеца назад, легитимна Previous Next и показалеца. Отново, ако работите с краищата, ще трябва да се справят тези, малко по-различно, и ние няма да говорим за това сега. Но можете вероятно разбера какво се нуждае да бъде направено само от гледане това видео. 

Така че ние сме изолиран X. X е възелът ние искаме да изтриете от списъка. И какво ще правим? Първо, трябва да се пренаредят външните указателите. Ние трябва да се пренаредят 9 следващия да пропуснете над 13 и точка да 10-- които е това, което ние току-що сте направили. И ние също трябва да пренаредите 10 е Previous да сочи към 9 вместо сочейки към 13. 

Така че отново, това е най- диаграма, за да започнете. Това беше нашата верига. Ние трябва да прескочим 13, но ние трябва да се запазят също целостта на списъка. Ние не искаме да загубим информация в двете посоки. Така че ние трябва да се пренаредят указателите внимателно така че ние не се прекъсне веригата на всички. 

Така че можем да кажем, 9 Следваща показалка точки на същото място че тринадесет Следваща показалка посочва точно сега. Тъй като ние сме в крайна сметка ще искате да пропуснете над 13. Така че, където и 13 точки следващия, вие Искам да подчертая девет там, вместо. Така че това е, че. И след това, където и 13 точки назад да, каквото и да е преди 13, ние искаме да отбележим 10 на това, че вместо 13. Сега забележи, ако следвате стрелките, можем да падне 13 без всъщност губи всякаква информация. Ние продължаваме да се целостта на списъка, движи както напред и назад. И тогава можем просто някак от него се почисти малко чрез издърпване списъка заедно. Така че ние реорганизира указатели и от двете страни. И тогава ние остави на X възел, който съдържа 13, и ние не се прекъсне веригата. Така че ние направихме добра. 

Final бележка тук на свързани списъци. Така както singly- и двойно по-свързано списъци, както сме виждали, подкрепа наистина ефективен вмъкване и заличаване на елементи. Можете да направите доста много го в постоянна време. Какво трябва да направим, за да изтриете елемент само на секунда преди? Преместихме една показалка. Преместихме друга показалка. Ние остави X-- отне три операции. Тя винаги отнема три операции за изтриете че node-- да освободи един възел. 

Как да вмъкнете? Е, ние сме просто винаги слепване на началото ако сме вмъкване ефективно. Така че ние трябва да rearrange-- в зависимост от това дали е а singly- или двойно по-свързана списък, бихме могли да направим три нужда или четири операции макс. Но отново, тя винаги е три или четири. Няма значение колко елементи са в нашия списък, тя винаги е три или четири operations-- точно като заличаване винаги три или четири операции. Това е константно време. Така че това е наистина страхотно. 

С масиви, което правехме нещо като сортиране чрез вмъкване. Вероятно си припомним, че банкнотите сортирай не е постоянна алгоритъм време. Това всъщност е доста скъпо. Така че това е много по-добре за вмъкване. Но както споменах в поединично-свързан списък на видео, ние имаме един недостатък тук, нали? Ние сме загубили способността да произволно достъп елементи. Не можем да кажем, искам елемент номер четири или елемент номер 10 на свързан списък по същия начин, че можем направите това с масив или можем просто директно индекс в елемент нашия масив е. 

И така се опитва да намери елемент в свързан list-- ако търсенето е important-- Сега може да отнеме на линейното време. В списъка получава дълъг, може да отнеме една допълнителна стъпка за всеки един елемент от списъка в за да намерите това, което търсите. Така че има компромиси. Има малко на про и против елемент тук. 

И двойно по-свързани списъци не са на Последният вид комбинация структура на данните че ние ще говорим за, като всички основни сградата блокове от C на пускането заедно. Защото в действителност, ние можем дори направи по-добре от това за създаване на структура на данни, който може да сте в състояние да се търси чрез в постоянен време също. Но повече за това в друг видеоклип. 

Аз съм Дъг Лойд. Това е CS50.