1 00:00:00,000 --> 00:00:03,381 >> [Играет музыка] 2 00:00:03,381 --> 00:00:04,604 3 00:00:04,604 --> 00:00:05,520 ДАГ Lloyd: Ладно. 4 00:00:05,520 --> 00:00:07,860 Так что если вы только что закончили, что видео по отдельности, связанных списков извините 5 00:00:07,860 --> 00:00:09,568 Я оставил тебя на немного захватывающим. 6 00:00:09,568 --> 00:00:12,790 Но я рад, что ты здесь, чтобы закончить история дважды связанных списков. 7 00:00:12,790 --> 00:00:15,250 >> Так что, если вы помните из что видео, мы говорили 8 00:00:15,250 --> 00:00:18,500 о том, как односвязный Списки ходят в нашу способность 9 00:00:18,500 --> 00:00:22,090 чтобы иметь дело с информацией где количество элементов 10 00:00:22,090 --> 00:00:24,442 или число элементов в список может расти или сокращаться. 11 00:00:24,442 --> 00:00:26,400 Теперь мы можем иметь дело с что-то подобное, где 12 00:00:26,400 --> 00:00:28,310 мы не могли справиться с ней с массивами. 13 00:00:28,310 --> 00:00:30,560 >> Но они страдают от одного критическим ограничением, 14 00:00:30,560 --> 00:00:33,790 является то, что с односвязный Список, мы можем только когда-либо двигаться 15 00:00:33,790 --> 00:00:36,200 в одном направлении по списку. 16 00:00:36,200 --> 00:00:39,010 И только реальная ситуация где, что может стать проблемой 17 00:00:39,010 --> 00:00:41,250 когда мы пытались удалить один элемент. 18 00:00:41,250 --> 00:00:46,000 И мы даже не обсуждаем, как это сделать в однократно связанного списка в псевдокоде. 19 00:00:46,000 --> 00:00:48,797 Это, конечно, выполнимо, но это может быть немного хлопот. 20 00:00:48,797 --> 00:00:50,630 Так что, если вы окажетесь в ситуации, когда 21 00:00:50,630 --> 00:00:53,175 Вы пытаетесь удалить отдельные элементы из списка 22 00:00:53,175 --> 00:00:55,430 или это будет необходимо что вы будете удалять 23 00:00:55,430 --> 00:00:57,970 отдельные элементы из список, вы можете 24 00:00:57,970 --> 00:01:02,090 рассмотреть вопрос об использовании вдвойне связанный список вместо однократно связанного списка. 25 00:01:02,090 --> 00:01:06,320 Потому вдвойне связанные списки позволяют вам чтобы переместить обе вперед и назад 26 00:01:06,320 --> 00:01:09,340 по списку вместо только вперед через list-- 27 00:01:09,340 --> 00:01:13,950 просто добавив один дополнительный элемент нашему определению структуры 28 00:01:13,950 --> 00:01:16,690 для дважды связанного списка узла. 29 00:01:16,690 --> 00:01:19,770 >> Опять же, если вы не собираетесь быть удаление отдельных элементов 30 00:01:19,770 --> 00:01:24,810 от list--, потому что мы, добавив дополнительное поле для нашей структуры 31 00:01:24,810 --> 00:01:28,340 определение, сами узлы для двунаправленных списков 32 00:01:28,340 --> 00:01:29,550 будут больше. 33 00:01:29,550 --> 00:01:31,600 Они собираются принять до более байт памяти. 34 00:01:31,600 --> 00:01:34,160 И так, если это не то, Вы собираетесь нужно сделать, 35 00:01:34,160 --> 00:01:36,300 Вы могли бы решить, что это не стоит компромисс 36 00:01:36,300 --> 00:01:39,360 придется тратить дополнительное байт памяти требуется 37 00:01:39,360 --> 00:01:43,940 для дважды связанного списка, если вы не будет удаление отдельных элементов. 38 00:01:43,940 --> 00:01:46,760 Но они также здорово для других вещей тоже. 39 00:01:46,760 --> 00:01:51,260 >> Так как я уже сказал, мы просто должны добавить одна поле нашей структуры 40 00:01:51,260 --> 00:01:55,360 definition-- это понятие предыдущего указателя. 41 00:01:55,360 --> 00:01:58,620 Так что с однократно связанного списка, мы имеют значение и следующий указатель, 42 00:01:58,620 --> 00:02:02,850 поэтому вдвойне связанный список только имеет способ двигаться в обратном направлении, а также. 43 00:02:02,850 --> 00:02:04,960 >> В настоящее время в односвязный Список видео, мы говорили 44 00:02:04,960 --> 00:02:07,210 о них пять из Основные вещи, которые нужно будет 45 00:02:07,210 --> 00:02:09,449 в состоянии сделать, чтобы работать со связанными списками. 46 00:02:09,449 --> 00:02:12,880 И для большинства из них, с тем, что это вдвойне связанный список 47 00:02:12,880 --> 00:02:14,130 на самом деле не большой скачок. 48 00:02:14,130 --> 00:02:17,936 Мы можем по-прежнему искать через, просто двигаться вперед от начала до конца. 49 00:02:17,936 --> 00:02:20,810 Мы все еще можем создать узел из разреженный воздух, в значительной степени тот же самый путь. 50 00:02:20,810 --> 00:02:23,591 Мы можем удалить списки довольно так же, слишком. 51 00:02:23,591 --> 00:02:25,340 Единственные вещи, которые несколько отличаются, 52 00:02:25,340 --> 00:02:28,970 действительно, вставляют новые узлы в списке, 53 00:02:28,970 --> 00:02:33,722 и мы, наконец, говорить об удалении один элемент из списка, а также. 54 00:02:33,722 --> 00:02:35,430 Опять же, в значительной степени три других, мы 55 00:02:35,430 --> 00:02:37,888 не буду говорить о них прямо сейчас, потому что они просто 56 00:02:37,888 --> 00:02:43,920 очень мелкие недочеты на идеях обсудили в однократно связанного списка видео. 57 00:02:43,920 --> 00:02:46,292 >> Итак, давайте вставить новый узел в дважды связанный список. 58 00:02:46,292 --> 00:02:48,750 Мы говорили о делаете это для односвязный список, а также, 59 00:02:48,750 --> 00:02:52,020 но есть пара дополнительных ловит с двунаправленных списков. 60 00:02:52,020 --> 00:02:55,280 Мы [? проходя?] в голову из перечислить здесь и некоторые произвольное значение, 61 00:02:55,280 --> 00:02:58,600 и мы хотим, чтобы получить новый руководитель списка из этой функции. 62 00:02:58,600 --> 00:03:01,414 Вот почему он возвращает dllnode звезду. 63 00:03:01,414 --> 00:03:02,330 Итак, какие шаги? 64 00:03:02,330 --> 00:03:04,496 Они, опять же, очень похожи в односвязный список 65 00:03:04,496 --> 00:03:05,670 с одной дополнительной того. 66 00:03:05,670 --> 00:03:08,900 Мы хотим, чтобы выделяет пространство для нового узел и проверка, чтобы убедиться, что это действует. 67 00:03:08,900 --> 00:03:11,510 Мы хотим, чтобы заполнить этот узел до с тем, что информация, которую мы 68 00:03:11,510 --> 00:03:12,564 хочу поставить в нем. 69 00:03:12,564 --> 00:03:15,480 Последнее, что нам нужно, чтобы do-- дополнительная вещь, которую мы должны сделать, rather-- 70 00:03:15,480 --> 00:03:19,435 это исправить Предыдущий указатель старого главе списка. 71 00:03:19,435 --> 00:03:21,310 Помните, что из-за из двусвязных списков, 72 00:03:21,310 --> 00:03:23,110 мы можем двигаться вперед и backwards-- которые 73 00:03:23,110 --> 00:03:27,080 означает, что каждый узел на самом деле указывает чтобы вместо двух других узлов только один. 74 00:03:27,080 --> 00:03:29,110 И поэтому мы должны исправить старый голова списка 75 00:03:29,110 --> 00:03:32,151 указать назад, чтобы новый глава связанный список, который был чем-то 76 00:03:32,151 --> 00:03:33,990 мы не должны сделать, прежде чем. 77 00:03:33,990 --> 00:03:37,420 И, как и прежде, мы просто возвращать указатель на новый главе списка. 78 00:03:37,420 --> 00:03:38,220 >> Так вот список. 79 00:03:38,220 --> 00:03:40,144 Мы хотим, чтобы вставить 12 в этом списке. 80 00:03:40,144 --> 00:03:42,060 Обратите внимание, что схема немного отличается. 81 00:03:42,060 --> 00:03:47,710 Каждый узел содержит три fields-- Данные и следующий указатель в красном, 82 00:03:47,710 --> 00:03:50,170 и указатель Предыдущая синим. 83 00:03:50,170 --> 00:03:54,059 Ничего не приходит до 15 узла, так что его Предыдущая указатель NULL. 84 00:03:54,059 --> 00:03:55,350 Это начало списка. 85 00:03:55,350 --> 00:03:56,560 Там нет ничего перед ним. 86 00:03:56,560 --> 00:04:03,350 И ничего не приходит после 10 узла, а так что следующий указатель является недействительным, а также. 87 00:04:03,350 --> 00:04:05,616 >> Так давайте добавим 12 к этому списку. 88 00:04:05,616 --> 00:04:08,070 Мы должны [неразборчиво] пространство для узла. 89 00:04:08,070 --> 00:04:11,480 Ставим 12 внутри него. 90 00:04:11,480 --> 00:04:14,840 И опять же, мы должны быть очень осторожны, чтобы не разорвать цепь. 91 00:04:14,840 --> 00:04:17,144 Мы хотим, чтобы переставить указатели в правильном порядке. 92 00:04:17,144 --> 00:04:19,519 А иногда, что, возможно, mean-- как мы увидим в частности, 93 00:04:19,519 --> 00:04:24,120 с delete--, что у нас есть некоторые избыточные указатели, но это нормально. 94 00:04:24,120 --> 00:04:25,750 >> Так что мы хотим сделать в первую очередь? 95 00:04:25,750 --> 00:04:28,290 Я бы рекомендовал вещи, которые вы должны, вероятно, 96 00:04:28,290 --> 00:04:35,350 сделать это, чтобы заполнить указатели 12 узел, прежде чем прикасаться кто-нибудь еще. 97 00:04:35,350 --> 00:04:38,640 Так что 12 будет указывать на следующий? 98 00:04:38,640 --> 00:04:39,860 15. 99 00:04:39,860 --> 00:04:42,430 То, что приходит до 12? 100 00:04:42,430 --> 00:04:43,640 Ничего. 101 00:04:43,640 --> 00:04:46,280 Теперь мы заполнили дополнительная информация в 12 102 00:04:46,280 --> 00:04:49,320 поэтому он имеет предыдущий, следующий, и ценность. 103 00:04:49,320 --> 00:04:53,505 >> Теперь мы можем иметь этот дополнительный 15-- шаг, который мы говорили about-- мы 104 00:04:53,505 --> 00:04:56,590 может иметь 15 точку назад до 12. 105 00:04:56,590 --> 00:04:59,634 А теперь мы можем перейти голову связанный список, чтобы быть 12. 106 00:04:59,634 --> 00:05:02,550 Так что это очень похоже на то, что мы делали с однократно связанных списков, 107 00:05:02,550 --> 00:05:06,940 для дополнительной стадии, за исключением подключения старую голову списка 108 00:05:06,940 --> 00:05:09,810 вернуться к новой главе списка. 109 00:05:09,810 --> 00:05:12,170 >> Теперь давайте, наконец, удалить узел из связанного списка. 110 00:05:12,170 --> 00:05:14,350 Так что давайте, у нас есть некоторые другие функции, которые 111 00:05:14,350 --> 00:05:18,080 находит узел, мы хотим, чтобы удалить и дал нам указатель точно 112 00:05:18,080 --> 00:05:19,710 узел, который мы хотим удалить. 113 00:05:19,710 --> 00:05:22,360 Мы даже не need-- сказать Голова все еще глобально объявлены. 114 00:05:22,360 --> 00:05:23,590 Нам не нужно голову здесь. 115 00:05:23,590 --> 00:05:26,830 Все это функция делает это мы в нашел указатель на точно узла мы 116 00:05:26,830 --> 00:05:28,090 хочу, чтобы избавиться от. 117 00:05:28,090 --> 00:05:28,940 Давайте избавиться от него. 118 00:05:28,940 --> 00:05:31,859 Это намного проще с дважды связанные списки. 119 00:05:31,859 --> 00:05:33,650 First-- это на самом деле всего пара вещей. 120 00:05:33,650 --> 00:05:38,760 Нам просто нужно, чтобы исправить окружающий указатели узлов, так что они Пропустить 121 00:05:38,760 --> 00:05:40,240 узел, мы хотим, чтобы удалить. 122 00:05:40,240 --> 00:05:43,484 И тогда мы можем удалить этот узел. 123 00:05:43,484 --> 00:05:45,150 Итак, еще раз, мы просто переживает здесь. 124 00:05:45,150 --> 00:05:49,625 Мы, видимо, решил, что мы хотим, чтобы удалить узел X. 125 00:05:49,625 --> 00:05:51,500 И опять, что я делать here-- по way-- 126 00:05:51,500 --> 00:05:54,580 это общий случай для узел, который находится в середине. 127 00:05:54,580 --> 00:05:56,547 Есть пара дополнительные оговорки, которые вы 128 00:05:56,547 --> 00:05:59,380 необходимо учитывать, когда вы удалите самое начало списка 129 00:05:59,380 --> 00:06:01,040 или в самом конце списка. 130 00:06:01,040 --> 00:06:03,730 Там есть пара специальных угловые случаи, чтобы иметь дело с там. 131 00:06:03,730 --> 00:06:07,960 >> Так это работает для удаления любого узла В середине list-- тот, который 132 00:06:07,960 --> 00:06:11,550 имеет законное указатель вперед и законным указатель назад, 133 00:06:11,550 --> 00:06:14,460 законным Предыдущая и Следующая указатель. 134 00:06:14,460 --> 00:06:16,530 Опять же, если вы работаете с концами, вы 135 00:06:16,530 --> 00:06:18,500 нужно обрабатывать те немного по-другому, 136 00:06:18,500 --> 00:06:19,570 и мы не собираемся говорить о том, что в настоящее время. 137 00:06:19,570 --> 00:06:21,319 Но вы, вероятно, выяснить, что нужно 138 00:06:21,319 --> 00:06:24,610 сделать, просто наблюдая это видео. 139 00:06:24,610 --> 00:06:28,910 >> Таким образом, мы изолированы Х. Х узел мы хотим, чтобы удалить из списка. 140 00:06:28,910 --> 00:06:30,140 Что мы делаем? 141 00:06:30,140 --> 00:06:32,800 Во-первых, мы должны переставить наружные указатели. 142 00:06:32,800 --> 00:06:35,815 Мы должны перестроить 9-х рядом с пропустить 13 143 00:06:35,815 --> 00:06:38,030 и указывают на 10-- которые это то, что мы только что сделали. 144 00:06:38,030 --> 00:06:41,180 И мы также должны изменить 10-х Предыдущая 145 00:06:41,180 --> 00:06:44,610 указать до 9, а не указывая на 13. 146 00:06:44,610 --> 00:06:46,490 >> Итак, еще раз, это было схема, чтобы начать с. 147 00:06:46,490 --> 00:06:47,730 Это была наша цепь. 148 00:06:47,730 --> 00:06:51,027 Мы должны пропустить 13, но мы должны также сохранить 149 00:06:51,027 --> 00:06:52,110 целостность списка. 150 00:06:52,110 --> 00:06:54,680 Мы не хотим потерять ни Информация в любом направлении. 151 00:06:54,680 --> 00:06:59,620 Таким образом, мы должны переставить указатели тщательно 152 00:06:59,620 --> 00:07:02,240 таким образом, мы не разорвать цепь вообще. 153 00:07:02,240 --> 00:07:05,710 >> Таким образом, мы можем сказать, 9 в следующем указатель указывает на то же место 154 00:07:05,710 --> 00:07:08,040 что Тринадцатой Следующая указатель указывает прямо сейчас. 155 00:07:08,040 --> 00:07:10,331 Потому что мы в конечном итоге захотят пропустить 13. 156 00:07:10,331 --> 00:07:13,750 Так, где 13 баллов Далее, вы хочу девять указать там вместо. 157 00:07:13,750 --> 00:07:15,200 Так вот, что. 158 00:07:15,200 --> 00:07:20,370 А потом, где 13 баллов назад чтобы, все, что приходит до 13, 159 00:07:20,370 --> 00:07:24,800 мы хотим, чтобы указать 10 к тому, что вместо 13. 160 00:07:24,800 --> 00:07:29,290 Теперь обратите внимание, если вы будете следовать стрелки, мы можем упасть 13 161 00:07:29,290 --> 00:07:32,380 фактически не потери информации. 162 00:07:32,380 --> 00:07:36,002 Мы сохранили целостность списка, двигаться как вперед, так и назад. 163 00:07:36,002 --> 00:07:38,210 И тогда мы можем просто вроде из его убрать немного 164 00:07:38,210 --> 00:07:40,930 потянув список вместе. 165 00:07:40,930 --> 00:07:43,270 Таким образом, мы переставили указатели на обе стороны. 166 00:07:43,270 --> 00:07:46,231 А потом мы освободили Х узел, который содержал 13, 167 00:07:46,231 --> 00:07:47,480 и мы не разорвать цепь. 168 00:07:47,480 --> 00:07:50,980 Так мы и сделали хорошо. 169 00:07:50,980 --> 00:07:53,000 >> Конечная нота здесь на связанных списках. 170 00:07:53,000 --> 00:07:55,990 Так как однозарядных и дважды связаны списки, как мы видели, 171 00:07:55,990 --> 00:07:58,959 поддержка действительно эффективным вставки и удаление элементов. 172 00:07:58,959 --> 00:08:00,750 Вы можете очень многое сделать он в постоянном времени. 173 00:08:00,750 --> 00:08:03,333 Что мы должны сделать, чтобы удалить элемент просто второй назад? 174 00:08:03,333 --> 00:08:04,440 Мы переехали один указатель. 175 00:08:04,440 --> 00:08:05,920 Мы переехали другой указатель. 176 00:08:05,920 --> 00:08:07,915 Мы освободили x-- взял три операции. 177 00:08:07,915 --> 00:08:14,500 Он всегда занимает три операции на удалить эту node-- освободить узел. 178 00:08:14,500 --> 00:08:15,280 >> Как мы вставляем? 179 00:08:15,280 --> 00:08:17,280 Ну, мы просто всегда лавируя на начало 180 00:08:17,280 --> 00:08:19,400 если мы вставки эффективно. 181 00:08:19,400 --> 00:08:21,964 Таким образом, мы должны rearrange-- в зависимости от того, если это 182 00:08:21,964 --> 00:08:24,380 однозарядных или дважды связаны Список, мы, возможно, потребуется сделать три 183 00:08:24,380 --> 00:08:26,824 или четыре операции макс. 184 00:08:26,824 --> 00:08:28,365 Но, опять же, это всегда три или четыре. 185 00:08:28,365 --> 00:08:30,531 Это не имеет значения, сколько элементы находятся в нашем списке, 186 00:08:30,531 --> 00:08:33,549 это всегда три или четыре operations-- так же, как удаление всегда 187 00:08:33,549 --> 00:08:35,320 три или четыре операции. 188 00:08:35,320 --> 00:08:36,919 Это постоянная времени. 189 00:08:36,919 --> 00:08:38,169 Так что это действительно здорово. 190 00:08:38,169 --> 00:08:40,620 >> С массивами, мы делали что-то вроде вставки рода. 191 00:08:40,620 --> 00:08:44,739 Вы, наверное, напомнить, что введение Сортировать не является постоянной алгоритм раз. 192 00:08:44,739 --> 00:08:46,030 Это на самом деле довольно дорого. 193 00:08:46,030 --> 00:08:48,840 Так что это гораздо лучше, для вставки. 194 00:08:48,840 --> 00:08:51,840 Но как я уже говорил в односвязный список видео, 195 00:08:51,840 --> 00:08:54,030 мы получили обратную здесь тоже, верно? 196 00:08:54,030 --> 00:08:57,580 Мы потеряли способность к произвольный доступ к элементам. 197 00:08:57,580 --> 00:09:02,310 Мы не можем сказать, я хочу, элемент номер четыре или элемент номер 10 из связанного списка 198 00:09:02,310 --> 00:09:04,990 так же, как мы можем сделать с массивом 199 00:09:04,990 --> 00:09:08,630 или мы можем просто напрямую индекс в элементе нашей массива. 200 00:09:08,630 --> 00:09:10,930 >> И таким образом пытаясь найти элемент в связанном list-- 201 00:09:10,930 --> 00:09:15,880 если поиск по important-- Теперь можно взять линейное время. 202 00:09:15,880 --> 00:09:18,330 Как список становится больше, это может занять один дополнительный шаг 203 00:09:18,330 --> 00:09:22,644 для каждого элемента в списке в чтобы найти то, что мы ищем. 204 00:09:22,644 --> 00:09:23,560 Так что компромиссы. 205 00:09:23,560 --> 00:09:25,780 Там это немного про и против элементом здесь. 206 00:09:25,780 --> 00:09:29,110 >> И вдвойне-связанные списки не являются Последний вид комбинации структуры данных 207 00:09:29,110 --> 00:09:32,840 что мы будем говорить, принимая все основное здание 208 00:09:32,840 --> 00:09:34,865 блоки С воедино. 209 00:09:34,865 --> 00:09:37,900 Потому что на самом деле, мы можем даже лучше, чем это 210 00:09:37,900 --> 00:09:41,970 создать структуру данных, что Вы могли бы быть в состоянии искать через 211 00:09:41,970 --> 00:09:43,360 в постоянном времени тоже. 212 00:09:43,360 --> 00:09:46,080 Но об этом в другой видео. 213 00:09:46,080 --> 00:09:47,150 >> Я Дуг Ллойд. 214 00:09:47,150 --> 00:09:49,050 Это CS50. 215 00:09:49,050 --> 00:09:50,877