1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] У програмуванні, ми часто повинні представляти списки значень,

2
00:00:10,050 --> 00:00:12,840
такі як імена студентів в розділі

3
00:00:12,840 --> 00:00:15,100
або їх результати на останній вікторини.

4
00:00:15,100 --> 00:00:17,430
>> У мові C, заявив масиви можуть бути використані

5
00:00:17,430 --> 00:00:19,160
для зберігання списків.

6
00:00:19,160 --> 00:00:21,200
Легко перерахувати елементи списку

7
00:00:21,200 --> 00:00:23,390
зберігаються в масиві, і якщо вам потрібно отримати доступ

8
00:00:23,390 --> 00:00:25,050
або змінити го елементу списку

9
00:00:25,050 --> 00:00:27,570
для деякого довільного індексу I,

10
00:00:27,570 --> 00:00:29,910
що може бути зроблено в постійному часу,

11
00:00:29,910 --> 00:00:31,660
але масиви мають недоліки.

12
00:00:31,660 --> 00:00:33,850
>> Коли ми оголосимо їх, ми зобов'язані сказати,

13
00:00:33,850 --> 00:00:35,900
фронт, як вони великі,

14
00:00:35,900 --> 00:00:38,160
тобто, скільки елементів вони можуть зберігати

15
00:00:38,160 --> 00:00:40,780
і наскільки великий ці елементи, які визначаються їх типом.

16
00:00:40,780 --> 00:00:45,450
Наприклад, внутр обр (10)

17
00:00:45,450 --> 00:00:48,220
може зберігати 10 пунктів

18
00:00:48,220 --> 00:00:50,200
, Які є розмір Int.

19
00:00:50,200 --> 00:00:52,590
>> Ми не можемо змінити розмір масиву після декларації.

20
00:00:52,590 --> 00:00:55,290
Ми повинні створити новий масив, якщо ми хочемо зберегти кілька елементів.

21
00:00:55,290 --> 00:00:57,410
Причина цього обмеження в тому, що існує наша

22
00:00:57,410 --> 00:00:59,040
Програма зберігає весь масив

23
00:00:59,040 --> 00:01:02,310
як безперервний шматок пам'яті.

24
00:01:02,310 --> 00:01:04,500
Кажуть, що це буфер, де ми зберігали в нашому масиві.

25
00:01:04,500 --> 00:01:06,910
Там можуть бути й інші змінні

26
00:01:06,910 --> 00:01:08,310
розташований в безпосередній близькості до масиву

27
00:01:08,310 --> 00:01:10,060
в пам'яті, тому ми не можемо

28
00:01:10,060 --> 00:01:12,060
просто зробити масиву більше.

29
00:01:12,060 --> 00:01:15,700
>> Іноді ми хотіли б торгувати швидкий доступ до даних масиву швидкості

30
00:01:15,700 --> 00:01:17,650
для трохи більше гнучкості.

31
00:01:17,650 --> 00:01:20,380
Введіть зв'язаний список, інша основна структура даних

32
00:01:20,380 --> 00:01:22,360
Ви може бути не так добре знайомі.

33
00:01:22,360 --> 00:01:24,200
На високому рівні,

34
00:01:24,200 --> 00:01:26,840
Зв'язаний список зберігає дані в послідовність вузлів

35
00:01:26,840 --> 00:01:29,280
, Які пов'язані один з одним посиланнями,

36
00:01:29,280 --> 00:01:31,760
звідси і назва «зв'язаний список.

37
00:01:31,760 --> 00:01:33,840
Як ми побачимо, ця різниця в дизайні

38
00:01:33,840 --> 00:01:35,500
призводить до різних переваги і недоліки

39
00:01:35,500 --> 00:01:37,000
ніж масив.

40
00:01:37,000 --> 00:01:39,840
>> Ось код C з дуже простої зв'язаний список цілих чисел.

41
00:01:39,840 --> 00:01:42,190
Ви бачите, що ми представляємо кожному вузлу

42
00:01:42,190 --> 00:01:45,520
У списку, як структура, яка містить 2 речі,

43
00:01:45,520 --> 00:01:47,280
ціле для зберігання під назвою «Вал»

