[Играет музыка] ДАГ 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.