>> [Гуляе музыка]
Даг Lloyd: Добра.
Так што калі вы толькі што скончылі, што відэа паасобку, звязаных спісаў прабачце
Я пакінуў цябе на трохі захапляльным.
Але я рады, што ты тут, каб скончыць гісторыя двойчы звязаных спісаў.
>> Так што, калі вы памятаеце з што відэа, мы гаварылі
пра тое, як односвязный Спісы ходзяць у нашу здольнасць
каб мець справу з інфармацыяй дзе колькасць элементаў
або лік элементаў у спіс можа расці або скарачацца.
Цяпер мы можам мець справу з нешта падобнае, дзе
мы не маглі справіцца з ёй з масівамі.
>> Але яны пакутуюць ад аднаго крытычным абмежаваннем,
з'яўляецца тое, што з односвязный Спіс, мы можам толькі калі-небудзь рухацца
у адным кірунку па спісе.
І толькі рэальная сітуацыя дзе, што можа стаць праблемай
калі мы спрабавалі выдаліць адзін элемент.
І мы нават не абмяркоўваем, як гэта зрабіць у аднакратна звязанага спісу ў псевдокоде.
Гэта, вядома, можна выканаць, але гэта можа быць трохі клопатаў.
Так што, калі вы апынецеся ў сітуацыі, калі
Вы спрабуеце выдаліць асобныя элементы з спісу
ці гэта будзе неабходна што вы будзеце выдаляць
асобныя элементы з спіс, вы можаце
разгледзець пытанне аб выкарыстанні ўдвая звязаны спіс замест аднакратна звязанага спісу.
Таму ўдвая звязаныя спісы дазваляюць вам каб перамясціць абедзве наперад і назад
па спісе замест толькі наперад праз list--
проста дадаўшы адзін дадатковы элемент нашаму вызначэнні структуры
для двойчы звязанага спісу вузла.
>> Зноў жа, калі вы не збіраецеся быць выдаленне асобных элементаў
ад list--, таму што мы, дадаўшы дадатковае поле для нашай структуры
вызначэнне, самі вузлы для двунакіраваных спісаў
будуць больш.
Яны збіраюцца прыняць да больш байт памяці.
І так, калі гэта не тое, Вы збіраецеся трэба зрабіць,
Вы маглі б вырашыць, што гэта не варта кампраміс
прыйдзецца марнаваць дадатковы байт памяці патрабуецца
для двойчы звязанага спісу, калі вы не будзе выдаленне асобных элементаў.
Але яны таксама выдатна для іншых рэчаў таксама.
>> Так як я ўжо сказаў, мы проста павінны дадаць адна поле нашай структуры
definition-- гэта паняцце папярэдняга паказальніка.
Так што з аднакратна звязанага спісу, мы маюць значэнне і наступны паказальнік,
таму ўдвая звязаны спіс толькі мае спосаб рухацца ў зваротным кірунку, а таксама.
>> У цяперашні час у односвязный Спіс відэа, мы гаварылі
пра іх пяць з Асноўныя рэчы, якія трэба будзе
ў стане зрабіць, каб працаваць са звязанымі спісамі.
І для большасці з іх, з тым, што гэта ўдвая звязаны спіс
на самай справе не вялікі скачок.
Мы можам па-ранейшаму шукаць праз, проста рухацца наперад ад пачатку да канца.
Мы ўсё яшчэ можам стварыць вузел з разрэджанае паветра, у значнай ступені той жа самы шлях.
Мы можам выдаліць спісы даволі гэтак жа, занадта.
Адзіныя рэчы, якія некалькі адрозніваюцца,
сапраўды, устаўляюць новыя вузлы ў спісе,
і мы, нарэшце, казаць аб выдаленні адзін элемент з спісу, а таксама.
Зноў жа, у значнай ступені тры іншых, мы
не буду казаць пра іх прама зараз, таму што яны проста
вельмі дробныя недахопы на ідэях абмеркавалі у аднакратна звязанага спісу відэа.
>> Такім чынам, давайце ўставіць новы вузел у двойчы звязаны спіс.
Мы гаварылі пра робіце гэта для односвязный спіс, а таксама,
але ёсць пара дадатковых ловіць з двунакіраваных спісаў.
Мы [? праходзячы?] у галаву з пералічыць тут і некаторыя адвольнае значэнне,
і мы хочам, каб атрымаць новы кіраўнік спісу з гэтай функцыі.
Вось чаму ён вяртае dllnode зорку.
Такім чынам, якія крокі?
Яны, ізноў жа, вельмі падобныя у односвязный спіс
з адной дадатковай таго.
Мы хочам, каб вылучае прастору для новага вузел і праверка, каб пераканацца, што гэта дзейнічае.
Мы хочам, каб запоўніць гэты вузел да з тым, што інфармацыя, якую мы
хачу паставіць у ім.
Апошняе, што нам трэба, каб do-- дадатковая рэч, якую мы павінны зрабіць, rather--
гэта выправіць Папярэдні паказальнік старога чале спісу.
Памятаеце, што з-за з двусвязных спісаў,
мы можам рухацца наперад і backwards-- якія
азначае, што кожны вузел на самай справе паказвае каб замест двух іншых вузлоў толькі адзін.
І таму мы павінны выправіць стары галава спісу
пазначыць таму, каб новы кіраўнік звязаны спіс, які быў чымсьці
мы не павінны зрабіць, перш чым.
І, як і раней, мы проста вяртаць паказальнік на новы чале спісу.
>> Дык вось спіс.
Мы хочам, каб ўставіць 12 у гэтым спісе.
Звярніце ўвагу, што схема трохі адрозніваецца.
Кожны вузел ўтрымлівае тры fields-- Дадзеныя і наступны паказальнік ў чырвоным,
і паказальнік Папярэдні сінім.
Нічога не прыходзіць да 15 вузла, так што яго Папярэдні паказальнік NULL.
Гэта пачатак спісу.
Там няма нічога перад ім.
І нічога не прыходзіць пасля 10 вузла, а так што наступны паказальнік з'яўляецца несапраўдным, а таксама.
>> Так давайце дадамо 12 да гэтага спісу.
Мы павінны [неразборліва] прастору для вузла.
Ставім 12 ўнутры яго.
І зноў жа, мы павінны быць вельмі асцярожныя, каб не разарваць ланцуг.
Мы хочам, каб пераставіць ўказальнікі ў правільным парадку.
А часам, што, магчыма, mean-- як мы ўбачым у прыватнасці,
з delete--, што ў нас ёсць некаторыя залішнія паказальнікі, але гэта нармальна.
>> Так што мы хочам зрабіць у першую чаргу?
Я б рэкамендаваў рэчы, якія вы павінны, верагодна,
зрабіць гэта, каб запоўніць паказальнікі 12 вузел, перш чым дакранацца хто-небудзь яшчэ.
Так што 12 будзе паказваць на наступны?
15.
Тое, што прыходзіць да 12?
Нічога.
Цяпер мы запоўнілі дадатковая інфармацыя ў 12
таму ён мае папярэдні, наступны, і каштоўнасць.
>> Цяпер мы можам мець гэты дадатковы 15-- крок, які мы казалі about-- мы
можа мець 15 кропку назад да 12.
А зараз мы можам перайсці галаву звязаны спіс, каб быць 12.
Так што гэта вельмі падобна на тое, што мы рабілі з аднакратна звязаных спісаў,
для дадатковай стадыі, за выключэннем падлучэння старую галаву спісу
вярнуцца да новай чале спісу.
>> Зараз давайце, нарэшце, выдаліць вузел з звязанага спісу.
Так што давайце, у нас ёсць некаторыя іншыя функцыі, якія
знаходзіць вузел, мы хочам, каб выдаліць і даў нам паказальнік дакладна
вузел, які мы хочам выдаліць.
Мы нават не need-- сказаць Галава ўсё яшчэ глабальна абвешчаныя.
Нам не трэба галаву тут.
Усё гэта функцыя робіць гэта мы ў знайшоў паказальнік на сапраўды вузла мы
хачу, каб пазбавіцца ад.
Давайце пазбавіцца ад яго.
Гэта нашмат прасцей з двойчы звязаныя спісы.
First-- гэта на самай справе ўсяго пару рэчаў.
Нам проста трэба, каб выправіць навакольны паказальнікі вузлоў, так што яны Прапусціць
вузел, мы хочам, каб выдаліць.
І тады мы можам выдаліць гэты вузел.
Такім чынам, яшчэ раз, мы проста перажывае тут.
Мы, відаць, вырашыў, што мы хочам, каб выдаліць вузел X.
І зноў, што я рабіць here-- па way--
гэта агульны выпадак для вузел, які знаходзіцца ў сярэдзіне.
Ёсць пара дадатковыя агаворкі, якія вы
неабходна ўлічваць, калі вы выдаліце самы пачатак спісу
або ў самым канцы спісу.
Там ёсць пара спецыяльных вуглавыя выпадкі, каб мець справу з там.
>> Так гэта працуе для выдалення любога вузла У сярэдзіне list-- той, які
мае законнае паказальнік наперад і законным паказальнік таму,
законным Папярэдняя і Наступны паказальнік.
Зноў жа, калі вы працуеце з канцамі, вы
трэба апрацоўваць тыя крыху па-іншаму,
і мы не збіраемся казаць аб тым, што ў цяперашні час.
Але вы, верагодна, высветліць, што трэба
зрабіць, проста назіраючы гэта відэа.
>> Такім чынам, мы ізаляваныя Х. Х вузел мы хочам, каб выдаліць з спісу.
Што мы робім?
Па-першае, мы павінны пераставіць вонкавыя паказальнікі.
Мы павінны перабудаваць 9-х побач з прапусціць 13
і паказваюць на 10-- якія гэта тое, што мы толькі што зрабілі.
І мы таксама павінны змяніць 10-х Папярэдні
пазначыць да 9, а не паказваючы на ​​13.
>> Такім чынам, яшчэ раз, гэта было схема, каб пачаць з.
Гэта была наша ланцуг.
Мы павінны прапусціць 13, але мы павінны таксама захаваць
цэласнасць спісу.
Мы не хочам страціць ні Інфармацыя ў любым кірунку.
Такім чынам, мы павінны пераставіць паказальнікі старанна
такім чынам, мы не разарваць ланцуг наогул.
>> Такім чынам, мы можам сказаць, 9 у наступным паказальнік паказвае на тое ж месца
што Трынаццатай Наступны паказальнік паказвае прама цяпер.
Таму што мы ў канчатковым выніку захочуць прапусціць 13.
Так, дзе 13 балаў Далей, вы хачу дзевяць пазначыць там замест.
Дык вось, што.
А потым, дзе 13 балаў таму каб, усё, што прыходзіць да 13,
мы хочам, каб паказаць 10 да таго, што замест 13.
Зараз звернеце ўвагу, калі вы будзеце прытрымлівацца стрэлкі, мы можам зваліцца 13
фактычна не страты інфармацыі.
Мы захавалі цэласнасць спісу, рухацца як наперад, так і назад.
І тады мы можам проста накшталт з яго прыбраць трохі
пацягнуўшы спіс разам.
Такім чынам, мы пераставілі паказальнікі на абодва бакі.
А потым мы вызвалілі Х вузел, які утрымліваў 13,
і мы не разарваць ланцуг.
Так мы і зрабілі добра.
>> Канчатковая нота тут на звязаных спісах.
Так як адназарадных і двойчы звязаны спісы, як мы бачылі,
падтрымка сапраўды эфектыўным ўстаўкі і выдаленне элементаў.
Вы можаце вельмі шмат зрабіць ён ў пастаянным часу.
Што мы павінны зрабіць, каб выдаліць элемент проста другі таму?
Мы пераехалі адзін паказальнік.
Мы пераехалі іншы паказальнік.
Мы вызвалілі x-- ўзяў тры аперацыі.
Ён заўсёды займае тры аперацыі на выдаліць гэтую node-- вызваліць вузел.
>> Як мы ўстаўляем?
Ну, мы проста заўсёды лавіруючы на ​​пачатак
калі мы ўстаўкі эфектыўна.
Такім чынам, мы павінны rearrange-- у залежнасці ад таго, калі гэта
адназарадных або двойчы звязаны Спіс, мы, магчыма, спатрэбіцца зрабіць тры
ці чатыры аперацыі макс.
Але, зноў жа, гэта заўсёды тры ці чатыры.
Гэта не мае значэння, колькі элементы знаходзяцца ў нашым спісе,
гэта заўсёды тры ці чатыры operations-- гэтак жа, як выдаленне заўсёды
тры ці чатыры аперацыі.
Гэта пастаянная часу.
Так што гэта сапраўды выдатна.
>> З масівамі, мы рабілі нешта накшталт ўстаўкі роду.
Вы, напэўна, нагадаць, што ўвядзенне Сартаваць не з'яўляецца пастаяннай алгарытм раз.
Гэта на самай справе даволі дорага.
Так што гэта значна лепш, для ўстаўкі.
Але як я ўжо казаў у односвязный спіс відэа,
мы атрымалі зваротную тут таксама, праўда?
Мы страцілі здольнасць да адвольны доступ да элементаў.
Мы не можам сказаць, я хачу, элемент нумар чатыры або элемент нумар 10 з звязанага спісу
гэтак жа, як мы можам зрабіць з масівам
або мы можам проста наўпрост індэкс у элеменце нашай масіва.
>> І такім чынам спрабуючы знайсці элемент у звязаным list--
калі пошук па important-- Цяпер можна ўзяць лінейнае час.
Як спіс становіцца больш, гэта можа заняць адзін дадатковы крок
для кожнага элемента ў спісе ў каб знайсці тое, што мы шукаем.
Так што кампрамісы.
Там гэта трохі пра і супраць элементам тут.
>> І ўдвая-звязаныя спісы не з'яўляюцца Апошні выгляд камбінацыі структуры дадзеных
што мы будзем казаць, прымаючы ўсё асноўнае будынак
блокі З разам.
Таму што на самой справе, мы можам нават лепш, чым гэта
стварыць структуру дадзеных, што Вы маглі б быць у стане шукаць праз
ў пастаянным часу таксама.
Але пра гэта ў іншы відэа.
>> Я Дуг Лойд.
Гэта CS50.