1
00:00:00,000 --> 00:00:02,832
>> [Грає музика]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> ДАГ Lloyd: ОК, так що в
ця точка в процесі,

4
00:00:08,560 --> 00:00:15,300
ми розглянули багато основам З
Ми знаємо багато про змінних, масивів,

5
00:00:15,300 --> 00:00:17,610
покажчики, все, що хороший матеріал.

6
00:00:17,610 --> 00:00:21,610
Ті, все начебто вбудованих
подивитися, як основи,

7
00:00:21,610 --> 00:00:23,880
але ми можемо зробити більше, вірно?

8
00:00:23,880 --> 00:00:27,930
Ми можемо об'єднати речі
разом в цікавих способів.

9
00:00:27,930 --> 00:00:31,010
>> І так давайте зробимо це, давайте почнемо
гілкуватися, що С дає нам,

10
00:00:31,010 --> 00:00:35,270
і почати створювати свій власний дані
структури, що використовують ці будівлі

11
00:00:35,270 --> 00:00:40,590
блоки разом, щоб зробити щось
дійсно цінним, корисним.

12
00:00:40,590 --> 00:00:43,420
Один зі способів зробити це
говорити про колекціях.

13
00:00:43,420 --> 00:00:48,360
Так до сих пір ми мали один тип даних
Структура для представлення колекції

14
00:00:48,360 --> 00:00:51,030
з подобається значення, близькі значення.

15
00:00:51,030 --> 00:00:52,350
Це було б масив.

16
00:00:52,350 --> 00:00:57,020
У нас є колекції цілих чисел, або
Колекції персонажів і так далі.

17
00:00:57,020 --> 00:01:00,890
>> Структури також впорядкувати дані з
Структура для збору інформації,

18
00:01:00,890 --> 00:01:03,220
але це не для збору, як цінності.

19
00:01:03,220 --> 00:01:08,090
Це, як правило, суміш різних типів даних
разом всередині одного вікна.

20
00:01:08,090 --> 00:01:10,750
Але це саме по собі не
використовується для ланцюга разом

21
00:01:10,750 --> 00:01:16,920
або з'єднати разом схожі
предмети, такі як масив.

22
00:01:16,920 --> 00:01:20,960
Масиви ідеально підходять для
елемент подивитися, але згадати

23
00:01:20,960 --> 00:01:24,262
що це дуже важко
вставити в масив,

24
00:01:24,262 --> 00:01:26,470
якщо ми вставки в
самий кінець цього масиву.

25
00:01:26,470 --> 00:01:29,730
>> І кращий приклад у мене є
бо це свого роду вставки.

26
00:01:29,730 --> 00:01:31,650
Якщо згадати наше відео
на сортування вставками,

27
00:01:31,650 --> 00:01:34,110
було багато
Витрати, пов'язані з наявністю

28
00:01:34,110 --> 00:01:37,970
підібрати елементи, і перекласти їх
з шляху, щоб відповідати щось

29
00:01:37,970 --> 00:01:41,290
в середині вашого масиву.

30
00:01:41,290 --> 00:01:44,690
Масиви також страждають від іншого
проблема, яка є негнучкість.

31
00:01:44,690 --> 00:01:47,150
Коли ми оголошуємо масив,
ми отримуємо один постріл на нього.

32
00:01:47,150 --> 00:01:49,790
Ми отримуємо сказати, Я хочу
це багато елементів.

33
00:01:49,790 --> 00:01:51,940
Може бути 100, це могло б
бути 1 000, це могло б

34
00:01:51,940 --> 00:01:55,930
бути х, де х являє собою число, користувач
дав нам у запрошенні або в команді

35
00:01:55,930 --> 00:01:56,630
лінія.

36
00:01:56,630 --> 00:01:59,905
>> Але ми отримати тільки один постріл на нього, ми
не потрапити в то говорити про, насправді я

37
00:01:59,905 --> 00:02:04,360
необхідно 101 або мені потрібно х плюс 20.

38
00:02:04,360 --> 00:02:07,910
Занадто пізно, ми вже оголосив
Масив, і якщо ми хочемо, щоб отримати 101 або х

39
00:02:07,910 --> 00:02:12,050
плюс 20, ми повинні оголосити
зовсім інший масив,

40
00:02:12,050 --> 00:02:15,540
скопіювати всі елементи масиву
над, а потім у нас є достатньо.

41
00:02:15,540 --> 00:02:19,880
А що, якщо ми не праві, знову ж,
якщо ми насправді потрібно 102 або х плюс 40,

42
00:02:19,880 --> 00:02:21,970
ми повинні зробити це знову.

43
00:02:21,970 --> 00:02:26,250
Так що вони дуже негнучкою
для зміни розміру наші дані,

44
00:02:26,250 --> 00:02:29,360
але якщо ми об'єднаємо разом деякі
з основ, які ми вже

45
00:02:29,360 --> 00:02:33,230
дізнався про покажчики і споруд,
зокрема, з використанням динамічної пам'яті

46
00:02:33,230 --> 00:02:36,180
розподіл з Танос, ми
може поставити ці частини разом

47
00:02:36,180 --> 00:02:40,960
створити нові дані structure-- A
односвязанни список ми могли б say--

48
00:02:40,960 --> 00:02:45,400
що дозволяє нам рости і
скоротиться колекцію значень

49
00:02:45,400 --> 00:02:48,800
і ми не матиме ніякого незайнятого простору.

50
00:02:48,800 --> 00:02:53,320
>> Отже, ще раз, ми називаємо цю ідею,
це поняття, пов'язаний список.

51
00:02:53,320 --> 00:02:56,320
Зокрема, в цьому відео ми
говорити про однозв'язний список,

52
00:02:56,320 --> 00:02:59,185
а потім ще відео ми поговоримо
про подвійно зв'язані списки, які

53
00:02:59,185 --> 00:03:01,560
це просто варіація на тему тут.

54
00:03:01,560 --> 00:03:05,200
Але односвязанни список
складається з вузлів,

55
00:03:05,200 --> 00:03:08,559
вузли просто бути абстрактною term--
це просто те, що я дзвоню

56
00:03:08,559 --> 00:03:10,350
це свого роду
Структура, в основному, я?

57
00:03:10,350 --> 00:03:16,190
Просто буду називати його node-- і це
вузол має двох членів, або два поля.

58
00:03:16,190 --> 00:03:20,300
Він має дані, які зазвичай
число, число з плаваючою точкою характер,

59
00:03:20,300 --> 00:03:23,790
або може бути деяким іншим типом даних,
що ви визначилися з типом DEF.

60
00:03:23,790 --> 00:03:29,290
І вона містить покажчик на
інший вузол того ж типу.

