>> [Грає музика]
>> ДАГ Lloyd: ОК, так що в ця точка в процесі,
ми розглянули багато основам З Ми знаємо багато про змінних, масивів,
покажчики, все, що хороший матеріал.
Ті, все начебто вбудованих подивитися, як основи,
але ми можемо зробити більше, вірно?
Ми можемо об'єднати речі разом в цікавих способів.
>> І так давайте зробимо це, давайте почнемо гілкуватися, що С дає нам,
і почати створювати свій власний дані структури, що використовують ці будівлі
блоки разом, щоб зробити щось дійсно цінним, корисним.
Один зі способів зробити це говорити про колекціях.
Так до сих пір ми мали один тип даних Структура для представлення колекції
з подобається значення, близькі значення.
Це було б масив.
У нас є колекції цілих чисел, або Колекції персонажів і так далі.
>> Структури також впорядкувати дані з Структура для збору інформації,
але це не для збору, як цінності.
Це, як правило, суміш різних типів даних разом всередині одного вікна.
Але це саме по собі не використовується для ланцюга разом
або з'єднати разом схожі предмети, такі як масив.
Масиви ідеально підходять для елемент подивитися, але згадати
що це дуже важко вставити в масив,
якщо ми вставки в самий кінець цього масиву.
>> І кращий приклад у мене є бо це свого роду вставки.
Якщо згадати наше відео на сортування вставками,
було багато Витрати, пов'язані з наявністю
підібрати елементи, і перекласти їх з шляху, щоб відповідати щось
в середині вашого масиву.
Масиви також страждають від іншого проблема, яка є негнучкість.
Коли ми оголошуємо масив, ми отримуємо один постріл на нього.
Ми отримуємо сказати, Я хочу це багато елементів.
Може бути 100, це могло б бути 1 000, це могло б
бути х, де х являє собою число, користувач дав нам у запрошенні або в команді
лінія.
>> Але ми отримати тільки один постріл на нього, ми не потрапити в то говорити про, насправді я
необхідно 101 або мені потрібно х плюс 20.
Занадто пізно, ми вже оголосив Масив, і якщо ми хочемо, щоб отримати 101 або х
плюс 20, ми повинні оголосити зовсім інший масив,
скопіювати всі елементи масиву над, а потім у нас є достатньо.
А що, якщо ми не праві, знову ж, якщо ми насправді потрібно 102 або х плюс 40,
ми повинні зробити це знову.
Так що вони дуже негнучкою для зміни розміру наші дані,
але якщо ми об'єднаємо разом деякі з основ, які ми вже
дізнався про покажчики і споруд, зокрема, з використанням динамічної пам'яті
розподіл з Танос, ми може поставити ці частини разом
створити нові дані structure-- A односвязанни список ми могли б say--
що дозволяє нам рости і скоротиться колекцію значень
і ми не матиме ніякого незайнятого простору.
>> Отже, ще раз, ми називаємо цю ідею, це поняття, пов'язаний список.
Зокрема, в цьому відео ми говорити про однозв'язний список,
а потім ще відео ми поговоримо про подвійно зв'язані списки, які
це просто варіація на тему тут.
Але односвязанни список складається з вузлів,
вузли просто бути абстрактною term-- це просто те, що я дзвоню
це свого роду Структура, в основному, я?
Просто буду називати його node-- і це вузол має двох членів, або два поля.
Він має дані, які зазвичай число, число з плаваючою точкою характер,
або може бути деяким іншим типом даних, що ви визначилися з типом DEF.
І вона містить покажчик на інший вузол того ж типу.
>> Отже, ми маємо дві речі всередині цей вузол, дані і покажчик
на інший вузол.
І якщо ви починаєте візуалізувати це, ви можете думати про це
як ланцюг вузлів, з'єднані один з одним.
У нас є перший вузол, його містить дані і покажчик
до другого вузла, який містить Дані, і покажчик на третьому вузлі.
І ось чому ми називаємо його Зв'язаний список, вони пов'язані один з одним.
>> Що робить це спеціальне Структура вузла виглядати?
Ну, якщо ви пам'ятаєте з нашого відео на визначення користувацьких типів, з типу DEF,
ми можемо визначити structure-- і введіть визначити структуру, як це.
tyepdef структури sllist, а потім я використовуючи значення слова тут довільно
для позначення будь-якого типу даних насправді.
Ви можете перейти на ціле число або поплавця, Ви могли б мати все, що ви хочете.
Це не обмежується тільки цілі числа, або що-небудь подібне.
Так значення тільки довільне Тип даних, а потім покажчик
на інший вузол того ж типу.
>> Тепер, є трохи зловити тут з визначення структури
коли це структура самоврядування посилальної.
Я повинен мати тимчасовий ім'я для мого будови.
В кінці дня я явно хочуть називати його
SLL вузол, що в кінцевому рахунку новий назвати частину мого визначення типу,
але я не можу використовувати SLL вузол в середині цього.
Причина в тому, я не створив тип називається SLL вузол
поки я не вдарив цього остаточну крапку тут.
До цього моменту, я повинен мати ще один спосіб, щоб звернутися до цього типу даних.
>> І це саме посилальної тип даних.
Це, S тип даних з Структура, яка містить дані,
і покажчик на інший Структура одного типу.
Тому мені потрібно, щоб мати можливість звернутися до Цей тип даних, принаймні тимчасово,
так даючи йому тимчасове Ім'я структури sllist
дозволяє мені сказати, то я хочу покажчик на інший структури sllist,
на структуру sllist зірка, а потім після того як я завершив визначення,
Тепер я можу назвати цей тип SLL вузол.
>> Так ось чому ви бачите там тимчасове ім'я тут,
а постійний ім'я тут.
Іноді ви можете побачити визначення структури,
наприклад, що ні самостійно посилальної, що
не їсти ім'я специфікатор тут.
Було б просто сказати TYPEDEF-структуру, відкрити фігурну дужку, а потім визначити його.
Але якщо ви структура саме посилальної, а це один,
Ви повинні вказати тимчасове ім'я типу.
Але в кінцевому підсумку, в даний час що ми зробили це,
ми можемо просто звернутися до ці вузли, агрегати, ці
а SLL вузлів для цілей в решті частини цього відео.
>> Гаразд, так що ми знаємо, як створити зв'язаний список вузол.
Ми знаємо, як визначити зв'язаний список вузлів.
Тепер, якщо ми збираємося, щоб почати використовувати їх, щоб зібрати інформацію,
є пара операцій ми потрібно зрозуміти і працювати.
Ми повинні знати, як створити зв'язаний список з повітря.
Якщо немає вже ніякого списку, ми хочемо, щоб почати один.
Таким чином, ми повинні бути в змозі створити зв'язаний список,
ми повинні, ймовірно, шукати за списком посилань
знайти елемент ми шукаємо.
Ми повинні бути в змозі вставити нові речі в списку,
ми хочемо, щоб наш список, щоб мати можливість рости.
І точно так само, ми хочемо, щоб мати можливість видалити речі з нашого списку,
ми хочемо, щоб наш список, щоб мати можливість скорочуватися.
І в кінці нашого програми, особливо
якщо згадати, що ми динамічного розподілу пам'яті
щоб побудувати ці списки зазвичай ми хочемо, щоб звільнити всі, що пам'ять
коли ми зробили з ним працювати.
І тому ми повинні бути в змозі видалити Весь зв'язаний список в одному невдачу махом.
Так давайте пройдемо деякі з цих операцій
і як ми могли б візуалізувати їх, говорити в псевдокоду коду спеціально.
Тому ми хочемо, щоб створити пов'язані список, так що, можливо, ми
хочу, щоб визначити функцію з цього прототипу.
SLL вузол зірка, створювати, і я проходження в один аргумент, деякі довільні дані
тип знову, деякого довільного типу даних.
Але я returning-- цю функцію слід повернутися до мене покажчик, щоб одноразово
Зв'язаний список вузол.
Знову ж таки, ми намагаємося створити зв'язаний список з повітря,
так що мені потрібно покажчик на що список, коли я зробив.
>> Отже, які ж етапи тут?
Ну, перше, що я збираюся зробити, це динамічно
виділити місце для нового вузла.
Знову ж таки, ми створюємо його з тонкої повітря, так що ми повинні Танос простору для нього.
І, звичайно, відразу після того як ми Танос,
ми завжди перевіряємо, щоб переконатися, що наші pointer-- ми не повернемося нуль.
Тому що, якщо ми будемо намагатися повагу нульовий покажчик,
ми збираємося страждають сегментації, і ми не хочемо цього.
>> Потім ми хочемо, щоб заповнити в полі, ми хочемо, щоб ініціалізувати значення поля
і ініціалізувати наступне поле.
А потім ми хочемо, метою яких в кінцевому підсумку, як Прототип функції indicates-- ми хочемо
повернути покажчик на SLL вузла.
Так що зробити це виглядати візуально?
Ну, по-перше, ми збираємося, щоб динамічно виділити місце для нового вузла SLL,
таким чином, ми malloc-- це візуальне уявлення
вузла ми тільки що створили.
І ми перевіряємо, щоб переконатися, це не null-- в цьому випадку,
картина не матиме показано, якщо це було порожнім,
ми б запустити з пам'яті, так що ми добре йти туди.
Так що тепер ми до кроку С, ініціалізувати поле вузли значення.
Ну, на основі цієї функції дзвоніть, я використовую тут,
Схоже, я хочу, щоб пройти в 6, Так що я 6 в полі значення.
Тепер, ініціалізувати наступне поле.
Ну, що я збираюся зробити там, немає нічого поруч, праворуч,
це єдине, що в списку.
Так що в наступний момент в списку?
>> Він не повинен вказувати на що-небудь, правильно.
Там немає нічого іншого, там, так що концепція ми знаємо, що це nothing--
покажчики на нічого?
Він повинен бути, може бути, ми хочемо покласти порожній покажчик там,
і я буду представляти нуль покажчик, як тільки червоний прапорець,
ми не можемо йти далі.
Як ми побачимо трохи пізніше, ми матимемо в кінцевому рахунку ланцюга
стрілок підключення ці вузли разом,
але коли ви натиснете червона коробка, це нуль,
ми не можемо йти далі, це кінець списку.
>> І, нарешті, ми просто хочемо, щоб повертає вказівник на цей вузол.
Таким чином, ми будемо називати його новим, і повернеться новий
тому він може бути використаний в всі функції його створив.
Так що ми йдемо, Ми створили одноразово Зв'язаний список вузол з повітря,
і тепер у нас є список, ми можемо працювати з.
>> Тепер, скажімо, ми вже великого ланцюга,
і ми хочемо, щоб знайти щось в ньому.
І ми хочемо, функцію, яка збирається повернутися істинним чи хибним, залежно
від того, чи існує значення в цьому списку.
Прототип функції, або Заява для цієї функції,
може виглядати this-- BOOL знайти, і то ми хочемо, щоб пройти в двох аргументів.
>> По-перше, це покажчик на Перший елемент пов'язаного списку.
Це насправді те, що ви будете завжди хочуть, щоб відстежувати,
і насправді може бути те, що Ви навіть поставити в глобальній змінній.
Після того, як ви створюєте список, Ви завжди, завжди
хочу, щоб відстежувати дуже Перший елемент списку.
Таким чином, ви можете звернутися до всі інші елементи, просто по ланцюжку,
без необхідності тримати покажчики в цілості й схоронності кожного елемента.
Вам потрібно тільки стежити за перший одним, якщо вони все зв'язані разом.
>> І тоді друга річ ми передаємо знову
довільно some-- незалежно від типу даних ми
шукаю там всередині ми сподіваємося, один з вузлів у списку.
Отже, які кроки?
Ну, перше, що ми робимо, це ми створюємо покажчик поперечне
вказуючи на голову списків.
Ну, чому ми це робимо, ми вже є вказівник на голову списків,
чому б нам просто не рухатися, що один навколо?
Ну, як я тільки що сказав ,, це дійсно важливо для нас
завжди стежити з дуже перший елемент у списку.
І так насправді краще створити дублікат, що
і використовувати не для переміщення, тому ми ніколи не випадково відійти, або ми завжди
є вказівник на якийсь момент, який Право на перший елемент списку.
Так що краще, щоб створити Другий, який ми використовуємо, щоб рухатися.
>> Тоді ми просто порівняти чи поле значення в цьому вузлі
це те, що ми шукаємо, і, якщо це ні, ми просто переходимо до наступного вузла.
І ми продовжуємо робити що знову, і знову, і знову,
поки ми не знайдемо ні елемент, або ми потрапили
null-- ми досягли кінця списку, і це не було.
Це повинно, ми сподіваємося, дзвонить дзвін для вас, як тільки лінійний пошук,
ми просто тиражування його в одноразово пов'язаний список структура
замість масиву, щоб зробити це.
>> Так ось приклад одноразово зв'язаний список.
Цей складається з п`ять вузлів, і у нас є
покажчик на голову з список, який називається список.
Перше, що ми хочемо зробити, це знову, створіть цей покажчик обходу.
Таким чином, ми тепер маємо два покажчики які вказують на те ж саме.
>> Отже, зверніть увагу тут також, я не повинні Танос будь-який простір для Trav.
Я не кажу, Trav дорівнює Танос те, що вузол вже існує,
що простір в пам'яті вже існує.
Таким чином, все, що я насправді роблю це створюючи ще один покажчик на нього.
Я не mallocing додатковий простір, просто тепер два покажчики
вказуючи на те ж саме.
>> Так 2, що я шукаю?
Ну, немає, так що замість я буде рухатися до наступного.
Так в основному, я б сказав, Трав дорівнює TRAV поруч.
Є 3, що я шукаю, немає.
Так що я як і раніше йти НЕ через, поки врешті-решт
отримати до 6, який є те, що я шукаю Для засноване на виклик функції
У мене у верхній там і так я зробив.
>> Тепер, що якщо елемент я шукаю не в списку,
це ще буде працювати?
Ну, зверніть увагу, що список тут трохи відрізняється,
і це ще одна річ, це Важливо зі зв'язаними списками,
Ви не повинні зберегти їх у певному порядку.
Ви можете, якщо хочете, але Ви, можливо, вже помітили,
що ми не відстежувати те, що номер елемента ми в.
>> І це свого роду одній угоді, що ми є зі зв'язаним списком вірші масивів,
це ми не маємо довільного доступу більше.
Ми не можемо просто сказати, я хочу щоб перейти до 0-й елемент,
або 6-й елемент мого масиву, який я можу зробити в масиві.
Я не можу сказати, що я хочу, щоб перейти до 0-я елемент або 6-й елемент,
або 25-елемент мого пов'язаного списку, немає індекс, пов'язаний з ними.
І так дійсно не має значення якщо ми збережемо наш список в порядку.
Якщо ви хочете, щоб вас , Звичайно, можна, але є
немає причини, чому вони повинні зберегти в будь-якому порядку.
Отже, ще раз, давайте спробуємо знайти 6 в цьому списку.
Ну, ми починаємо на початок, ми не знаходимо 6,
а потім ми продовжимо, не знайшовши 6, поки ми в кінцевому підсумку не отримаєте тут.
Так що зараз Trav вказує на вузол містить 8, а шість не там.
>> Так що наступний крок буде щоб перейти до наступного вказівником,
так би мовити, Trav дорівнює TRAV поруч.
Ну, Trav поруч, зазначено червоний коробка є, є недійсним.
Так що нікуди йти, і тому на даному етапі
ми можемо зробити висновок, що ми досягли кінець пов'язаного списку,
і 6 не там.
І це будуть повернуті брехня в цьому випадку.
>> ОК, як ми вставляємо новий вузол у зв'язаному списку?
Таким чином, ми змогли створити зв'язаний список з нізвідки,
але ми, ймовірно, хочете, щоб побудувати ланцюжок, а не
створити купу різних списків.
Ми хочемо, щоб один список, що має купу вузлів в ньому,
а не купка списків з одного вузла.
Таким чином, ми не можемо просто продовжувати використовувати Створити функція, яку ми визначили раніше, в даний час ми
вставити в Список, який вже існує.
>> Так даному випадку, ми збираємося пройти в двох аргументів,
покажчик на голову, що пов'язані список, який ми хочемо додати к.
Знову ж, це, чому це так Важливо, що ми завжди
відслідковувати, тому це єдиний спосіб ми дійсно
повинні звернутися до весь список просто покажчик на перший елемент.
Таким чином, ми хочемо передати в покажчик на перший елемент цього,
і все, що ми значення хочете додати в список.
І врешті-решт ця функція буде повертати покажчик
новому главі пов'язаного списку.
>> Які етапи тут?
Ну, як з створення, ми повинні динамічно виділяти
місця для нового вузла, і перевірте, щоб що ми не вистачити пам'яті, знову ж таки,
тому що ми використовуємо Танос.
Потім ми хочемо, щоб заповнити і вставте вузол,
так поставити номер, все, що Допустимі, у вузлі.
Ми хочемо, щоб вставити вузол на початок пов'язаного списку.
>> Там це причина того, що я хочу зробити це, і це
можливо, варто приймати другу щоб призупинити відео тут,
і думаю, про те, чому я хотів би вставити на початку пов'язаний
Список.
Знову ж таки, я згадував раніше що він робить насправді не
має значення, якщо ми збережемо його в будь порядок, так що, можливо, що це ключ.
І ви бачили, що сталося б, якби ми хотів, метою яких або просто на секунду
тому, коли ми йшли через пошук Ви
міг бачити те, що може станеться, якщо ми намагалися
вставити в кінець списку.
Тому що ми не маємо покажчик на кінець списку.
>> Таким чином, причина того, що я хотів би вставити на початку,
тому, що я можу зробити це негайно.
У мене є вказівник на початок, і ми побачимо це у візуальний в секунду.
Але якщо я хочу, щоб вставити в кінці кінців, Я повинен почати з самого початку,
пройти весь шлях до кінець, а потім прикріпити його.
Так що буде означати, що вставки в кінець списку
став би про п Операція, повертаючись
до обговорення обчислювальна складність.
Це було б стати про н роботи, де також список отримав більше, і більше,
і більше, це буде ставати все більш і важче лавірувати то
на кінці.
Але це завжди дуже легко лавірувати щось на на початку,
Ви завжди на початку.
>> І ми побачимо, візуальний це знову.
І те, як тільки ми зробили, коли ми вставили новий вузол,
ми хочемо, щоб повернутися до нашої покажчик новий глава пов'язаного списку, який
так як ми вставки на початок, насправді буде
покажчик на вузол ми тільки що створили.
Давайте візуалізувати це, тому що я думаю, що це допоможе.
>> Так ось наш список, вона складається з чотири елементи, вузол, що містить 15,
що вказує на вузол містить 9, який
вказує на вузлі, що містить 13, що вказує на вузол, що містить
10, який має нульове Покажчик в своєму наступному покажчик
так що це кінець списку.
Тому ми хочемо, щоб вставити Новий вузол зі значенням 12
На початку цього Список, що ми робимо?
Ну, по-перше, ми Танос простір для вузол, а потім покласти 12 там.
>> Так що тепер ми досягли точка прийняття рішення, вірно?
У нас є кілька покажчики, які ми могли б
рухатися, що треба рухатися, ми в першу чергу?
Чи повинні ми зробити 12 пункт новий глава list--
або, вибачте, ми повинні зробити 12 вказують на старий чолі списку?
Або ми повинні сказати, що Список в даний час починається в 12 років.
Там це розходження там, і ми будемо дивитися
на те, що відбувається з обома в секунду.
>> Але це призводить до велика тема для бічній панелі,
який що один з каверзні речі зі зв'язаними списками
є організація покажчики в правильному порядку.
Якщо ви перемістите речі з того, Ви можете в кінцевому підсумку випадково
сиротами інше списку.
І ось тому приклад.
Отже, давайте з ідеєю of-- Ну, ми тільки що створили 12.
Ми знаємо, 12 буде новий глава списку,
і так, чому б нам просто не перейти покажчик Список вказати там.
>> ОК, так що це добре.
Так що тепер, коли робить наступний пункт 12?
Я маю на увазі, візуально ми бачимо що буде вказувати на 15,
як люди це дійсно очевидно для нас.
Як комп'ютер знаєте?
Ми не маємо нічого вказуючи на 15 більше, вірно?
>> Ми втратили можливість посилатися на 15.
Ми не можемо сказати, новий стрілку поруч рівних то, немає нічого.
Насправді, ми осиротіли інша частина списку
тим самим, ми випадково порушив ланцюг.
І ми, звичайно, не хочете, щоб зробити це.
>> Отже, давайте поверніться і спробуйте це знову.
Можливо, те, що потрібно зробити, це встановити наступний покажчик 12 в
до старого чолі списку перших, то ми можемо перемістити список більше.
І справді, тобто Правильний порядок, що ми
необхідно дотримуватися, коли ми роботи з однозв'язний список.
Ми завжди хочемо, щоб підключити Новий елемент у списку,
перш, ніж ми прийняти таку важливим кроком зміни
де глава пов'язаного списку.
Знову ж, це такий фундаментальний річ, ми не хочемо, щоб втратити його.
>> Тому ми хочемо, щоб переконатися, що всі пов'язані разом,
перш ніж ми перейдемо цей покажчик.
І так це буде правильний порядок, який є підключення 12 до списку,
то кажуть, що список починається 12.
Якби ми сказали список починається в 12 і потім спробував підключити 12 в список,
ми вже бачили, що відбувається.
Ми втрачаємо список помилково.
>> Отже, ще одна річ, щоб говорити про.
Що робити, якщо ми хочемо, щоб позбутися від весь пов'язаний список відразу?
Знову ж таки, ми mallocing Все це простір, і тому ми
потрібно звільнити його, коли ми зробили.
Так що тепер ми хочемо, щоб видалити весь пов'язаний список.
Ну, те, що ми хочемо зробити?
>> Якщо ми досягли нульовий покажчик, ми хочете, щоб зупинити, інакше, просто видаліть
інша частина списку, а потім звільнити мене.
Видалити іншу частину списку, і потім звільнити поточний вузол.
Що це схоже, те, що техніка у нас говорили
про раніше це звучить як?
Видалити всі інші, то повернутися і видалити мене.
>> Це рекурсія, ми зробили Проблема трохи менше,
ми говоримо видалити всіх ще, то ви можете видалити мене.
А далі вниз по дорозі, що вузол скажу, видалити всі інші.
Але врешті-решт ми отримаємо в Точка де список порожній,
і це наша база випадок.
>> Отже, давайте поглянемо на це, і як це може працювати.
Так ось наш список, це те ж саме список ми просто говоримо,
і є кроки.
Там дуже багато тексту тут, але сподіваюся, візуалізація допоможе.
>> Таким чином, ми have-- і я також витягнув до нашої кадрів стека ілюстрації
з нашого відео на стеків викликів, і, сподіваюся, все це
разом покажу вам, що відбувається.
Так от наш код псевдокод.
Якщо ми досягнемо нуль покажчик, зупинити, інакше,
видалити іншу частину списку, Потім звільнити поточний вузол.
Так що зараз, list-- покажчик, що ми
передаючи знищити очок до 12.
12 не є нульовим покажчиком, тому ми збирається видалити іншу частину списку.
>> Що є видалення Решта з нас бере участь?
Ну, це означає, роблячи подзвоніть, щоб знищити, кажучи
що 15 це початок Інша частина списку, який ми хочемо знищити.
І тому виклик, щоб знищити 12 вид на утримання.
Це заморожені там, чекаючи подзвоніть, щоб знищити 15, щоб закінчити свою роботу.
>> Ну, 15 не є нульовим покажчиком, і так що це, щоб сказати, все в порядку,
добре, видалити іншу частину списку.
Інша частина списку починає в 9, і тому ми просто
чекати, поки ви не видалите все, що матеріал, а потім повернутися і видалити мене.
Ну 9 скаже, ну, Я не порожній покажчик,
так що видаліть інші список тут.
І тому спробуйте і знищити 13.
13 говорить, що я не порожній покажчик, Те ж саме, він передає долар.
10 не порожній покажчик, 10 містить порожній покажчик,
але 10 не саме по собі є NULL покажчик прямо зараз,
і так вона проходить долар теж.
>> А тепер список точок там, це дійсно буде вказувати на some--
якщо у мене було більше місця в зображенні, це буде вказувати на деякої випадкової простору
що ми не знаємо, що це таке.
Це нульовий покажчик, хоча, список буквально тепер встановлено, що це значення нульові.
Це вказує прямо в цій червоній коробці.
Ми досягли нульовий покажчик, тому ми можемо зупинити, і ми зробили.
>> І так, що фіолетовий кадру now-- на Верх stack-- це активний кадр,
але це робиться.
Якщо ми досягли нульовий покажчик, зупинитися.
Ми нічого не робимо, ми не може звільнити нульовий покажчик,
ми не Танос будь простір, і тому ми зробили.
Так, що функції кадру руйнується, і ми
resume-- ми забрати, де ми залишили від з наступною вищої одного, який
це темно-синя рамка тут.
Таким чином, ми забрати там, де ми зупинилися.
Ми видалили іншу частину Список вже, так що тепер ми
збирається звільнити поточні вузли.
Так що тепер ми можемо звільнити цей вузол, і в даний час ми досягли кінця функції.
І так, що функція кадр буде знищений, і ми забрати в блакитному один.
>> Так що says-- я вже done-- видалення іншої частини списку, так
звільнити поточний вузол.
А тепер жовтий кадр назад на вершині стека.
І так, як ви бачите, ми тепер руйнуючи список справа наліво.
>> Що сталося б, хоча, Якби ми зробили щось не так?
Так само, як коли ми намагалися додати елемент.
Якщо ми переплуталися, якщо ланцюг ми не підключити покажчики
в правильному порядку, якщо ми просто звільнив перший елемент,
якщо ми просто звільнили голова списку, тепер ми
немає ніякого способу послатися на інша частина списку.
І тому ми б сиротами все,
ми б мали те, що називається витік пам'яті.
Якщо ви пам'ятаєте з нашого відео на динамічному розподілі пам'яті,
це не дуже хороша річ.
>> Отже, як я вже сказав, кілька операцій,
що ми повинні використовувати для роботи з пов'язаний список ефективно.
І ви, можливо, помітили, я опустив одну, видалення одного елемента із зв'язаного
Список.
Тому я зробив це це насправді свого роду
складно думати про те, як видалити один елемент з однократно
Зв'язаний список.
Ми повинні бути в змозі пропустити щось в списку, який
означає, що ми отримуємо в point-- ми хочете видалити цей node--
але для того, щоб зробити це так, ми не втрачати інформацію,
ми повинні пов'язувати це вузол тут, тут.
>> Так що я, ймовірно, зробив це неправильно з візуальної точки зору.
Таким чином, ми знаходимося на початку нашого Список, ми протікає через,
ми хочемо, щоб видалити цей вузол.
Якщо ми просто видалити його, ми порушили ланцюжок.
Цей вузол прямо тут відноситься до всього іншого,
він містить ланцюг звідси на.
>> Отже, що ми повинні зробити, насправді після того як ми дістатися до цієї точки,
що ми повинні зробити крок назад один, і підключити цей вузол до цього вузла,
так що ми можемо потім видалити один у середині.
Але поодинці пов'язані списків не забезпечити нам шлях назад.
Таким чином, ми повинні або зберегти два покажчики, і перемістити їх
зразок вимикання кроком, один за одного, як ми йдемо, або дістатися до точки,
а потім відправити другий покажчик кінця.
І, як ви бачите, це може отримати трохи брудно.
На щастя, у нас є ще один спосіб вирішити, що
коли ми говоримо про подвійно зв'язані списки.
>> Я Дуг Ллойд, це CS50.