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