[Грає музика] ДАГ 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.