44
00:01:47,280 --> 00:01:50,460
і посилання на наступний вузол в списку

45
00:01:50,460 --> 00:01:52,990
, Які ми представляємо в якості покажчика називається "Далі".

46
00:01:54,120 --> 00:01:56,780
Таким чином, ми можемо відстежити весь список

47
00:01:56,780 --> 00:01:58,790
за допомогою всього одного покажчика на вузлі 1,

48
00:01:58,790 --> 00:02:01,270
і тоді ми зможемо виконати наступні покажчики

49
00:02:01,270 --> 00:02:03,130
на 2-й вузол,

50
00:02:03,130 --> 00:02:05,280
до 3-го вузлу,

51
00:02:05,280 --> 00:02:07,000
до 4-му вузлу,

52
00:02:07,000 --> 00:02:09,889
і так далі, поки ми не отримаємо до кінця списку.

53
00:02:10,520 --> 00:02:12,210
>> Ви могли б дивитися 1 Перевага цього є

54
00:02:12,210 --> 00:02:14,490
на статичну структуру масиву - з пов'язаного списку,

55
00:02:14,490 --> 00:02:16,450
нам не потрібно великий шматок пам'яті в цілому.

56
00:02:17,400 --> 00:02:20,530
Перший вузол списку могли б жити на цьому місці в пам'яті,

57
00:02:20,530 --> 00:02:23,160
і 2-го вузла може бути на всьому шляху сюди.

58
00:02:23,160 --> 00:02:25,780
Ми можемо дістатися до всіх вузлів, незалежно від того, де в пам'яті вони є,

59
00:02:25,780 --> 00:02:28,890
тому що, починаючи з першого вузла, наступного покажчика кожного вузла

60
00:02:28,890 --> 00:02:31,700
говорить нам точно, куди йти далі.

61
00:02:31,700 --> 00:02:33,670
>> Крім того, ми не повинні говорити фронт

62
00:02:33,670 --> 00:02:36,740
наскільки великий зв'язаний список буде так, як ми робимо з статичні масиви,

63
00:02:36,740 --> 00:02:39,060
так як ми можемо продовжувати додавати вузли в список

64
00:02:39,060 --> 00:02:42,600
тих пір, поки є вільне місце десь у пам'яті для нових вузлів.

65
00:02:42,600 --> 00:02:45,370
Тому, пов'язаних списків можна легко змінити розмір динамічно.

66
00:02:45,370 --> 00:02:47,950
Скажімо, пізніше в програмі, нам потрібно додати кілька вузлів

67
00:02:47,950 --> 00:02:49,350
в нашому списку.

68
00:02:49,350 --> 00:02:51,480
Для вставки нового вузла в нашому списку на льоту,

69
00:02:51,480 --> 00:02:53,740
все, що нам потрібно зробити, це виділити пам'ять для цього вузла,

70
00:02:53,740 --> 00:02:55,630
хлопнути в значенні даних,

71
00:02:55,630 --> 00:02:59,070
, А потім помістити його там, де ми хочемо шляхом коригування відповідних покажчиків.

72
00:02:59,070 --> 00:03:02,310
>> Наприклад, якщо ми хочемо розмістити вузол між

73
00:03:02,310 --> 00:03:04,020
2-й і 3-й вузли списку,

74
00:03:04,020 --> 00:03:06,800
 Ми не повинні були б рухатися 2-й або 3-й вузли на всіх.

75
00:03:06,800 --> 00:03:09,190
Сказати, що ми червоні вставки цих вузлів.

76
00:03:09,190 --> 00:03:12,890
Все, що ми повинні були б зробити, це встановити наступний покажчик нового вузла

77
00:03:12,890 --> 00:03:14,870
вказувати на 3-му вузлі

78
00:03:14,870 --> 00:03:18,580
, А потім перемонтувати наступний покажчик 2-го вузла

79
00:03:18,580 --> 00:03:20,980
вказують на нашому новому вузлі.

80
00:03:22,340 --> 00:03:24,370
Таким чином, ми можемо змінити розмір наших списків на льоту

