>> [Музички]
Даг LLOYD: Во ред.
Значи, ако сте само што беше завршен дека видео на одделно-поврзани листи Жал
Јас ќе останев на малку cliffhanger.
Но јас сум среќен што си тука за да се заврши приказната за двојно-поврзани листи.
>> Значи, ако се сеќавате од тоа видео, ние разговаравме
за тоа како одделно-поврзана листи посетуваат нашата способност
да се справи со информации каде што бројот на елементи
или бројот на предмети во листа може да расте или се намалува.
Ние сега може да се справи со нешто слично, каде што
ние не може да се справи со неа со низи.
>> Но тие не страдаат од еден критична ограничување кое
е дека со одделно-поврзана листа, ние само може да се движеле
во една насока низ листата.
А единствената реална ситуација каде што може да стане проблем
беше кога се обидувавме да избришете еден елемент.
А ние дури и не разговараат за тоа како да го направи тоа во одделно-поврзани листа во pseudocode а.
Тоа е секако и остварливо, но тоа може да биде малку на нерви.
Значи, ако се наоѓате себеси во ситуација каде што
што се обидувате да ги избришете поединечни елементи од листата
или тоа се случува да се бара дека ќе се избрише
поединечни елементи од листата, можеби ќе сакате
да се разгледа со користење на двојно-поврзана листата наместо одделно-поврзани листа.
Затоа двојно-поврзани листи дозволувате да се движат напред и назад
низ листата наместо само напред низ list--
само со додавање еден дополнителен елемент на нашата дефиниција структура
за двојно-поврзани листа јазол.
>> Повторно, ако не одиш да се се бришење на поединечни елементи
од list-- бидејќи ние сме додавање на екстра поле на нашата структура
дефиниција, на јазли за двојно-поврзани листи
се ќе биде поголем.
Тие се случува да се земе повеќе бајти меморија.
И така, ако ова не е нешто ви се случува да треба да направите,
може да одлучи дека е не вреди да се пласирам
да треба да се трошат екстра бајти меморија потребно
за двојно-поврзани листа, ако не си ќе треба да се избрише еден елементи.
Но тие се исто така кул за други работи исто така.
>> Па како што реков, ние само треба да додадете една единствена област на нашата структура
definition-- овој поим Назад на покажувачот.
Па со одделно-поврзани листа, ние има вредност и следниот покажувач,
па на двојно-поврзани листа само има начин да се движи наназад, како и.
>> Сега во одделно-поврзана видео листа, разговаравме
за овие пет од главните работи што треба да бидат
можност да го направите да работи со поврзани листи.
И за повеќето од овие, фактот дека тоа е двојно-поврзани листа
не е навистина голем скок.
Ние се уште може да пребарувате низ само со се движат напред од почеток до крај.
Ние се уште може да се создаде еден јазол од воздух, прилично многу исти начин.
Можеме да го избришете списокот прилично на ист начин исто така.
Единствените нешта што се суптилно различни,
навистина, се вметнуваат нови јазли во листата,
и ние конечно ќе зборуваме за бришење еден елемент од листата, како и.
Повторно, доста другите три, ние сме
не одам да се зборува за нив во моментов, бидејќи тие се само
многу мали измени на идеите дискутира во одделно-поврзани листа видео.
>> Значи, да се вметне нов јазол во двојно-поврзани листа.
Ние разговаравме за тоа за одделно-поврзани листи, како и,
но има неколку екстра фаќа со двојно-поврзани листи.
Ние сме [? поминува?] во главата на листата тука и некои произволни вредност,
и ние сакаме да се добие нов шеф на листата од оваа функција.
Тоа е зошто тоа се враќа dllnode ѕвезда.
Па што се чекори?
Тие се, повторно, многу слични да одделно-поврзани листи
со еден екстра прилог.
Ние сакаме да се одвојува простор за нова јазол и проверете, за да бидете сигурни дека тоа е валиден.
Ние сакаме да се пополни тој јазол нагоре со што информациите што ги
сакате да се стави во неа.
Последното нешто што ние треба да го do-- екстра нешто што ние треба да се направи, rather--
е да ја поправите Претходна покажувачот на стариот шеф на листата.
Се сеќавам дека поради на двојно-поврзани листи,
ние може да се движи напред и backwards-- која
значи дека секој јазол всушност укажува до две други јазли, наместо на само еден.
И така ние треба да се поправи стариот врвот од листата
до точка назад кон новиот шеф на поврзаните листа, што беше нешто
ние не треба да се направи пред.
И како и досега, ние едноставно се врати Покажувач на новиот шеф на листата.
>> Значи тука е листа.
Ние сакаме да внесете 12 во оваа листа.
Забележи дека на дијаграмот е малку поинаква.
Секој јазол содржи три fields-- податоци, како и Следна покажувачот во црвено,
Претходната и покажувачот во сина боја.
Ништо не доаѓа пред 15 јазли, па нејзините Претходна покажувачот е нула.
Тоа е почетокот на листата.
Нема ништо пред него.
И ништо не се доаѓа по 10 јазли, како и па тоа е Следна покажувачот е нула, како и.
>> Па ајде да додадете 12 на оваа листа.
Ние треба [Беззвучен] простор за јазол.
Ќе стави 12 во него.
А потоа повторно, ние треба да биде навистина внимателни да не се скрши синџирот.
Ние сакаме да ги преуредите покажувачи во правилен ред.
А понекогаш и кои би можеле да mean-- како што ќе видиме, особено
со delete-- дека ние имаме некои излишни покажувачи, но тоа е во ред.
>> Значи она што сакаме да го направиме првиот?
Јас ќе им препорачаат на работи што требаше
направи се за да се пополни покажувачи на 12 јазол, пред да се допре било кој друг.
Значи, што е 12 случува да се укаже на следно?
15.
Она што доаѓа пред 12?
Ништо.
Сега сме исполни дополнителни информации во 12
така што има Претходно, Напред, и вредност.
>> Сега можеме да го имаме 15-- оваа дополнителна чекор ние се зборува about-- ние
може да има 15 точка назад кон 12.
И сега можеме да се движиме на главата на поврзаните листа, исто така, да биде 12.
Така, тоа е прилично слична на она што го прават во одделно-поврзани листи,
освен за дополнителен чекор на поврзување на стари врвот од листата
назад на новиот шеф на листата.
>> Сега ајде да конечно бришење еден јазол од поврзани листа.
Па да речеме имаме некоја друга функција што
е да се најде еден јазол што сакаме да го избришете и ни даде покажувач точно
јазол дека сакате да ја избришете.
Ние дури и не need-- велат дека главата се уште глобално декларирана.
Ние не треба главата тука.
Сите оваа функција се прави е да имаме Пронајдени покажувач токму ние јазол
сакаат да се ослободи од.
Ајде да се ослободи од неа.
Тоа е многу полесно со двојно-поврзани листи.
First-- тоа е всушност само неколку работи.
Ние само треба да се поправи на околните покажувачи јазли, така што тие ги прескокне
јазол што сакаме да го избришете.
И потоа можеме да го избришете тој јазол.
Значи, повторно, ние сме само ќе низ овде.
Ние сме очигледно одлучи дека сакаме да ги избришете X. јазол
И повторно, она што јас сум прави here-- од way--
е општ случај за јазол кој е во средината.
Постојат неколку дополнителни ограничувања кои ви
треба да се разгледа кога ќе се избрише На самиот почеток на листата
или на самиот крај на листата.
Има неколку специјални агол случаи да се справи со таму.
>> Па тоа работи за бришење на јазол во средината на list-- оној кој
има легитимно покажувачот напред и легитимен покажувачот наназад,
легитимни Претходната и следната покажувачот.
Повторно, ако си работат со краевите, можете
треба да се справи со оние малку поинаку,
и ние нема да зборуваме за тоа сега.
Но вие веројатно може да дознаам што треба
треба да се направи само со гледање на ова видео.
>> Значи ние сме изолирани X. X е јазолот сакаме да ги избришете од списокот.
Што ќе правиме?
Прво, ние треба да се преуреди надворешниот покажувачи.
Ние треба да се преуреди 9 следната да ја прескокнете над 13
и точка за која 10-- е она што ние сме само направено.
И ние исто така треба да се преуредите 10 Претходни
да се упати на 9 наместо да укажува до 13.
>> Значи, повторно, ова е дијаграм за да се започне со.
Тоа беше нашиот синџир.
Ние треба да ја прескокнете над 13, но ние треба да се зачува, исто така,
интегритетот на листата.
Ние не сакаме да изгуби било информации во двете насоки.
Значи ние треба да се преуреди покажувачи внимателно
па ние не се скрши синџирот на сите.
>> Значи можеме да кажеме 9 Следна покажувачот укажува на истото место
дека тринаесет Следна покажувач укажува токму сега.
Бидејќи ние сме на крајот ќе сакате да го прескокнете над 13.
Значи каде и 13 поени Следно, сакате девет до точка таму, наместо.
Значи тоа е тоа.
А потоа каде 13 поени назад да, она што доаѓа пред 13,
сакаме да укажеме 10 на тоа, наместо на 13.
Сега се забележи, ако ги следат стрели, ние може да се откажат од 13
без всушност губи секоја информација.
Ние сме чуваат интегритетот на листата, движат и напред и назад.
А потоа можеме да само вид од него се исчисти малку
со повлекување на листата заедно.
Па ние преуредува на покажувачи на двете страни.
А потоа ние ослободени Х јазли, кои се содржани 13,
а ние не се скрши синџирот.
Па ние го сторивме добро.
>> Последната забелешка тука на поврзани листи.
Па и двете singly- и двојно-поврзана листи, како што видовме,
поддршка навистина ефикасна вметнување и бришење на елементи.
Прилично многу може да се направи тоа во временска константа.
Што ние треба да направите за да го избришете елемент само една секунда пред?
Ние се пресели еден покажувач.
Ние се пресели уште еден покажувач.
Ние ослободени X-- зеде три операции.
Тоа секогаш ги зема три операции за избришете дека node-- да ослободи еден јазол.
>> Како да ја внесете?
Па, ние сме само секогаш tacking на почетокот
ако ние сме вметнување ефикасно.
Значи ние треба да rearrange-- во зависност дали е
singly- еден или двојно-поврзана листа, ние би можеле да треба да направите три
или четири операции макс.
Но, повторно, секогаш е три или четири.
Не е важно колку елементи се во нашата листа,
тоа е секогаш три или четири операции- исто како и бришење е секогаш
три или четири операции.
Тоа е постојана време.
Значи тоа е навистина голем.
>> Со низи, што се прави нешто како вметнување вид.
Најверојатно се потсетиме дека вметнување вид не е постојана алгоритам време.
Тоа е всушност прилично скапи.
Значи ова е многу подобро за вметнување.
Но, како што споменав во одделно-поврзани листа видео,
имаме надолна линија и тука, нели?
Ние сме го изгубиле способноста да случаен пристап до елементите.
Не можеме да кажеме, сакам елемент број четири или елемент бројот 10 на поврзани листа
истиот начин на кој можеме да да го направи тоа со низа
или ние може само директно индекс елемент во нашата низа е.
>> И така се обидува да најде елемент во една врска list--
ако пребарување е important-- сега може да потрае линеарното време.
Што е списокот добива подолго, тоа може да потрае еден дополнителен чекор
за секој еден елемент од списокот во цел да се најде она што го барате.
Значи има трговски off.
Таму е малку на про и един елемент тука.
>> И двојно-поврзани листи не се Последниот вид на комбинација структура на податоци
кои ќе се зборува за, преземање на сите основни градбени
блокови на C на ставање заедно.
Бидејќи всушност, може да се па дури и го направи подобро од ова
за да се создаде структура на податоци кои можеби ќе можете да пребарувате преку
во постојан време.
Но повеќе за тоа во друга видео.
>> Јас сум Даг Лојд.
Ова е CS50.