61
00:03:29,290 --> 00:03:34,710
>> Отже, ми маємо дві речі всередині
цей вузол, дані і покажчик

62
00:03:34,710 --> 00:03:36,380
на інший вузол.

63
00:03:36,380 --> 00:03:39,370
І якщо ви починаєте візуалізувати
це, ви можете думати про це

64
00:03:39,370 --> 00:03:42,280
як ланцюг вузлів,
з'єднані один з одним.

65
00:03:42,280 --> 00:03:45,070
У нас є перший вузол, його
містить дані і покажчик

66
00:03:45,070 --> 00:03:49,110
до другого вузла, який містить
Дані, і покажчик на третьому вузлі.

67
00:03:49,110 --> 00:03:52,940
І ось чому ми називаємо його
Зв'язаний список, вони пов'язані один з одним.

68
00:03:52,940 --> 00:03:56,070
>> Що робить це спеціальне
Структура вузла виглядати?

69
00:03:56,070 --> 00:04:01,120
Ну, якщо ви пам'ятаєте з нашого відео на
визначення користувацьких типів, з типу DEF,

70
00:04:01,120 --> 00:04:05,400
ми можемо визначити structure-- і
введіть визначити структуру, як це.

71
00:04:05,400 --> 00:04:11,240
tyepdef структури sllist, а потім я
використовуючи значення слова тут довільно

72
00:04:11,240 --> 00:04:13,891
для позначення будь-якого типу даних насправді.

73
00:04:13,891 --> 00:04:16,890
Ви можете перейти на ціле число або поплавця,
Ви могли б мати все, що ви хочете.

74
00:04:16,890 --> 00:04:19,389
Це не обмежується тільки
цілі числа, або що-небудь подібне.

75
00:04:19,389 --> 00:04:22,790
Так значення тільки довільне
Тип даних, а потім покажчик

76
00:04:22,790 --> 00:04:26,310
на інший вузол того ж типу.

77
00:04:26,310 --> 00:04:29,690
>> Тепер, є трохи зловити
тут з визначення структури

78
00:04:29,690 --> 00:04:33,030
коли це структура самоврядування посилальної.

79
00:04:33,030 --> 00:04:35,340
Я повинен мати тимчасовий
ім'я для мого будови.

80
00:04:35,340 --> 00:04:37,640
В кінці дня я
явно хочуть називати його

81
00:04:37,640 --> 00:04:43,030
SLL вузол, що в кінцевому рахунку новий
назвати частину мого визначення типу,

82
00:04:43,030 --> 00:04:47,450
але я не можу використовувати SLL вузол
в середині цього.

83
00:04:47,450 --> 00:04:51,430
Причина в тому, я не
створив тип називається SLL вузол

84
00:04:51,430 --> 00:04:55,200
поки я не вдарив цього остаточну крапку тут.

85
00:04:55,200 --> 00:04:59,720
До цього моменту, я повинен мати
ще один спосіб, щоб звернутися до цього типу даних.

86
00:04:59,720 --> 00:05:02,440
>> І це саме
посилальної тип даних.

87
00:05:02,440 --> 00:05:06,314
Це, S тип даних з
Структура, яка містить дані,

88
00:05:06,314 --> 00:05:08,480
і покажчик на інший
Структура одного типу.

89
00:05:08,480 --> 00:05:11,750
Тому мені потрібно, щоб мати можливість звернутися до
Цей тип даних, принаймні тимчасово,

90
00:05:11,750 --> 00:05:14,910
так даючи йому тимчасове
Ім'я структури sllist

91
00:05:14,910 --> 00:05:18,540
дозволяє мені сказати, то я хочу
покажчик на інший структури sllist,

92
00:05:18,540 --> 00:05:24,690
на структуру sllist зірка, а потім
після того як я завершив визначення,

93
00:05:24,690 --> 00:05:27,220
Тепер я можу назвати цей тип SLL вузол.

94
00:05:27,220 --> 00:05:30,520
>> Так ось чому ви бачите там
тимчасове ім'я тут,

95
00:05:30,520 --> 00:05:31,879
а постійний ім'я тут.

96
00:05:31,879 --> 00:05:33,920
Іноді ви можете побачити
визначення структури,

97
00:05:33,920 --> 00:05:36,570
наприклад, що ні
самостійно посилальної, що

98
00:05:36,570 --> 00:05:39,390
не їсти ім'я специфікатор тут.

99
00:05:39,390 --> 00:05:43,040
Було б просто сказати TYPEDEF-структуру,
відкрити фігурну дужку, а потім визначити його.

100
00:05:43,040 --> 00:05:45,620
Але якщо ви структура саме
посилальної, а це один,

101
00:05:45,620 --> 00:05:49,010
Ви повинні вказати
тимчасове ім'я типу.

102
00:05:49,010 --> 00:05:51,310
Але в кінцевому підсумку, в даний час
що ми зробили це,

103
00:05:51,310 --> 00:05:53,620
ми можемо просто звернутися до
ці вузли, агрегати, ці

104
00:05:53,620 --> 00:05:57,900
а SLL вузлів для цілей
в решті частини цього відео.

105
00:05:57,900 --> 00:06:00,900
>> Гаразд, так що ми знаємо, як
створити зв'язаний список вузол.

106
00:06:00,900 --> 00:06:03,240
Ми знаємо, як визначити
зв'язаний список вузлів.

107
00:06:03,240 --> 00:06:06,670
Тепер, якщо ми збираємося, щоб почати
використовувати їх, щоб зібрати інформацію,

108
00:06:06,670 --> 00:06:10,360
є пара операцій ми
потрібно зрозуміти і працювати.

109
00:06:10,360 --> 00:06:12,860
Ми повинні знати, як створити
зв'язаний список з повітря.

110
00:06:12,860 --> 00:06:14,901
Якщо немає вже ніякого списку,
ми хочемо, щоб почати один.

111
00:06:14,901 --> 00:06:16,960
Таким чином, ми повинні бути в змозі
створити зв'язаний список,

112
00:06:16,960 --> 00:06:19,130
ми повинні, ймовірно, шукати
за списком посилань

113
00:06:19,130 --> 00:06:21,830
знайти елемент ми шукаємо.

114
00:06:21,830 --> 00:06:24,430
Ми повинні бути в змозі вставити
нові речі в списку,

115
00:06:24,430 --> 00:06:25,930
ми хочемо, щоб наш список, щоб мати можливість рости.

116
00:06:25,930 --> 00:06:28,638
І точно так само, ми хочемо, щоб мати можливість
видалити речі з нашого списку,

117
00:06:28,638 --> 00:06:30,250
ми хочемо, щоб наш список, щоб мати можливість скорочуватися.