81
00:03:24,370 --> 00:03:26,090
З нашого комп'ютера не покладатися на індексацію,

82
00:03:26,090 --> 00:03:28,990
а на зв'язку за допомогою покажчиків для їх зберігання.

83
00:03:29,120 --> 00:03:31,600
>> Тим не менш, недолік зв'язані списки

84
00:03:31,600 --> 00:03:33,370
є те, що, на відміну від статичного масиву,

85
00:03:33,370 --> 00:03:36,690
Комп'ютер не може просто стрибнути в середину списку.

86
00:03:38,040 --> 00:03:40,780
Так як комп'ютер повинен відвідати кожен вузол у зв'язаному списку

87
00:03:40,780 --> 00:03:42,330
щоб дістатися до наступного,

88
00:03:42,330 --> 00:03:44,770
це займе більше часу, щоб знайти конкретний вузол

89
00:03:44,770 --> 00:03:46,400
ніж це було б в масиві.

90
00:03:46,400 --> 00:03:48,660
Щоб пройти весь список займає час, пропорційне

91
00:03:48,660 --> 00:03:50,580
до довжини списку,

92
00:03:50,580 --> 00:03:54,630
або O (N) в асимптотичних позначень.

93
00:03:54,630 --> 00:03:56,510
У середньому, досягнувши будь-якого вузла

94
00:03:56,510 --> 00:03:58,800
також займає час, пропорційне до н.

95
00:03:58,800 --> 00:04:00,700
>> Тепер, давайте насправді написати код

96
00:04:00,700 --> 00:04:02,000
, Який працює зі зв'язаними списками.

97
00:04:02,000 --> 00:04:04,220
Скажімо, ми хочемо зв'язаний список цілих чисел.

98
00:04:04,220 --> 00:04:06,140
Ми можемо уявити вузол в наш список ще раз

99
00:04:06,140 --> 00:04:08,340
як структура з 2 полями,

100
00:04:08,340 --> 00:04:10,750
Ціле число називається "Вал"

101
00:04:10,750 --> 00:04:13,490
і наступний покажчик на наступний вузол списку.

102
00:04:13,490 --> 00:04:15,660
Ну, здається досить простим.

103
00:04:15,660 --> 00:04:17,220
>> Скажімо, ми хочемо написати функцію,

104
00:04:17,220 --> 00:04:19,329
який проходить по списку і виводить

105
00:04:19,329 --> 00:04:22,150
Значення, яке зберігається в останній вузол списку.

106
00:04:22,150 --> 00:04:24,850
Ну, значить, ми повинні будемо пройти всі вузли в списку

107
00:04:24,850 --> 00:04:27,310
щоб знайти останнього, але так як ми не додаємо

108
00:04:27,310 --> 00:04:29,250
або видаляючи, ми не хочемо змінити

109
00:04:29,250 --> 00:04:32,210
Внутрішня структура наступного покажчика в списку.

110
00:04:32,210 --> 00:04:34,790
>> Отже, нам знадобиться покажчик спеціально для обходу

111
00:04:34,790 --> 00:04:36,940
який ми називаємо «гусеничні».

112
00:04:36,940 --> 00:04:38,870
Вона буде сканувати через всі елементи списку

113
00:04:38,870 --> 00:04:41,190
, Виконавши наступний ланцюжок покажчиків.

114
00:04:41,190 --> 00:04:43,750
Все, що ми зберегли це покажчик на вузол 1,

115
00:04:43,750 --> 00:04:45,730
або «голови» списку.

116
00:04:45,730 --> 00:04:47,370
Керівник вказує на перший вузол.

117
00:04:47,370 --> 00:04:49,120
Це типу покажчик-на-вузла.

118
00:04:49,120 --> 00:04:51,280
>> Щоб отримати фактичний перший вузол у списку,

119
00:04:51,280 --> 00:04:53,250
ми повинні разименованія цього покажчика,

120
00:04:53,250 --> 00:04:55,100
але перш ніж ми зможемо разименовать це, нам потрібно перевірити

121
00:04:55,100 --> 00:04:57,180
якщо покажчик є нульовим першим.

