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, это могло бы
быть 1000, это могло бы

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