118
00:06:30,250 --> 00:06:32,160
І в кінці нашого
програми, особливо

119
00:06:32,160 --> 00:06:34,550
якщо згадати, що ми
динамічного розподілу пам'яті

120
00:06:34,550 --> 00:06:38,337
щоб побудувати ці списки зазвичай
ми хочемо, щоб звільнити всі, що пам'ять

121
00:06:38,337 --> 00:06:39,670
коли ми зробили з ним працювати.

122
00:06:39,670 --> 00:06:44,627
І тому ми повинні бути в змозі видалити
Весь зв'язаний список в одному невдачу махом.

123
00:06:44,627 --> 00:06:46,460
Так давайте пройдемо
деякі з цих операцій

124
00:06:46,460 --> 00:06:51,192
і як ми могли б візуалізувати їх,
говорити в псевдокоду коду спеціально.

125
00:06:51,192 --> 00:06:53,150
Тому ми хочемо, щоб створити
пов'язані список, так що, можливо, ми

126
00:06:53,150 --> 00:06:56,480
хочу, щоб визначити функцію
з цього прототипу.

127
00:06:56,480 --> 00:07:01,690
SLL вузол зірка, створювати, і я проходження
в один аргумент, деякі довільні дані

128
00:07:01,690 --> 00:07:05,530
тип знову, деякого довільного типу даних.

129
00:07:05,530 --> 00:07:10,482
Але я returning-- цю функцію слід
повернутися до мене покажчик, щоб одноразово

130
00:07:10,482 --> 00:07:11,190
Зв'язаний список вузол.

131
00:07:11,190 --> 00:07:14,050
Знову ж таки, ми намагаємося створити
зв'язаний список з повітря,

132
00:07:14,050 --> 00:07:17,900
так що мені потрібно покажчик на
що список, коли я зробив.

133
00:07:17,900 --> 00:07:19,420
>> Отже, які ж етапи тут?

134
00:07:19,420 --> 00:07:20,960
Ну, перше, що я
збираюся зробити, це динамічно

135
00:07:20,960 --> 00:07:22,550
виділити місце для нового вузла.

136
00:07:22,550 --> 00:07:26,689
Знову ж таки, ми створюємо його з тонкої
повітря, так що ми повинні Танос простору для нього.

137
00:07:26,689 --> 00:07:28,480
І, звичайно, відразу
після того як ми Танос,

138
00:07:28,480 --> 00:07:31,692
ми завжди перевіряємо, щоб переконатися, що наші
pointer-- ми не повернемося нуль.

139
00:07:31,692 --> 00:07:33,650
Тому що, якщо ми будемо намагатися
повагу нульовий покажчик,

140
00:07:33,650 --> 00:07:36,190
ми збираємося страждають
сегментації, і ми не хочемо цього.

141
00:07:36,190 --> 00:07:39,510
>> Потім ми хочемо, щоб заповнити в полі,
ми хочемо, щоб ініціалізувати значення поля

142
00:07:39,510 --> 00:07:41,690
і ініціалізувати наступне поле.

143
00:07:41,690 --> 00:07:45,450
А потім ми хочемо, метою яких в кінцевому підсумку, як
Прототип функції indicates-- ми хочемо

144
00:07:45,450 --> 00:07:49,940
повернути покажчик на SLL вузла.

145
00:07:49,940 --> 00:07:51,710
Так що зробити це виглядати візуально?

146
00:07:51,710 --> 00:07:55,230
Ну, по-перше, ми збираємося, щоб динамічно
виділити місце для нового вузла SLL,

147
00:07:55,230 --> 00:07:58,320
таким чином, ми malloc-- це
візуальне уявлення

148
00:07:58,320 --> 00:08:00,020
вузла ми тільки що створили.

149
00:08:00,020 --> 00:08:02,757
І ми перевіряємо, щоб переконатися,
це не null-- в цьому випадку,

150
00:08:02,757 --> 00:08:04,840
картина не матиме
показано, якщо це було порожнім,

151
00:08:04,840 --> 00:08:07,298
ми б запустити з пам'яті,
так що ми добре йти туди.

152
00:08:07,298 --> 00:08:10,200
Так що тепер ми до кроку С,
ініціалізувати поле вузли значення.

153
00:08:10,200 --> 00:08:12,280
Ну, на основі цієї функції
дзвоніть, я використовую тут,

154
00:08:12,280 --> 00:08:16,700
Схоже, я хочу, щоб пройти в 6,
Так що я 6 в полі значення.

155
00:08:16,700 --> 00:08:18,865
Тепер, ініціалізувати наступне поле.

156
00:08:18,865 --> 00:08:21,640
Ну, що я збираюся зробити там,
немає нічого поруч, праворуч,

157
00:08:21,640 --> 00:08:23,600
це єдине, що в списку.

158
00:08:23,600 --> 00:08:27,206
Так що в наступний момент в списку?

159
00:08:27,206 --> 00:08:29,660
>> Він не повинен вказувати на що-небудь, правильно.

160
00:08:29,660 --> 00:08:33,600
Там немає нічого іншого, там, так що
концепція ми знаємо, що це nothing--

161
00:08:33,600 --> 00:08:35,638
покажчики на нічого?

162
00:08:35,638 --> 00:08:37,929
Він повинен бути, може бути, ми хочемо
покласти порожній покажчик там,

163
00:08:37,929 --> 00:08:40,178
і я буду представляти нуль
покажчик, як тільки червоний прапорець,

164
00:08:40,178 --> 00:08:41,559
ми не можемо йти далі.

165
00:08:41,559 --> 00:08:44,430
Як ми побачимо трохи пізніше,
ми матимемо в кінцевому рахунку ланцюга

166
00:08:44,430 --> 00:08:46,330
стрілок підключення
ці вузли разом,

167
00:08:46,330 --> 00:08:48,480
але коли ви натиснете
червона коробка, це нуль,

168
00:08:48,480 --> 00:08:51,150
ми не можемо йти далі,
це кінець списку.

169
00:08:51,150 --> 00:08:53,960
>> І, нарешті, ми просто хочемо, щоб
повертає вказівник на цей вузол.

170
00:08:53,960 --> 00:08:56,160
Таким чином, ми будемо називати його новим,
і повернеться новий

171
00:08:56,160 --> 00:08:59,370
тому він може бути використаний в
всі функції його створив.

172
00:08:59,370 --> 00:09:03,100
Так що ми йдемо, Ми створили одноразово
Зв'язаний список вузол з повітря,

173
00:09:03,100 --> 00:09:05,920
і тепер у нас є список, ми можемо працювати з.

174
00:09:05,920 --> 00:09:08,260
>> Тепер, скажімо, ми вже
великого ланцюга,