122
00:04:57,180 --> 00:04:59,190
Якщо він порожній, список порожній,

123
00:04:59,190 --> 00:05:01,320
і ми повинні надрукувати повідомлення, що, оскільки список порожній,

124
00:05:01,320 --> 00:05:03,250
немає останнього вузла.

125
00:05:03,250 --> 00:05:05,190
Але, скажімо, в список не порожній.

126
00:05:05,190 --> 00:05:08,340
Якщо це не так, то ми повинні повзти через весь список

127
00:05:08,340 --> 00:05:10,440
поки ми не отримаємо на останній вузол списку,

128
00:05:10,440 --> 00:05:13,030
і як ми можемо сказати, якщо ми дивимося на останній вузол у списку?

129
00:05:13,670 --> 00:05:16,660
>> Ну, якщо наступний покажчик вузла є нульовим,

130
00:05:16,660 --> 00:05:18,320
Ми знаємо, що ми знаходимося в кінці

131
00:05:18,320 --> 00:05:22,390
З останнім наступний покажчик матиме наступний вузол в списку, щоб вказувати.

132
00:05:22,390 --> 00:05:26,590
Це гарна практика, щоб завжди мати наступний покажчик останнього вузла ініціалізований до нуля

133
00:05:26,590 --> 00:05:30,800
мати стандартизований майно, яке попереджає нас, коли ми досягли кінця списку.

134
00:05:30,800 --> 00:05:33,510
>> Таким чином, якщо гусеничних → наступний порожній,

135
00:05:34,120 --> 00:05:38,270
пам'ятайте, що стрілка синтаксис ярлик для разименованія

136
00:05:38,270 --> 00:05:40,010
покажчик на структуру, то доступ

137
00:05:40,010 --> 00:05:42,510
свого наступного поля еквівалентні ніяково:

138
00:05:42,510 --> 00:05:48,750
(* Гусеничні). Наступний.

139
00:05:49,820 --> 00:05:51,260
Як тільки ми виявили, що останній вузол,

140
00:05:51,260 --> 00:05:53,830
ми хочемо надрукувати гусеничних → Вал,

141
00:05:53,830 --> 00:05:55,000
значення в поточному вузлі

142
00:05:55,000 --> 00:05:57,130
який ми знаємо, це останній.

143
00:05:57,130 --> 00:05:59,740
В іншому випадку, якщо ми ще не в останню вузла в списку,

144
00:05:59,740 --> 00:06:02,340
ми повинні перейти до наступного вузла в списку

145
00:06:02,340 --> 00:06:04,750
і переконайтеся, що це остання.

146
00:06:04,750 --> 00:06:07,010
Щоб зробити це, ми просто встановити наш сканер покажчик

147
00:06:07,010 --> 00:06:09,840
, Щоб вказати на наступне значення поточного вузла,

148
00:06:09,840 --> 00:06:11,680
, Тобто на наступний вузол в списку.

149
00:06:11,680 --> 00:06:13,030
Це робиться шляхом установки

150
00:06:13,030 --> 00:06:15,280
Гусеничний = гусеничних → Далі.

151
00:06:16,050 --> 00:06:18,960
Тоді ми повторюємо цей процес, з петлею наприклад,

152
00:06:18,960 --> 00:06:20,960
поки ми не знайдемо останній вузол.

153
00:06:20,960 --> 00:06:23,150
Так, наприклад, якщо гусеничних вказував на голову,

154
00:06:24,050 --> 00:06:27,710
Покладемо гусеничних вказують на гусеничному → наступному,

155
00:06:27,710 --> 00:06:30,960
який так само, як у наступному полі 1-го вузла.

156
00:06:30,960 --> 00:06:33,620
Отже, тепер наш сканер вказує на другому вузлі,

157
00:06:33,620 --> 00:06:35,480
і, знову ж таки, ми повторюємо це з петлею,

158
00:06:37,220 --> 00:06:40,610
поки ми не знайшли останнього вузла, тобто,

159
00:06:40,610 --> 00:06:43,640
де наступний покажчик вузла вказує на нуль.

160
00:06:43,640 --> 00:06:45,070
І у нас це є,

