>> [Мусиц плаиинг]
Даг Ллоид: У реду.
Дакле, ако сте управо завршио да видео на појединачно-повезаних листи извињавања
Оставио сам ти га на помало цлиффхангер.
Али драго ми је да си овде да завршим прича о двоструко-повезаних листама.
>> Дакле, ако се сећате из тај видео, разговарали смо
о томе како појединачно повезан Листе уради присуствују нашу способност
да се бави информацијама где је број елемената
или број ставки у листа може да расте или смањити.
Сада може да се бави тако нешто, где
нисмо могли носити са тим са низовима.
>> Али они не пате од једног критична ограничења која
је да са појединачно повезан листа, можемо само икада мове
у једном смјеру кроз листу.
И једини реално стање где да може да постане проблем
било када смо покушавали да избрисали један елемент.
И нисмо ни разговарали о томе како да то урадите у појединачно-повезане листе у псеудокоду.
То је свакако изводљиво, али то може бити мало муке.
Дакле, ако се нађете у ситуацији у којој
покушавате да избришете појединачних елемената са листе
или ће то бити потребно да ћете бити брисање
појединачних елемената из списак, можда ћете желети
узети у обзир помоћу двоструко повезан список уместо појединачно-повезане листе.
Због двоструко-повезане листе вам омогућити да померите оба напред и назад
кроз листу уместо само напред кроз лист--
само додавањем један додатни елемент да нашој дефиницији структура
за двоструко-повезане листе чвора.
>> Опет, ако нећеш да се брисање појединачних елемената
од лист-- јер смо додајући екстра поље нашој структури
дефиницији, сами чворови за двоструко-повезаних листи
ће бити већи.
Они ће узети до више бајтова меморије.
И тако, ако то није нешто идете да треба да урадите,
можда одлучити да је није вредно компромис
морати да проведете екстра бајтова меморије потребна
за двоструко-повезане листе, ако ниси Биће брисања појединачних елемената.
Али они су и кул за друге ствари.
>> Дакле, као што сам рекао, имамо само да додам једна поље нашој структури
дефинитион-- ову представу из претходног показивачем.
Дакле, са појединачно-повезане листе, ми има вредност и следећи показивач,
тако да је двоструко повезана листа има само начин за кретање уназад као добро.
>> Сада у појединачно повезан Листа Видео, разговарали смо
о ово су пет од Главне ствари које треба да буде
у стању да уради за рад са повезаним листама.
И за већину ових, чињенице да је то двоструко повезана листа
није баш велики скок.
Још увек можете претраживати путем од само напредовање од почетка до краја.
Још увек можемо створити чвор оут оф редак ваздух, скоро на исти начин.
Ми можете брисати листе прилично много исто превише начин.
Једине ствари које су суптилно разликују,
Заиста, стављате нови чворови у попис,
и коначно ћемо разговарати о брисању један елемент са листе као добро.
Опет, прилично остала три, ми смо
неће да говори о њима сада, јер само су
веома мале Твеакс о идејама расправља у појединачно-повезане листе видео.
>> Дакле, хајде да убаците нови чвор у двоструко-повезане листе.
Разговарали смо о радим ово због појединачно повезане листе, као и,
али постоји неколико екстра хвата са двоструко-повезаних листама.
Ми смо [? пролази?] у Шеф лист овде и неке произвољне вредности,
и желимо да добијете нову главу листе из ове функције.
Зато враћа дллноде звезду.
Дакле, шта су кораци?
Они су, опет, веома сличне да појединачно повезане листе
са једним додатним тога.
Желимо да одваја простор за нови чвор и проверите да ли је важећа.
Желимо да попуни ту чвор до са све информације смо
Желим да се стави у њу.
Последња ствар коју треба да Па-- екстра ствар коју треба да урадите, ратхер--
је да се поправи Претходна показивач старог шефа листе.
Имајте на уму да због од двоструко-везани листе,
можемо да идемо напред и бацквардс-- који
значи да сваки чвор у ствари указује да друга два чвора уместо само једног.
И тако морамо да поправимо стари носилац листе
уназад указују на новог шефа повезаног листа, који је био нешто
нисмо имали раније учинити.
И као и раније, само смо ретурн а показивач на новог шефа листе.
>> Дакле, овде је списак.
Желимо да убаците 12 у овом списку.
Обратите пажњу на то дијаграм је нешто другачија.
Сваки чвор садржи три фиелдс-- података, а Следеће показивач у црвено,
а Претходна показивач у плаво.
Ништа не долази пре 15 чвора, тако да је његово Претходна показивач је нула.
То је почетак листе.
Не постоји ништа пред собом.
И ништа не долази након 10 чвора, и тако да је Следеће показивач је нула као добро.
>> Дакле, хајде да додамо 12 до овој листи.
Требамо [неразумљиво] простор за чвора.
Ставили смо 12 у њему.
А онда опет, морамо да будемо стварно Пазите да не прекинути ланац.
Желимо да преуредили показивачи у исправном редоследу.
А понекад да би Мислим-- као што ћемо видети посебно
са делете-- да имамо неке редундант показивачи, али то је у реду.
>> Дакле, шта желимо да урадимо прво?
Ја бих препоручујемо ствари које вероватно треба
урадите је да попуни савете од 12 чвор пре него што додирнете било ко други.
Дакле, шта се дешава 12 да укаже на следећи?
15.
Оно што долази пре 12?
Ništa.
Сада смо напуни Додатне информације у 12
тако да има Претходни, нект, и вредност.
>> Сада можемо да имамо 15-- ово екстра корак смо причаш-- смо ми
може имати 15 степени уназад до 12.
А сада можемо да идемо главу повезаног листа да буде и 12.
Дакле, то је прилично слично ономе што смо су радили са појединачно-повезаних листи,
осим екстра корак повезује стару главу листе
Назад на новог шефа листе.
>> Сада ћемо коначно брисање чвор из повезане листе.
Рецимо да имамо неки други функција која
је проналажење чвор желимо да избришете и дао нам је показивач тачно
чвор који желимо да избришете.
Ми чак не морају-- кажем Глава је још увек у свету проглашена.
Не треба нам овде главу.
Све ово функција ради је имамо пронашао показивач на потпуно смо ми чвора
Желим да се отараси.
Идемо се отарасим тога.
То је много лакше са двоструко повезана листа.
Фирст-- то је у ствари само пар ствари.
Само морамо да поправимо околину показивачи чворова "тако да прескочим
чвор желимо да избришете.
И онда можемо избрисати те чвор.
Дакле, опет, ми ћемо само кроз овде.
Ми смо очигледно одлучио да желимо да избришете Кс. чвор
И опет, шта ћу ради овдје-- од стране ваи--
је општи случај за чвор који је у средини.
Постоји неколико ектра упозорења да
треба да размотре када бришете само почетак листе
или на самом крају листе.
Постоји неколико посебна цорнер случајеви да се баве тамо.
>> Дакле, ово ради за брисање било ког чвора у средини лист-- оне која
има легитимно показивач напријед и легитимна показивач уназад,
легитиман Претходна Следећа показивач и.
Опет, ако радите са крајевима, ви
треба да рукује онима мало другачије,
а ми не идемо у причати о томе сада.
Али вероватно можеш схватити шта је потребно
да се уради само гледајући овај видео.
>> Тако смо изоловани Кс Кс је чвор желимо избрисати са листе.
Шта да радимо?
Прво, морамо да преуредили се ван показивачи.
Морамо да преуреде 9 је поред прескочим 13
и указују на 10-- који је оно што смо управо урадили.
И ми такође треба да преуредити 10 је Претходна
да укаже на 9 уместо указујући на 13.
>> Дакле, да поновим, ово је био дијаграм за почетак.
То је био наш ланац.
Морамо да прескочим 13, али морамо да се сачува
интегритет листе.
Не желимо да изгубимо било информације у оба смера.
Зато морамо да преуредили показивачи пажљиво
тако да не прекинути ланац уопште.
>> Дакле, можемо рећи 9 је следећи показивач указује на истом месту
да Тринаест је Следећа показивач указује управо сада.
Зато што смо на крају смо хтети да прескочим 13.
Дакле, кад год је 13 поена следеће, вас Желим девет тамо укаже уместо тога.
Дакле, то је то.
А онда где год 13 поена назад да, шта год долази пре 13,
желимо да укажемо 10 оној уместо 13.
Сада обратите пажњу, ако пратите стрелице, можемо пад од 13
без стварног губитка података.
Ми смо стално интегритет листе, креће и унапред и уназад.
А онда можемо некако да га почисти мало
повлачењем листу заједно.
Тако смо преуредио показивачи на обе стране.
И онда смо ослободили Кс чвор који садржи 13,
и нисмо прекинути ланац.
Тако смо и урадили добро.
>> Завршни напомена на повезаним листама.
Дакле, како сингли- и двоструко повезана листе, као што смо видели,
подршка заиста ефикасан уметање и брисање елемената.
Можете углавном радимо је у сталном време.
Шта треба да урадимо да избришете елемент само секунд пре?
Преселили смо се један показивач.
Преселили смо се још један показивач.
Ослободили смо Кс-- је три операције.
Увек је потребно три операције на избрисати те ноде-- да ослободи чвор.
>> Како убацити?
Па, ми смо само увек тацкинг на почетку
ако смо ефикасно уметање.
Зато морамо да реарранге-- у зависности од тога да ли је
сингли- или двоструко повезана листа, можемо да урадимо три треба
или четири операције макс.
Али опет, то је увек три или четири.
Није битно колико елементи су у нашем листу,
Увек је три или четири оператионс-- као и брисање увек
три или четири операције.
То је константа време.
Дакле, то је стварно супер.
>> Са низовима, што смо радили нешто попут уметања врсте.
Вероватно се сећате тог уметања врста није константа време алгоритам.
То је заправо прилично скупо.
Дакле, ово је много боље за уметање.
Али као што сам поменуо у појединачно повезане листе видео,
имамо мана превише, овде?
Изгубили смо могућност да насумице приступ елементима.
Не можемо да кажемо, хоћу елемент број четири или елемент број 10 из повезане листе
исти начин на који можемо то са низом
или можемо само директно индекса у елемент нашег арраи екипе.
>> И тако покушава да нађе елемент у повезаном лист--
ако је претраживање ВАЗНО сада могу узети линеарног времена.
Како је списак је дужи и дужи, то Можда се један додатни корак
за сваки појединачни елемент листе у како би пронашли оно што тражите.
Дакле, постоји компромисе.
Ту је мало про и против елеменат овде.
>> И двоструко-повезане листе нису последња врста структуре података комбинације
да ћемо говорити о, узимајући све основне зграду
блокови Ц стављајући заједно.
Јер, у ствари, можемо чак и боље од овога
да створи структуру података која можда ћете моћи да претражујете
у сталном време превише.
Али више о томе у другом видеу.
>> Ја сам Доуг Лојд.
Ово је ЦС50.