175
00:09:08,260 --> 00:09:09,800
і ми хочемо, щоб знайти щось в ньому.

176
00:09:09,800 --> 00:09:12,716
І ми хочемо, функцію, яка збирається
повернутися істинним чи хибним, залежно

177
00:09:12,716 --> 00:09:15,840
від того, чи існує значення в цьому списку.

178
00:09:15,840 --> 00:09:18,160
Прототип функції, або
Заява для цієї функції,

179
00:09:18,160 --> 00:09:23,320
може виглядати this-- BOOL знайти, і
то ми хочемо, щоб пройти в двох аргументів.

180
00:09:23,320 --> 00:09:26,996
>> По-перше, це покажчик на
Перший елемент пов'язаного списку.

181
00:09:26,996 --> 00:09:29,620
Це насправді те, що ви будете
завжди хочуть, щоб відстежувати,

182
00:09:29,620 --> 00:09:33,110
і насправді може бути те, що
Ви навіть поставити в глобальній змінній.

183
00:09:33,110 --> 00:09:35,360
Після того, як ви створюєте список,
Ви завжди, завжди

184
00:09:35,360 --> 00:09:38,990
хочу, щоб відстежувати дуже
Перший елемент списку.

185
00:09:38,990 --> 00:09:43,690
Таким чином, ви можете звернутися до всі інші
елементи, просто по ланцюжку,

186
00:09:43,690 --> 00:09:47,300
без необхідності тримати покажчики
в цілості й схоронності кожного елемента.

187
00:09:47,300 --> 00:09:50,920
Вам потрібно тільки стежити за перший
одним, якщо вони все зв'язані разом.

188
00:09:50,920 --> 00:09:52,460
>> І тоді друга річ
ми передаємо знову

189
00:09:52,460 --> 00:09:54,376
довільно some--
незалежно від типу даних ми

190
00:09:54,376 --> 00:09:59,640
шукаю там всередині
ми сподіваємося, один з вузлів у списку.

191
00:09:59,640 --> 00:10:00,980
Отже, які кроки?

192
00:10:00,980 --> 00:10:04,250
Ну, перше, що ми робимо, це
ми створюємо покажчик поперечне

193
00:10:04,250 --> 00:10:06,015
вказуючи на голову списків.

194
00:10:06,015 --> 00:10:08,890
Ну, чому ми це робимо, ми вже
є вказівник на голову списків,

195
00:10:08,890 --> 00:10:10,974
чому б нам просто не рухатися, що один навколо?

196
00:10:10,974 --> 00:10:13,140
Ну, як я тільки що сказав ,,
це дійсно важливо для нас

197
00:10:13,140 --> 00:10:17,580
завжди стежити з
дуже перший елемент у списку.

198
00:10:17,580 --> 00:10:21,270
І так насправді краще
створити дублікат, що

199
00:10:21,270 --> 00:10:25,350
і використовувати не для переміщення, тому ми ніколи не
випадково відійти, або ми завжди

200
00:10:25,350 --> 00:10:30,430
є вказівник на якийсь момент, який
Право на перший елемент списку.

201
00:10:30,430 --> 00:10:33,290
Так що краще, щоб створити
Другий, який ми використовуємо, щоб рухатися.

202
00:10:33,290 --> 00:10:35,877
>> Тоді ми просто порівняти чи
поле значення в цьому вузлі

203
00:10:35,877 --> 00:10:38,960
це те, що ми шукаємо, і, якщо це
ні, ми просто переходимо до наступного вузла.

204
00:10:38,960 --> 00:10:41,040
І ми продовжуємо робити що
знову, і знову, і знову,

205
00:10:41,040 --> 00:10:44,811
поки ми не знайдемо ні
елемент, або ми потрапили

206
00:10:44,811 --> 00:10:47,310
null-- ми досягли кінця
списку, і це не було.

207
00:10:47,310 --> 00:10:50,540
Це повинно, ми сподіваємося, дзвонить дзвін
для вас, як тільки лінійний пошук,

208
00:10:50,540 --> 00:10:54,430
ми просто тиражування його в
одноразово пов'язаний список структура

209
00:10:54,430 --> 00:10:56,280
замість масиву, щоб зробити це.

210
00:10:56,280 --> 00:10:58,210
>> Так ось приклад
одноразово зв'язаний список.