161
00:06:45,070 --> 00:06:47,620
ми знайшли останнього вузла в списку, а щоб надрукувати його значення,

162
00:06:47,620 --> 00:06:50,800
ми просто використовуємо гусеничних → знач.

163
00:06:50,800 --> 00:06:53,130
>> Переміщення не так вже погано, але те, що про установку?

164
00:06:53,130 --> 00:06:56,290
Припустимо, ми хочемо, щоб вставити число в 4-й позиції

165
00:06:56,290 --> 00:06:58,040
У цілого списку.

166
00:06:58,040 --> 00:07:01,280
Тобто між поточним 3 і 4 вузлів.

167
00:07:01,280 --> 00:07:03,760
Знову ж таки, у нас є для перегляду списку тільки

168
00:07:03,760 --> 00:07:06,520
дістатися до 3-го елемента, один ми вставка після.

169
00:07:06,520 --> 00:07:09,300
Таким чином, ми створюємо гусеничних покажчик знову пройти списку,

170
00:07:09,300 --> 00:07:11,400
перевірити, якщо наша голова покажчик є нульовим,

171
00:07:11,400 --> 00:07:14,810
і якщо це не так, вказати наш сканер покажчик на головному вузлі.

172
00:07:16,880 --> 00:07:18,060
Отже, ми на 1-м елементом.

173
00:07:18,060 --> 00:07:21,020
Ми повинні йти вперед ще 2 елементи перш ніж ми зможемо вставити,

174
00:07:21,020 --> 00:07:23,390
тому ми можемо використовувати для циклу

175
00:07:23,390 --> 00:07:26,430
Int я = 1; I <3, Я + +

176
00:07:26,430 --> 00:07:28,590
і в кожній ітерації циклу,

177
00:07:28,590 --> 00:07:31,540
просувати наш сканер покажчик вперед на 1 вузол

178
00:07:31,540 --> 00:07:34,570
, Перевіряючи, якщо наступне поле поточного вузла є нульовим,

179
00:07:34,570 --> 00:07:37,550
і якщо це не так, перемістіть наш сканер покажчик на наступний вузол

180
00:07:37,550 --> 00:07:41,810
, Встановивши його рівним наступний покажчик поточного вузла.

181
00:07:41,810 --> 00:07:45,210
Таким чином, оскільки наш цикл говорить, щоб зробити це

182
00:07:45,210 --> 00:07:47,550
в два рази,

183
00:07:49,610 --> 00:07:51,190
ми досягли 3-го вузла,

184
00:07:51,190 --> 00:07:53,110
і як тільки наш сканер покажчик досяг вузол після

185
00:07:53,110 --> 00:07:55,270
який ми хочемо вставити наш новий ціле число,

186
00:07:55,270 --> 00:07:57,050
Як ми насправді вставка?

187
00:07:57,050 --> 00:07:59,440
>> Ну, наше нове ціле повинен бути вставлений в список

188
00:07:59,440 --> 00:08:01,250
як частину своєї власної структури вузла,

189
00:08:01,250 --> 00:08:03,140
так як це дійсно послідовність вузлів.

190
00:08:03,140 --> 00:08:05,690
Отже, давайте зробимо новий покажчик на вузол

191
00:08:05,690 --> 00:08:08,910
називається "new_node"

192
00:08:08,910 --> 00:08:11,800
і встановити його, щоб вказати на пам'ять, що ми зараз виділити

193
00:08:11,800 --> 00:08:14,270
в купі для самого вузла,

194
00:08:14,270 --> 00:08:16,000
пам'яті і скільки нам потрібно виділити?

195
00:08:16,000 --> 00:08:18,250
Ну, розмір вузла,

196
00:08:20,450 --> 00:08:23,410
і ми хочемо встановити його вал поле число, яке ми хочемо вставити.

197
00:08:23,410 --> 00:08:25,590
Скажімо, 6.

198
00:08:25,590 --> 00:08:27,710
Тепер вузол містить наш ціле значення.

199
00:08:27,710 --> 00:08:30,650
Це також гарна практика для ініціалізації наступного поля нового вузла

200
00:08:30,650 --> 00:08:33,690
вказують на нуль,

201
00:08:33,690 --> 00:08:35,080
Але що тепер?

202
00:08:35,080 --> 00:08:37,179
>> Ми повинні змінити внутрішню структуру списку

203
00:08:37,179 --> 00:08:40,409
і на наступний покажчиків, що містяться в існуючих списку

204
00:08:40,409 --> 00:08:42,950
3 і 4 вузлів.

205
00:08:42,950 --> 00:08:46,560
З наступного покажчика визначають порядок списку,

206
00:08:46,560 --> 00:08:48,650
і так як ми вставки нашого нового вузла

207
00:08:48,650 --> 00:08:50,510
прямо в середині списку,

208
00:08:50,510 --> 00:08:52,010
вона може бути трохи складніше.

209
00:08:52,010 --> 00:08:54,250
Це тому, що пам'ятаю, наш комп'ютер

210
00:08:54,250 --> 00:08:56,250
тільки знає розташування вузлів в списку

211
00:08:56,250 --> 00:09:00,400
через чергового покажчики зберігаються в попередніх вузлах.

212
00:09:00,400 --> 00:09:03,940
Таким чином, якщо ми коли-небудь втратив будь-яку з цих місць,

213
00:09:03,940 --> 00:09:06,860
кажуть, змінивши одну з наступних покажчиків в нашому списку

214
00:09:06,860 --> 00:09:09,880
Наприклад, сказати, що ми змінилися

215
00:09:09,880 --> 00:09:12,920
Наступні 3-го вузла поля

216
00:09:12,920 --> 00:09:15,610
вказати на деякі вузла сюди.

217
00:09:15,610 --> 00:09:17,920
Ми були б не пощастило, тому що ми не хочемо

218
00:09:17,920 --> 00:09:20,940
є ідеї, де знайти інші частини списку,

219
00:09:20,940 --> 00:09:23,070
і це, очевидно, дуже погано.

220
00:09:23,070 --> 00:09:25,080
Таким чином, ми повинні бути дуже обережні, про порядок

221
00:09:25,080 --> 00:09:28,360
, В якій ми маніпулювати нашим наступним покажчиків під час установки.

222
00:09:28,360 --> 00:09:30,540
>> Таким чином, щоб спростити це, давайте скажемо, що

223
00:09:30,540 --> 00:09:32,220
наші перші 4 вузлів

224
00:09:32,220 --> 00:09:36,200
називаються A, B, C, і D, зі стрілками, що представляє ланцюжок покажчиків

225
00:09:36,200 --> 00:09:38,070
, Які з'єднують вузли.

226
00:09:38,070 --> 00:09:40,050
Отже, нам потрібно вставити наш новий вузол

227
00:09:40,050 --> 00:09:42,070
між вузлами C і D.

228
00:09:42,070 --> 00:09:45,060
Дуже важливо робити це в правильному порядку, і я покажу вам, чому.

229
00:09:45,060 --> 00:09:47,500
>> Давайте подивимося на неправильний спосіб зробити це першим.

230
00:09:47,500 --> 00:09:49,490
Гей, ми знаємо, що новий вузол повинен прийти відразу після C,

231
00:09:49,490 --> 00:09:51,910
так що давайте встановити наступний покажчик Сі

232
00:09:51,910 --> 00:09:54,700
вказують на new_node.

233
00:09:56,530 --> 00:09:59,180
Ладно, здається, все в порядку, ми просто повинні закінчити зараз,

234
00:09:59,180 --> 00:10:01,580
робить наступний пункт покажчик на новий вузол в D,

235
00:10:01,580 --> 00:10:03,250
Але почекайте, як ми можемо це зробити?

236
00:10:03,250 --> 00:10:05,170
Єдине, що може сказати нам, де D був,

237
00:10:05,170 --> 00:10:07,630
був наступний покажчик Раніше зберігається в C,

238
00:10:07,630 --> 00:10:09,870
але ми просто переписали, що покажчик

239
00:10:09,870 --> 00:10:11,170
щоб вона вказувала на новий вузол,