211
00:10:58,210 --> 00:11:00,043
Цей складається з
п`ять вузлів, і у нас є

212
00:11:00,043 --> 00:11:04,330
покажчик на голову з
список, який називається список.

213
00:11:04,330 --> 00:11:07,385
Перше, що ми хочемо зробити, це
знову, створіть цей покажчик обходу.

214
00:11:07,385 --> 00:11:09,760
Таким чином, ми тепер маємо два покажчики
які вказують на те ж саме.

215
00:11:09,760 --> 00:11:15,025
>> Отже, зверніть увагу тут також, я не
повинні Танос будь-який простір для Trav.

216
00:11:15,025 --> 00:11:18,970
Я не кажу, Trav дорівнює Танос
те, що вузол вже існує,

217
00:11:18,970 --> 00:11:21,160
що простір в пам'яті вже існує.

218
00:11:21,160 --> 00:11:24,290
Таким чином, все, що я насправді роблю це
створюючи ще один покажчик на нього.

219
00:11:24,290 --> 00:11:28,210
Я не mallocing додатковий
простір, просто тепер два покажчики

220
00:11:28,210 --> 00:11:31,370
вказуючи на те ж саме.

221
00:11:31,370 --> 00:11:33,710
>> Так 2, що я шукаю?

222
00:11:33,710 --> 00:11:37,220
Ну, немає, так що замість я
буде рухатися до наступного.

223
00:11:37,220 --> 00:11:41,740
Так в основному, я б сказав,
Трав дорівнює TRAV поруч.

224
00:11:41,740 --> 00:11:43,630
Є 3, що я шукаю, немає.

225
00:11:43,630 --> 00:11:45,780
Так що я як і раніше йти
НЕ через, поки врешті-решт

226
00:11:45,780 --> 00:11:48,690
отримати до 6, який є те, що я шукаю
Для засноване на виклик функції

227
00:11:48,690 --> 00:11:51,600
У мене у верхній
там і так я зробив.

228
00:11:51,600 --> 00:11:54,150
>> Тепер, що якщо елемент я
шукаю не в списку,

229
00:11:54,150 --> 00:11:55,510
це ще буде працювати?

230
00:11:55,510 --> 00:11:57,120
Ну, зверніть увагу, що список
тут трохи відрізняється,

231
00:11:57,120 --> 00:11:59,410
і це ще одна річ, це
Важливо зі зв'язаними списками,

232
00:11:59,410 --> 00:12:01,780
Ви не повинні зберегти
їх у певному порядку.

233
00:12:01,780 --> 00:12:05,390
Ви можете, якщо хочете, але
Ви, можливо, вже помітили,

234
00:12:05,390 --> 00:12:09,310
що ми не відстежувати
те, що номер елемента ми в.

235
00:12:09,310 --> 00:12:13,150
>> І це свого роду одній угоді, що ми
є зі зв'язаним списком вірші масивів,

236
00:12:13,150 --> 00:12:15,300
це ми не маємо
довільного доступу більше.

237
00:12:15,300 --> 00:12:18,150
Ми не можемо просто сказати, я хочу
щоб перейти до 0-й елемент,

238
00:12:18,150 --> 00:12:21,410
або 6-й елемент мого масиву,
який я можу зробити в масиві.

239
00:12:21,410 --> 00:12:25,080
Я не можу сказати, що я хочу, щоб перейти до
0-я елемент або 6-й елемент,

240
00:12:25,080 --> 00:12:30,360
або 25-елемент мого пов'язаного списку,
немає індекс, пов'язаний з ними.

241
00:12:30,360 --> 00:12:33,660
І так дійсно не має значення
якщо ми збережемо наш список в порядку.

242
00:12:33,660 --> 00:12:36,080
Якщо ви хочете, щоб вас
, Звичайно, можна, але є

243
00:12:36,080 --> 00:12:38,567
немає причини, чому вони повинні
зберегти в будь-якому порядку.

244
00:12:38,567 --> 00:12:40,400
Отже, ще раз, давайте спробуємо
знайти 6 в цьому списку.

245
00:12:40,400 --> 00:12:43,200
Ну, ми починаємо на
початок, ми не знаходимо 6,

246
00:12:43,200 --> 00:12:47,690
а потім ми продовжимо, не знайшовши
6, поки ми в кінцевому підсумку не отримаєте тут.

247
00:12:47,690 --> 00:12:52,790
Так що зараз Trav вказує на вузол
містить 8, а шість не там.

248
00:12:52,790 --> 00:12:55,250
>> Так що наступний крок буде
щоб перейти до наступного вказівником,

249
00:12:55,250 --> 00:12:57,440
так би мовити, Trav дорівнює TRAV поруч.

250
00:12:57,440 --> 00:13:00,750
Ну, Trav поруч, зазначено
червоний коробка є, є недійсним.

251
00:13:00,750 --> 00:13:03,020
Так що нікуди
йти, і тому на даному етапі

252
00:13:03,020 --> 00:13:06,120
ми можемо зробити висновок, що ми досягли
кінець пов'язаного списку,

253
00:13:06,120 --> 00:13:07,190
і 6 не там.

254
00:13:07,190 --> 00:13:10,980
І це будуть повернуті
брехня в цьому випадку.

255
00:13:10,980 --> 00:13:14,540
>> ОК, як ми вставляємо новий
вузол у зв'язаному списку?

256
00:13:14,540 --> 00:13:17,310
Таким чином, ми змогли створити
зв'язаний список з нізвідки,

257
00:13:17,310 --> 00:13:19,370
але ми, ймовірно, хочете, щоб
побудувати ланцюжок, а не

258
00:13:19,370 --> 00:13:22,620
створити купу різних списків.

259
00:13:22,620 --> 00:13:25,700
Ми хочемо, щоб один список, що
має купу вузлів в ньому,

260
00:13:25,700 --> 00:13:28,040
а не купка списків з одного вузла.

261
00:13:28,040 --> 00:13:31,260
Таким чином, ми не можемо просто продовжувати використовувати Створити
функція, яку ми визначили раніше, в даний час ми

262
00:13:31,260 --> 00:13:33,860
вставити в
Список, який вже існує.

263
00:13:33,860 --> 00:13:36,499
>> Так даному випадку, ми збираємося
пройти в двох аргументів,

264
00:13:36,499 --> 00:13:39,290
покажчик на голову, що
пов'язані список, який ми хочемо додати к.

265
00:13:39,290 --> 00:13:40,910
Знову ж, це, чому це так
Важливо, що ми завжди

266
00:13:40,910 --> 00:13:43,400
відслідковувати, тому
це єдиний спосіб ми дійсно

267
00:13:43,400 --> 00:13:46,690
повинні звернутися до весь список
просто покажчик на перший елемент.

268
00:13:46,690 --> 00:13:49,360
Таким чином, ми хочемо передати в
покажчик на перший елемент цього,

269
00:13:49,360 --> 00:13:52,226
і все, що ми значення
хочете додати в список.

270
00:13:52,226 --> 00:13:54,600
І врешті-решт ця функція
буде повертати покажчик

271
00:13:54,600 --> 00:13:57,980
новому главі пов'язаного списку.

272
00:13:57,980 --> 00:13:59,700
>> Які етапи тут?

273
00:13:59,700 --> 00:14:02,249
Ну, як з створення,
ми повинні динамічно виділяти

274
00:14:02,249 --> 00:14:05,540
місця для нового вузла, і перевірте, щоб
що ми не вистачити пам'яті, знову ж таки,

275
00:14:05,540 --> 00:14:07,150
тому що ми використовуємо Танос.

276
00:14:07,150 --> 00:14:09,080
Потім ми хочемо, щоб заповнити
і вставте вузол,

277
00:14:09,080 --> 00:14:12,730
так поставити номер, все, що
Допустимі, у вузлі.

278
00:14:12,730 --> 00:14:17,310
Ми хочемо, щоб вставити вузол на
початок пов'язаного списку.

279
00:14:17,310 --> 00:14:19,619
>> Там це причина того, що я
хочу зробити це, і це

280
00:14:19,619 --> 00:14:21,910
можливо, варто приймати другу
щоб призупинити відео тут,

281
00:14:21,910 --> 00:14:25,860
і думаю, про те, чому я хотів би
вставити на початку пов'язаний

282
00:14:25,860 --> 00:14:26,589
Список.

283
00:14:26,589 --> 00:14:28,630
Знову ж таки, я згадував раніше
що він робить насправді не

284
00:14:28,630 --> 00:14:33,020
має значення, якщо ми збережемо його в будь
порядок, так що, можливо, що це ключ.

285
00:14:33,020 --> 00:14:36,040
І ви бачили, що сталося б, якби ми
хотів, метою яких або просто на секунду

286
00:14:36,040 --> 00:14:37,360
тому, коли ми йшли
через пошук Ви

287
00:14:37,360 --> 00:14:39,235
міг бачити те, що може
станеться, якщо ми намагалися

288
00:14:39,235 --> 00:14:41,330
вставити в кінець списку.

289
00:14:41,330 --> 00:14:44,750
Тому що ми не маємо
покажчик на кінець списку.

290
00:14:44,750 --> 00:14:47,490
>> Таким чином, причина того, що я хотів би
вставити на початку,

291
00:14:47,490 --> 00:14:49,380
тому, що я можу зробити це негайно.

292
00:14:49,380 --> 00:14:52,730
У мене є вказівник на початок, і
ми побачимо це у візуальний в секунду.

293
00:14:52,730 --> 00:14:55,605
Але якщо я хочу, щоб вставити в кінці кінців,
Я повинен почати з самого початку,

294
00:14:55,605 --> 00:14:58,760
пройти весь шлях до
кінець, а потім прикріпити його.

295
00:14:58,760 --> 00:15:01,420
Так що буде означати, що
вставки в кінець списку

296
00:15:01,420 --> 00:15:04,140
став би про п
Операція, повертаючись

297
00:15:04,140 --> 00:15:06,720
до обговорення
обчислювальна складність.

298
00:15:06,720 --> 00:15:10,140
Це було б стати про н роботи, де
також список отримав більше, і більше,

299
00:15:10,140 --> 00:15:13,310
і більше, це буде ставати все більш і
важче лавірувати то

300
00:15:13,310 --> 00:15:14,661
на кінці.

301
00:15:14,661 --> 00:15:17,410
Але це завжди дуже легко
лавірувати щось на на початку,

302
00:15:17,410 --> 00:15:19,060
Ви завжди на початку.

303
00:15:19,060 --> 00:15:21,620
>> І ми побачимо, візуальний це знову.

304
00:15:21,620 --> 00:15:24,100
І те, як тільки ми зробили, коли
ми вставили новий вузол,

305
00:15:24,100 --> 00:15:26,880
ми хочемо, щоб повернутися до нашої покажчик
новий глава пов'язаного списку, який

306
00:15:26,880 --> 00:15:29,213
так як ми вставки на
початок, насправді буде

307
00:15:29,213 --> 00:15:31,060
покажчик на вузол ми тільки що створили.

308
00:15:31,060 --> 00:15:33,280
Давайте візуалізувати це,
тому що я думаю, що це допоможе.

309
00:15:33,280 --> 00:15:36,661
>> Так ось наш список, вона складається з
чотири елементи, вузол, що містить 15,

310
00:15:36,661 --> 00:15:38,410
що вказує на вузол
містить 9, який

311
00:15:38,410 --> 00:15:41,370
вказує на вузлі, що містить 13,
що вказує на вузол, що містить

312
00:15:41,370 --> 00:15:44,840
10, який має нульове
Покажчик в своєму наступному покажчик

313
00:15:44,840 --> 00:15:47,010
так що це кінець списку.

314
00:15:47,010 --> 00:15:50,200
Тому ми хочемо, щоб вставити
Новий вузол зі значенням 12

315
00:15:50,200 --> 00:15:52,720
На початку цього
Список, що ми робимо?

316
00:15:52,720 --> 00:15:58,770
Ну, по-перше, ми Танос простір для
вузол, а потім покласти 12 там.

317
00:15:58,770 --> 00:16:02,211
>> Так що тепер ми досягли
точка прийняття рішення, вірно?

318
00:16:02,211 --> 00:16:03,960
У нас є кілька
покажчики, які ми могли б

319
00:16:03,960 --> 00:16:06,770
рухатися, що треба рухатися, ми в першу чергу?

320
00:16:06,770 --> 00:16:09,250
Чи повинні ми зробити 12 пункт
новий глава list--

321
00:16:09,250 --> 00:16:13,020
або, вибачте, ми повинні зробити 12
вказують на старий чолі списку?

322
00:16:13,020 --> 00:16:15,319
Або ми повинні сказати, що
Список в даний час починається в 12 років.

323
00:16:15,319 --> 00:16:17,110
Там це розходження
там, і ми будемо дивитися

324
00:16:17,110 --> 00:16:19,870
на те, що відбувається з обома в секунду.

325
00:16:19,870 --> 00:16:23,350
>> Але це призводить до
велика тема для бічній панелі,

326
00:16:23,350 --> 00:16:26,280
який що один з
каверзні речі зі зв'язаними списками

327
00:16:26,280 --> 00:16:30,980
є організація покажчики
в правильному порядку.

328
00:16:30,980 --> 00:16:34,520
Якщо ви перемістите речі з того,
Ви можете в кінцевому підсумку випадково

329
00:16:34,520 --> 00:16:36,050
сиротами інше списку.

330
00:16:36,050 --> 00:16:37,300
І ось тому приклад.

331
00:16:37,300 --> 00:16:40,540
Отже, давайте з ідеєю of--
Ну, ми тільки що створили 12.

332
00:16:40,540 --> 00:16:43,180
Ми знаємо, 12 буде
новий глава списку,

333
00:16:43,180 --> 00:16:47,660
і так, чому б нам просто не перейти
покажчик Список вказати там.

334
00:16:47,660 --> 00:16:49,070
>> ОК, так що це добре.

335
00:16:49,070 --> 00:16:51,560
Так що тепер, коли робить наступний пункт 12?

336
00:16:51,560 --> 00:16:54,580
Я маю на увазі, візуально ми бачимо
що буде вказувати на 15,

337
00:16:54,580 --> 00:16:57,250
як люди це дійсно очевидно для нас.

338
00:16:57,250 --> 00:17:00,300
Як комп'ютер знаєте?

339
00:17:00,300 --> 00:17:02,720
Ми не маємо нічого
вказуючи на 15 більше, вірно?

340
00:17:02,720 --> 00:17:05,869
>> Ми втратили можливість посилатися на 15.

341
00:17:05,869 --> 00:17:11,460
Ми не можемо сказати, новий стрілку поруч рівних
то, немає нічого.

342
00:17:11,460 --> 00:17:13,510
Насправді, ми осиротіли
інша частина списку

343
00:17:13,510 --> 00:17:16,465
тим самим, ми
випадково порушив ланцюг.

344
00:17:16,465 --> 00:17:18,089
І ми, звичайно, не хочете, щоб зробити це.

345
00:17:18,089 --> 00:17:20,000
>> Отже, давайте поверніться і спробуйте це знову.

346
00:17:20,000 --> 00:17:24,060
Можливо, те, що потрібно зробити,
це встановити наступний покажчик 12 в

347
00:17:24,060 --> 00:17:28,290
до старого чолі списку перших,
то ми можемо перемістити список більше.

348
00:17:28,290 --> 00:17:30,420
І справді, тобто
Правильний порядок, що ми

349
00:17:30,420 --> 00:17:32,836
необхідно дотримуватися, коли ми
роботи з однозв'язний список.

350
00:17:32,836 --> 00:17:36,460
Ми завжди хочемо, щоб підключити
Новий елемент у списку,

351
00:17:36,460 --> 00:17:41,010
перш, ніж ми прийняти таку
важливим кроком зміни

352
00:17:41,010 --> 00:17:43,360
де глава пов'язаного списку.

353
00:17:43,360 --> 00:17:46,740
Знову ж, це такий фундаментальний річ,
ми не хочемо, щоб втратити його.

354
00:17:46,740 --> 00:17:49,310
>> Тому ми хочемо, щоб переконатися, що
всі пов'язані разом,

355
00:17:49,310 --> 00:17:52,040
перш ніж ми перейдемо цей покажчик.

356
00:17:52,040 --> 00:17:55,300
І так це буде правильний порядок,
який є підключення 12 до списку,

357
00:17:55,300 --> 00:17:57,630
то кажуть, що список починається 12.

358
00:17:57,630 --> 00:18:00,860
Якби ми сказали список починається в 12 і
потім спробував підключити 12 в список,

359
00:18:00,860 --> 00:18:02,193
ми вже бачили, що відбувається.

360
00:18:02,193 --> 00:18:04,920
Ми втрачаємо список помилково.

361
00:18:04,920 --> 00:18:06,740
>> Отже, ще одна річ, щоб говорити про.

362
00:18:06,740 --> 00:18:09,750
Що робити, якщо ми хочемо, щоб позбутися від
весь пов'язаний список відразу?

363
00:18:09,750 --> 00:18:11,750
Знову ж таки, ми mallocing
Все це простір, і тому ми

364
00:18:11,750 --> 00:18:13,351
потрібно звільнити його, коли ми зробили.

365
00:18:13,351 --> 00:18:15,350
Так що тепер ми хочемо, щоб видалити
весь пов'язаний список.

366
00:18:15,350 --> 00:18:16,850
Ну, те, що ми хочемо зробити?

367
00:18:16,850 --> 00:18:20,460
>> Якщо ми досягли нульовий покажчик, ми
хочете, щоб зупинити, інакше, просто видаліть

368
00:18:20,460 --> 00:18:23,420
інша частина списку, а потім звільнити мене.

369
00:18:23,420 --> 00:18:28,890
Видалити іншу частину списку,
і потім звільнити поточний вузол.

370
00:18:28,890 --> 00:18:32,850
Що це схоже,
те, що техніка у нас говорили

371
00:18:32,850 --> 00:18:35,440
про раніше це звучить як?

372
00:18:35,440 --> 00:18:39,560
Видалити всі інші, то
повернутися і видалити мене.

373
00:18:39,560 --> 00:18:42,380
>> Це рекурсія, ми зробили
Проблема трохи менше,

374
00:18:42,380 --> 00:18:46,910
ми говоримо видалити всіх
ще, то ви можете видалити мене.

375
00:18:46,910 --> 00:18:50,940
А далі вниз по дорозі, що вузол
скажу, видалити всі інші.

376
00:18:50,940 --> 00:18:53,940
Але врешті-решт ми отримаємо в
Точка де список порожній,

377
00:18:53,940 --> 00:18:55,310
і це наша база випадок.

378
00:18:55,310 --> 00:18:57,010
>> Отже, давайте поглянемо на це,
і як це може працювати.

379
00:18:57,010 --> 00:18:59,759
Так ось наш список, це те ж саме
список ми просто говоримо,

380
00:18:59,759 --> 00:19:00,980
і є кроки.

381
00:19:00,980 --> 00:19:04,200
Там дуже багато тексту тут, але
сподіваюся, візуалізація допоможе.

382
00:19:04,200 --> 00:19:08,557
>> Таким чином, ми have-- і я також витягнув
до нашої кадрів стека ілюстрації

383
00:19:08,557 --> 00:19:10,890
з нашого відео на стеків викликів,
і, сподіваюся, все це

384
00:19:10,890 --> 00:19:13,260
разом покажу вам, що відбувається.

385
00:19:13,260 --> 00:19:14,510
Так от наш код псевдокод.

386
00:19:14,510 --> 00:19:17,830
Якщо ми досягнемо нуль
покажчик, зупинити, інакше,

387
00:19:17,830 --> 00:19:21,320
видалити іншу частину списку,
Потім звільнити поточний вузол.

388
00:19:21,320 --> 00:19:25,700
Так що зараз, list--
покажчик, що ми

389
00:19:25,700 --> 00:19:28,410
передаючи знищити очок до 12.

390
00:19:28,410 --> 00:19:33,340
12 не є нульовим покажчиком, тому ми
збирається видалити іншу частину списку.

391
00:19:33,340 --> 00:19:35,450
>> Що є видалення
Решта з нас бере участь?

392
00:19:35,450 --> 00:19:37,950
Ну, це означає, роблячи
подзвоніть, щоб знищити, кажучи

393
00:19:37,950 --> 00:19:42,060
що 15 це початок
Інша частина списку, який ми хочемо знищити.

394
00:19:42,060 --> 00:19:47,480
І тому виклик, щоб знищити
12 вид на утримання.

395
00:19:47,480 --> 00:19:52,690
Це заморожені там, чекаючи
подзвоніть, щоб знищити 15, щоб закінчити свою роботу.

396
00:19:52,690 --> 00:19:56,280
>> Ну, 15 не є нульовим покажчиком, і
так що це, щоб сказати, все в порядку,

397
00:19:56,280 --> 00:19:58,450
добре, видалити іншу частину списку.

398
00:19:58,450 --> 00:20:00,760
Інша частина списку починає
в 9, і тому ми просто

399
00:20:00,760 --> 00:20:04,514
чекати, поки ви не видалите все, що
матеріал, а потім повернутися і видалити мене.

400
00:20:04,514 --> 00:20:06,680
Ну 9 скаже, ну,
Я не порожній покажчик,

401
00:20:06,680 --> 00:20:09,020
так що видаліть інші список тут.

402
00:20:09,020 --> 00:20:11,805
І тому спробуйте і знищити 13.

403
00:20:11,805 --> 00:20:15,550
13 говорить, що я не порожній покажчик,
Те ж саме, він передає долар.

404
00:20:15,550 --> 00:20:17,930
10 не порожній покажчик, 10
містить порожній покажчик,

405
00:20:17,930 --> 00:20:20,200
але 10 не саме по собі є
NULL покажчик прямо зараз,

406
00:20:20,200 --> 00:20:22,470
і так вона проходить долар теж.

407
00:20:22,470 --> 00:20:25,560
>> А тепер список точок там, це
дійсно буде вказувати на some--

408
00:20:25,560 --> 00:20:28,710
якщо у мене було більше місця в зображенні,
це буде вказувати на деякої випадкової простору

409
00:20:28,710 --> 00:20:29,960
що ми не знаємо, що це таке.

410
00:20:29,960 --> 00:20:34,680
Це нульовий покажчик, хоча, список
буквально тепер встановлено, що це значення нульові.

411
00:20:34,680 --> 00:20:36,820
Це вказує прямо в цій червоній коробці.

412
00:20:36,820 --> 00:20:39,960
Ми досягли нульовий покажчик, тому
ми можемо зупинити, і ми зробили.

413
00:20:39,960 --> 00:20:46,230
>> І так, що фіолетовий кадру now-- на
Верх stack-- це активний кадр,

414
00:20:46,230 --> 00:20:47,017
але це робиться.

415
00:20:47,017 --> 00:20:48,600
Якщо ми досягли нульовий покажчик, зупинитися.

416
00:20:48,600 --> 00:20:51,290
Ми нічого не робимо, ми
не може звільнити нульовий покажчик,

417
00:20:51,290 --> 00:20:55,070
ми не Танос будь
простір, і тому ми зробили.

418
00:20:55,070 --> 00:20:57,590
Так, що функції кадру
руйнується, і ми

419
00:20:57,590 --> 00:21:00,930
resume-- ми забрати, де ми залишили
від з наступною вищої одного, який

420
00:21:00,930 --> 00:21:02,807
це темно-синя рамка тут.

421
00:21:02,807 --> 00:21:04,390
Таким чином, ми забрати там, де ми зупинилися.

422
00:21:04,390 --> 00:21:06,598
Ми видалили іншу частину
Список вже, так що тепер ми

423
00:21:06,598 --> 00:21:08,000
збирається звільнити поточні вузли.

424
00:21:08,000 --> 00:21:12,920
Так що тепер ми можемо звільнити цей вузол, і в даний час
ми досягли кінця функції.

425
00:21:12,920 --> 00:21:16,810
І так, що функція кадр буде знищений,
і ми забрати в блакитному один.

426
00:21:16,810 --> 00:21:20,650
>> Так що says-- я вже done--
видалення іншої частини списку, так

427
00:21:20,650 --> 00:21:23,140
звільнити поточний вузол.

428
00:21:23,140 --> 00:21:26,520
А тепер жовтий кадр
назад на вершині стека.

429
00:21:26,520 --> 00:21:29,655
І так, як ви бачите, ми тепер
руйнуючи список справа наліво.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Що сталося б, хоча,
Якби ми зробили щось не так?

432
00:21:37,280 --> 00:21:39,410
Так само, як коли ми намагалися
додати елемент.

433
00:21:39,410 --> 00:21:41,909
Якщо ми переплуталися, якщо ланцюг
ми не підключити покажчики

434
00:21:41,909 --> 00:21:44,690
в правильному порядку, якщо ми
просто звільнив перший елемент,

435
00:21:44,690 --> 00:21:47,420
якщо ми просто звільнили
голова списку, тепер ми

436
00:21:47,420 --> 00:21:49,642
немає ніякого способу послатися на
інша частина списку.

437
00:21:49,642 --> 00:21:51,350
І тому ми б
сиротами все,

438
00:21:51,350 --> 00:21:53,880
ми б мали те, що
називається витік пам'яті.

439
00:21:53,880 --> 00:21:56,800
Якщо ви пам'ятаєте з нашого відео
на динамічному розподілі пам'яті,

440
00:21:56,800 --> 00:21:58,650
це не дуже хороша річ.

441
00:21:58,650 --> 00:22:00,810
>> Отже, як я вже сказав,
кілька операцій,

442
00:22:00,810 --> 00:22:04,010
що ми повинні використовувати для роботи
з пов'язаний список ефективно.

443
00:22:04,010 --> 00:22:08,430
І ви, можливо, помітили, я опустив одну,
видалення одного елемента із зв'язаного

444
00:22:08,430 --> 00:22:09,064
Список.

445
00:22:09,064 --> 00:22:10,980
Тому я зробив це
це насправді свого роду

446
00:22:10,980 --> 00:22:14,360
складно думати про те, як видалити
один елемент з однократно

447
00:22:14,360 --> 00:22:15,600
Зв'язаний список.

448
00:22:15,600 --> 00:22:19,950
Ми повинні бути в змозі пропустити
щось в списку, який

449
00:22:19,950 --> 00:22:22,975
означає, що ми отримуємо в point-- ми
хочете видалити цей node--

450
00:22:22,975 --> 00:22:25,350
але для того, щоб зробити це так, ми
не втрачати інформацію,

451
00:22:25,350 --> 00:22:30,530
ми повинні пов'язувати це
вузол тут, тут.

452
00:22:30,530 --> 00:22:33,390
>> Так що я, ймовірно, зробив це неправильно
з візуальної точки зору.

453
00:22:33,390 --> 00:22:36,830
Таким чином, ми знаходимося на початку нашого
Список, ми протікає через,

454
00:22:36,830 --> 00:22:40,510
ми хочемо, щоб видалити цей вузол.

455
00:22:40,510 --> 00:22:43,440
Якщо ми просто видалити його,
ми порушили ланцюжок.

456
00:22:43,440 --> 00:22:45,950
Цей вузол прямо тут
відноситься до всього іншого,

457
00:22:45,950 --> 00:22:48,260
він містить ланцюг звідси на.

458
00:22:48,260 --> 00:22:51,190
>> Отже, що ми повинні зробити, насправді
після того як ми дістатися до цієї точки,

459
00:22:51,190 --> 00:22:56,670
що ми повинні зробити крок назад один, і
підключити цей вузол до цього вузла,

460
00:22:56,670 --> 00:22:58,590
так що ми можемо потім видалити
один у середині.

461
00:22:58,590 --> 00:23:02,120
Але поодинці пов'язані списків не
забезпечити нам шлях назад.

462
00:23:02,120 --> 00:23:05,160
Таким чином, ми повинні або зберегти
два покажчики, і перемістити їх

463
00:23:05,160 --> 00:23:09,527
зразок вимикання кроком, один за
одного, як ми йдемо, або дістатися до точки,

464
00:23:09,527 --> 00:23:11,110
а потім відправити другий покажчик кінця.

465
00:23:11,110 --> 00:23:13,150
І, як ви бачите, це
може отримати трохи брудно.

466
00:23:13,150 --> 00:23:15,360
На щастя, у нас є
ще один спосіб вирішити, що

467
00:23:15,360 --> 00:23:17,810
коли ми говоримо про подвійно зв'язані списки.

468
00:23:17,810 --> 00:23:20,720
>> Я Дуг Ллойд, це CS50.

469
00:23:20,720 --> 00:23:22,298