240
00:10:11,170 --> 00:10:14,230
таким чином, ми більше не мають поняття, де D знаходиться в пам'яті,

241
00:10:14,230 --> 00:10:17,020
і ми втратили іншу частину списку.

242
00:10:17,020 --> 00:10:19,000
Не годиться.

243
00:10:19,000 --> 00:10:21,090
>> Отже, як ми робимо це правильно?

244
00:10:22,360 --> 00:10:25,090
По-перше, вказати наступний покажчик на новий вузол за адресою D.

245
00:10:26,170 --> 00:10:28,990
Тепер, як новий вузол і C в наступному покажчики

246
00:10:28,990 --> 00:10:30,660
вказують на той же вузол, D,

247
00:10:30,660 --> 00:10:32,290
але це нормально.

248
00:10:32,290 --> 00:10:35,680
Тепер ми можемо відзначити наступний покажчик C на новому вузлі.

249
00:10:37,450 --> 00:10:39,670
Таким чином, ми зробили це без втрати даних.

250
00:10:39,670 --> 00:10:42,280
У коді З поточного вузла

251
00:10:42,280 --> 00:10:45,540
що обхід покажчик гусеничних вказує на,

252
00:10:45,540 --> 00:10:50,400
і D представляє вузол, на який вказує наступне поле поточного вузла,

253
00:10:50,400 --> 00:10:52,600
або гусеничному → Далі.

254
00:10:52,600 --> 00:10:55,460
Таким чином, ми спочатку встановити наступний покажчик нового вузла

255
00:10:55,460 --> 00:10:57,370
вказують на гусеничному → наступному,

256
00:10:57,370 --> 00:11:00,880
Точно так само ми сказали, наступний покажчик повинен new_node

257
00:11:00,880 --> 00:11:02,780
вказують на D на малюнку.

258
00:11:02,780 --> 00:11:04,540
Тоді, ми можемо встановити наступний покажчик поточного вузла

259
00:11:04,540 --> 00:11:06,330
на нашому новому вузлі,

260
00:11:06,330 --> 00:11:10,980
так само, як ми повинні були чекати до точки С, щоб new_node на кресленні.

261
00:11:10,980 --> 00:11:12,250
Тепер все в порядку, і ми не втратили

262
00:11:12,250 --> 00:11:14,490
відстеження будь-яких даних, і ми змогли просто

263
00:11:14,490 --> 00:11:16,200
дотримуватися нашого нового вузла в середині списку

264
00:11:16,200 --> 00:11:19,330
без перебудови все це або навіть переміщення будь-яких елементів

265
00:11:19,330 --> 00:11:22,490
то, як ми повинні були б з фіксованою довжиною масиву.

266
00:11:22,490 --> 00:11:26,020
>> Отже, зв'язані списки є основними, але важливо, динамічні структури даних

267
00:11:26,020 --> 00:11:29,080
які мають як переваги, так і недоліки

268
00:11:29,080 --> 00:11:31,260
в порівнянні з масивів та інших структур даних,

269
00:11:31,260 --> 00:11:33,350
і, як це часто буває в комп'ютерній науці,

270
00:11:33,350 --> 00:11:35,640
важливо знати, коли використовувати кожен інструмент,

271
00:11:35,640 --> 00:11:37,960
так що ви можете вибрати правильний інструмент для правильної роботи.

272
00:11:37,960 --> 00:11:40,060
>> Для отримання додаткової практикою, спробувати написати функцій

273
00:11:40,060 --> 00:11:42,080
видалити вузли із зв'язаного списку -

274
00:11:42,080 --> 00:11:44,050
не забувайте бути обережними про порядок, в якому ви переставити

275
00:11:44,050 --> 00:11:47,430
Ваш наступний покажчик, щоб не втратити шматок вашого списку -

276
00:11:47,430 --> 00:11:50,200
або функція для підрахунку вузли у зв'язаному списку,

277
00:11:50,200 --> 00:11:53,280
або весело один, щоб змінити порядок всі вузли у зв'язаному списку.

278
00:11:53,280 --> 00:11:56,090
>> Мене звуть Джексон Steinkamp, ​​це CS50.