1
00:00:00,000 --> 00:00:03,381
>> [За възпроизвеждане на музика]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
Дъг LLOYD: Добре.

4
00:00:05,520 --> 00:00:07,860
Така че, ако току-що завърши, че
видео по единично-свързани списъци съжалявам

5
00:00:07,860 --> 00:00:09,568
Аз сте спрели на
малко на Катерачът.

6
00:00:09,568 --> 00:00:12,790
Но се радвам, че сте тук, за да продължи
историята на двойно по-свързани списъци.

7
00:00:12,790 --> 00:00:15,250
>> Така че, ако си спомняте от
че видео, ние говорихме

8
00:00:15,250 --> 00:00:18,500
за това как поединично-свързана
списъци посещават нашата способност

9
00:00:18,500 --> 00:00:22,090
да се справят с информация
където броят на елементите

10
00:00:22,090 --> 00:00:24,442
или броя на елементите в
списък може да расте или се свива.

11
00:00:24,442 --> 00:00:26,400
Сега можем да се справим с
нещо подобно, където

12
00:00:26,400 --> 00:00:28,310
не бихме могли да се справим с него с масиви.

13
00:00:28,310 --> 00:00:30,560
>> Но те не страдат от едно
критична ограничение,

14
00:00:30,560 --> 00:00:33,790
че е с единично свързан
списък, ние можем само да се движат

15
00:00:33,790 --> 00:00:36,200
в една посока през списъка.

16
00:00:36,200 --> 00:00:39,010
И единствената реална ситуация
когато това може да стане проблем

17
00:00:39,010 --> 00:00:41,250
беше, когато се опитвахме да
изтриете отделен елемент.

18
00:00:41,250 --> 00:00:46,000
А ние дори не обсъждат как да го направя
в поединично-свързан списък в Псевдокод а.

19
00:00:46,000 --> 00:00:48,797
Това със сигурност е постижимо, но
тя може да бъде малко на една караница.

20
00:00:48,797 --> 00:00:50,630
Така че, ако откриете себе си
при положение,

21
00:00:50,630 --> 00:00:53,175
която се опитвате да изтриете
единични елементи от списъка

22
00:00:53,175 --> 00:00:55,430
или това ще се изисква
че ще бъдат изтриване

23
00:00:55,430 --> 00:00:57,970
единични елементи от
в списъка, може да искате

24
00:00:57,970 --> 00:01:02,090
да обмисли възможността за използване на двойно по-свързано
изброят вместо на единично-свързан списък.

25
00:01:02,090 --> 00:01:06,320
Заради двойно по-свързани списъци ви позволяват
да се движи напред, назад и отзад

26
00:01:06,320 --> 00:01:09,340
в списъка вместо
само напред през list--

27
00:01:09,340 --> 00:01:13,950
просто чрез добавяне на един допълнителен елемент
до нашата дефиниция структура

28
00:01:13,950 --> 00:01:16,690
за двойно по-свързан списък възел.

29
00:01:16,690 --> 00:01:19,770
>> Отново, ако не започваш да се
изтриваме единични елементи

30
00:01:19,770 --> 00:01:24,810
от list-- защото сме добавяне
допълнително поле за нашата структура

31
00:01:24,810 --> 00:01:28,340
определение, самите възли
за двойно по-свързани списъци

32
00:01:28,340 --> 00:01:29,550
ще бъде по-голям.

33
00:01:29,550 --> 00:01:31,600
Те ще вземат
до повече байта памет.

34
00:01:31,600 --> 00:01:34,160
И така, ако това не е нещо,
започваш да трябва да направите,

35
00:01:34,160 --> 00:01:36,300
може да решите, че е
не си струва търговията на разстояние

36
00:01:36,300 --> 00:01:39,360
да се наложи да прекарат допълнителни
байта памет, изисквани

37
00:01:39,360 --> 00:01:43,940
за двойно по-свързан списък, ако не сте
Ще бъдат изтриване единични елементи.

38
00:01:43,940 --> 00:01:46,760
Но те са също така хладно
за други неща също.

39
00:01:46,760 --> 00:01:51,260
>> Така че, както казах, ние просто трябва да добавите
едно единствено поле за нашата структура

40
00:01:51,260 --> 00:01:55,360
definition-- това понятие
Предишна на показалеца.

41
00:01:55,360 --> 00:01:58,620
Така че с единично-свързан списък, ние
имат стойност и Next показалеца,

42
00:01:58,620 --> 00:02:02,850
така че двойно по-свързан списък просто има
начин да се движи назад, както добре.

43
00:02:02,850 --> 00:02:04,960
>> Сега в поединично-свързана
списък на видео, ние говорихме

44
00:02:04,960 --> 00:02:07,210
за това са пет от
Основните неща, които трябва да бъдат

45
00:02:07,210 --> 00:02:09,449
в състояние да направи, за да работи с свързани списъци.

46
00:02:09,449 --> 00:02:12,880
И за повечето от тях, фактът,
че това е двойно по-свързан списък

47
00:02:12,880 --> 00:02:14,130
не е наистина голям скок.

48
00:02:14,130 --> 00:02:17,936
Все още можем да се търси чрез само с
се движат напред от началото до края.

49
00:02:17,936 --> 00:02:20,810
Все още можем да се създаде един възел от
нищото, почти по същия начин.

50
00:02:20,810 --> 00:02:23,591
Ние можем да изтриете списъци доста
по същия начин, също.

51
00:02:23,591 --> 00:02:25,340
Единствените неща, които
са едва доловимо различен,

52
00:02:25,340 --> 00:02:28,970
Наистина, поставяте
нови възли в списъка,

53
00:02:28,970 --> 00:02:33,722
и ние най-накрая ще говорим за изтриване
един елемент от списъка, както добре.

54
00:02:33,722 --> 00:02:35,430
Отново доста много
другите трима, ние сме

55
00:02:35,430 --> 00:02:37,888
Няма да говорим за тях
точно сега, защото те са просто

56
00:02:37,888 --> 00:02:43,920
много малки ощипвам на идеите, обсъдени
в поединично-свързан списък видеото.

57
00:02:43,920 --> 00:02:46,292
>> Така че нека да вмъкнете нов възел
в двойно по-свързан списък.

58
00:02:46,292 --> 00:02:48,750
Ние говорихме за това това за
поединично-свързани списъци, както и,

59
00:02:48,750 --> 00:02:52,020
но има няколко допълнителни
хваща с двойно по-свързани списъци.

60
00:02:52,020 --> 00:02:55,280
Бяха [? минаваща?] в главата на
избройте тук и някои произволна стойност,

61
00:02:55,280 --> 00:02:58,600
и ние искаме да получите най-новата глава
на списъка от тази функция.

62
00:02:58,600 --> 00:03:01,414
Ето защо тя се връща на dllnode звезда.

63
00:03:01,414 --> 00:03:02,330
Така че какви са стъпките?

64
00:03:02,330 --> 00:03:04,496
Те са, отново, много подобен
на единично свързан списъци

65
00:03:04,496 --> 00:03:05,670
с едно допълнително добавяне.

66
00:03:05,670 --> 00:03:08,900
Искаме да заделя пространство за нов
възел и проверка, за да се уверите, че е валиден.

67
00:03:08,900 --> 00:03:11,510
Искаме да запълни този възел нагоре
всякаква информация, която ние

68
00:03:11,510 --> 00:03:12,564
Искам да сложа в него.

69
00:03:12,564 --> 00:03:15,480
Последното нещо, което ние трябва да do-- на
допълнително нещо, което трябва да направим, rather--

70
00:03:15,480 --> 00:03:19,435
е да се определи Предишна показалеца
на стария начело на списъка.

71
00:03:19,435 --> 00:03:21,310
Не забравяйте, че поради
двойно-свързани списъци,

72
00:03:21,310 --> 00:03:23,110
можем да продължим напред
и backwards-- които

73
00:03:23,110 --> 00:03:27,080
означава, че всеки възел действително точки
до двама други възли, вместо само един.

74
00:03:27,080 --> 00:03:29,110
И така, ние трябва да се определи
старата началото на списъка

75
00:03:29,110 --> 00:03:32,151
да посочи назад към новия ръководител на
на свързан списък, който беше нещо

76
00:03:32,151 --> 00:03:33,990
ние не трябва да направите преди.

77
00:03:33,990 --> 00:03:37,420
И както и преди, ние просто се върне
указател към новия ръководител на списъка.

78
00:03:37,420 --> 00:03:38,220
>> Така че тук е списък.

79
00:03:38,220 --> 00:03:40,144
Искаме да въведете 12 в този списък.

80
00:03:40,144 --> 00:03:42,060
Забележете, че диаграмата
е малко по-различен.

81
00:03:42,060 --> 00:03:47,710
Всеки възел съдържа три fields--
данни, както и Next показалка в червено,

82
00:03:47,710 --> 00:03:50,170
Предишна и показалеца в синьо.

83
00:03:50,170 --> 00:03:54,059
Нищо не идва преди 15 възела,
така че си Previous показалка е нищожна.

84
00:03:54,059 --> 00:03:55,350
Това е началото на списъка.

85
00:03:55,350 --> 00:03:56,560
Няма нищо преди това.

86
00:03:56,560 --> 00:04:03,350
И нищо не идва след 10 възела и
така че това е Next показалка е нищожна, както добре.

87
00:04:03,350 --> 00:04:05,616
>> Така че нека да добавите 12 към този списък.

88
00:04:05,616 --> 00:04:08,070
Ние се нуждаем [недоловим] пространство за възела.

89
00:04:08,070 --> 00:04:11,480
Ние събрахме 12 вътре в него.

90
00:04:11,480 --> 00:04:14,840
И след това отново, ние трябва да бъдем наистина
Внимавайте да не се прекъсне веригата.

91
00:04:14,840 --> 00:04:17,144
Искаме да пренаредите
указатели в правилния ред.

92
00:04:17,144 --> 00:04:19,519
И понякога, че може mean--
както ще видим по-специално

93
00:04:19,519 --> 00:04:24,120
с delete--, че ние имаме някаква
съкратените указатели, но това е ОК.

94
00:04:24,120 --> 00:04:25,750
>> Така че това, което искаме да направим първо?

95
00:04:25,750 --> 00:04:28,290
Бих препоръчал
неща, които вероятно

96
00:04:28,290 --> 00:04:35,350
направя, трябва да попълните указателите от 12-те
възел, преди да докосне някой друг.

97
00:04:35,350 --> 00:04:38,640
Така че това, което се случва 12 да сочи към следващия?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
Онова, което идва преди 12?

100
00:04:42,430 --> 00:04:43,640
Нищо.

101
00:04:43,640 --> 00:04:46,280
Сега сме напълни
допълнителна информация в 12

102
00:04:46,280 --> 00:04:49,320
така че има Previous, Next, и стойност.

103
00:04:49,320 --> 00:04:53,505
>> Сега ние можем да имаме 15-- това допълнително
стъпка ние говорим about-- ние

104
00:04:53,505 --> 00:04:56,590
може да има 15 точка обратно към 12.

105
00:04:56,590 --> 00:04:59,634
И сега можем да се движим главата на
свързания списък да бъде също 12.

106
00:04:59,634 --> 00:05:02,550
Така че това е доста подобен на това, което ние
правехме с единично-свързани списъци,

107
00:05:02,550 --> 00:05:06,940
с изключение на допълнителна стъпка на
свързващ старата начело на списъка

108
00:05:06,940 --> 00:05:09,810
Обратно към новия ръководител на списъка.

109
00:05:09,810 --> 00:05:12,170
>> Сега нека най-накрая изтрийте
един възел от свързан списък.

110
00:05:12,170 --> 00:05:14,350
Така че нека да кажем, че имаме
някаква друга функция, която

111
00:05:14,350 --> 00:05:18,080
е намирането на възел искаме да изтриете
и ни е дал указател към точно

112
00:05:18,080 --> 00:05:19,710
възела, който ние искаме да изтриете.

113
00:05:19,710 --> 00:05:22,360
Ние дори не need-- изречете
главата е все още в световен мащаб обявена.

114
00:05:22,360 --> 00:05:23,590
Ние не се нуждаем главата тук.

115
00:05:23,590 --> 00:05:26,830
All тази функция се прави е ние сме
намерено указател към точно WE възел

116
00:05:26,830 --> 00:05:28,090
искате да се отървете от.

117
00:05:28,090 --> 00:05:28,940
Нека да се отървете от него.

118
00:05:28,940 --> 00:05:31,859
Това е много по-лесно с
двойно-свързани списъци.

119
00:05:31,859 --> 00:05:33,650
First-- това е всъщност
само на няколко неща.

120
00:05:33,650 --> 00:05:38,760
Ние просто трябва да се определи обкръжението
указатели възли, така че те прескачам

121
00:05:38,760 --> 00:05:40,240
възела искаме да изтриете.

122
00:05:40,240 --> 00:05:43,484
И тогава ние можем да изтриете този възел.

123
00:05:43,484 --> 00:05:45,150
Така че отново, ние просто преживява тук.

124
00:05:45,150 --> 00:05:49,625
Ние очевидно са решили, че
ние искаме да изтриете X. възел

125
00:05:49,625 --> 00:05:51,500
И отново, това, което аз съм
прави here-- от way--

126
00:05:51,500 --> 00:05:54,580
е общ случай за
възел, който е в средата.

127
00:05:54,580 --> 00:05:56,547
Има няколко на
допълнителни уговорки, които сте

128
00:05:56,547 --> 00:05:59,380
трябва да се помисли, когато сте изтриване
самото начало на списъка

129
00:05:59,380 --> 00:06:01,040
или в самия край на списъка.

130
00:06:01,040 --> 00:06:03,730
Има няколко специални
ъглови случаи да се справят с там.

131
00:06:03,730 --> 00:06:07,960
>> Така че това работи за изтриване на всеки възел
в средата на list-- този, който

132
00:06:07,960 --> 00:06:11,550
има законен показалеца напред
и законна показалеца назад,

133
00:06:11,550 --> 00:06:14,460
легитимна Previous Next и показалеца.

134
00:06:14,460 --> 00:06:16,530
Отново, ако работите
с краищата, ще

135
00:06:16,530 --> 00:06:18,500
трябва да се справят тези,
малко по-различно,

136
00:06:18,500 --> 00:06:19,570
и ние няма да
говорим за това сега.

137
00:06:19,570 --> 00:06:21,319
Но можете вероятно
разбера какво се нуждае

138
00:06:21,319 --> 00:06:24,610
да бъде направено само от гледане това видео.

139
00:06:24,610 --> 00:06:28,910
>> Така че ние сме изолиран X. X е възелът
ние искаме да изтриете от списъка.

140
00:06:28,910 --> 00:06:30,140
И какво ще правим?

141
00:06:30,140 --> 00:06:32,800
Първо, трябва да се пренаредят
външните указателите.

142
00:06:32,800 --> 00:06:35,815
Ние трябва да се пренаредят
9 следващия да пропуснете над 13

143
00:06:35,815 --> 00:06:38,030
и точка да 10-- които
е това, което ние току-що сте направили.

144
00:06:38,030 --> 00:06:41,180
И ние също трябва да
пренаредите 10 е Previous

145
00:06:41,180 --> 00:06:44,610
да сочи към 9 вместо сочейки към 13.

146
00:06:44,610 --> 00:06:46,490
>> Така че отново, това е най-
диаграма, за да започнете.

147
00:06:46,490 --> 00:06:47,730
Това беше нашата верига.

148
00:06:47,730 --> 00:06:51,027
Ние трябва да прескочим 13,
но ние трябва да се запазят също

149
00:06:51,027 --> 00:06:52,110
целостта на списъка.

150
00:06:52,110 --> 00:06:54,680
Ние не искаме да загубим
информация в двете посоки.

151
00:06:54,680 --> 00:06:59,620
Така че ние трябва да се пренаредят
указателите внимателно

152
00:06:59,620 --> 00:07:02,240
така че ние не се прекъсне веригата на всички.

153
00:07:02,240 --> 00:07:05,710
>> Така че можем да кажем, 9 Следваща показалка
точки на същото място

154
00:07:05,710 --> 00:07:08,040
че тринадесет Следваща
показалка посочва точно сега.

155
00:07:08,040 --> 00:07:10,331
Тъй като ние сме в крайна сметка
ще искате да пропуснете над 13.

156
00:07:10,331 --> 00:07:13,750
Така че, където и 13 точки следващия, вие
Искам да подчертая девет там, вместо.

157
00:07:13,750 --> 00:07:15,200
Така че това е, че.

158
00:07:15,200 --> 00:07:20,370
И след това, където и 13 точки назад
да, каквото и да е преди 13,

159
00:07:20,370 --> 00:07:24,800
ние искаме да отбележим 10
на това, че вместо 13.

160
00:07:24,800 --> 00:07:29,290
Сега забележи, ако следвате
стрелките, можем да падне 13

161
00:07:29,290 --> 00:07:32,380
без всъщност губи всякаква информация.

162
00:07:32,380 --> 00:07:36,002
Ние продължаваме да се целостта на списъка,
движи както напред и назад.

163
00:07:36,002 --> 00:07:38,210
И тогава можем просто някак
от него се почисти малко

164
00:07:38,210 --> 00:07:40,930
чрез издърпване списъка заедно.

165
00:07:40,930 --> 00:07:43,270
Така че ние реорганизира
указатели и от двете страни.

166
00:07:43,270 --> 00:07:46,231
И тогава ние остави на X
възел, който съдържа 13,

167
00:07:46,231 --> 00:07:47,480
и ние не се прекъсне веригата.

168
00:07:47,480 --> 00:07:50,980
Така че ние направихме добра.

169
00:07:50,980 --> 00:07:53,000
>> Final бележка тук на свързани списъци.

170
00:07:53,000 --> 00:07:55,990
Така както singly- и двойно по-свързано
списъци, както сме виждали,

171
00:07:55,990 --> 00:07:58,959
подкрепа наистина ефективен вмъкване
и заличаване на елементи.

172
00:07:58,959 --> 00:08:00,750
Можете да направите доста много
го в постоянна време.

173
00:08:00,750 --> 00:08:03,333
Какво трябва да направим, за да изтриете
елемент само на секунда преди?

174
00:08:03,333 --> 00:08:04,440
Преместихме една показалка.

175
00:08:04,440 --> 00:08:05,920
Преместихме друга показалка.

176
00:08:05,920 --> 00:08:07,915
Ние остави X-- отне три операции.

177
00:08:07,915 --> 00:08:14,500
Тя винаги отнема три операции за
изтриете че node-- да освободи един възел.

178
00:08:14,500 --> 00:08:15,280
>> Как да вмъкнете?

179
00:08:15,280 --> 00:08:17,280
Е, ние сме просто винаги
слепване на началото

180
00:08:17,280 --> 00:08:19,400
ако сме вмъкване ефективно.

181
00:08:19,400 --> 00:08:21,964
Така че ние трябва да rearrange--
в зависимост от това дали е

182
00:08:21,964 --> 00:08:24,380
а singly- или двойно по-свързана
списък, бихме могли да направим три нужда

183
00:08:24,380 --> 00:08:26,824
или четири операции макс.

184
00:08:26,824 --> 00:08:28,365
Но отново, тя винаги е три или четири.

185
00:08:28,365 --> 00:08:30,531
Няма значение колко
елементи са в нашия списък,

186
00:08:30,531 --> 00:08:33,549
тя винаги е три или четири operations--
точно като заличаване винаги

187
00:08:33,549 --> 00:08:35,320
три или четири операции.

188
00:08:35,320 --> 00:08:36,919
Това е константно време.

189
00:08:36,919 --> 00:08:38,169
Така че това е наистина страхотно.

190
00:08:38,169 --> 00:08:40,620
>> С масиви, което правехме
нещо като сортиране чрез вмъкване.

191
00:08:40,620 --> 00:08:44,739
Вероятно си припомним, че банкнотите
сортирай не е постоянна алгоритъм време.

192
00:08:44,739 --> 00:08:46,030
Това всъщност е доста скъпо.

193
00:08:46,030 --> 00:08:48,840
Така че това е много по-добре за вмъкване.

194
00:08:48,840 --> 00:08:51,840
Но както споменах в
поединично-свързан списък на видео,

195
00:08:51,840 --> 00:08:54,030
ние имаме един недостатък тук, нали?

196
00:08:54,030 --> 00:08:57,580
Ние сме загубили способността да
произволно достъп елементи.

197
00:08:57,580 --> 00:09:02,310
Не можем да кажем, искам елемент номер четири
или елемент номер 10 на свързан списък

198
00:09:02,310 --> 00:09:04,990
по същия начин, че можем
направите това с масив

199
00:09:04,990 --> 00:09:08,630
или можем просто директно индекс
в елемент нашия масив е.

200
00:09:08,630 --> 00:09:10,930
>> И така се опитва да намери
елемент в свързан list--

201
00:09:10,930 --> 00:09:15,880
ако търсенето е important--
Сега може да отнеме на линейното време.

202
00:09:15,880 --> 00:09:18,330
В списъка получава дълъг,
може да отнеме една допълнителна стъпка

203
00:09:18,330 --> 00:09:22,644
за всеки един елемент от списъка в
за да намерите това, което търсите.

204
00:09:22,644 --> 00:09:23,560
Така че има компромиси.

205
00:09:23,560 --> 00:09:25,780
Има малко на про
и против елемент тук.

206
00:09:25,780 --> 00:09:29,110
>> И двойно по-свързани списъци не са на
Последният вид комбинация структура на данните

207
00:09:29,110 --> 00:09:32,840
че ние ще говорим за,
като всички основни сградата

208
00:09:32,840 --> 00:09:34,865
блокове от C на пускането заедно.

209
00:09:34,865 --> 00:09:37,900
Защото в действителност, ние можем
дори направи по-добре от това

210
00:09:37,900 --> 00:09:41,970
за създаване на структура на данни, който
може да сте в състояние да се търси чрез

211
00:09:41,970 --> 00:09:43,360
в постоянен време също.

212
00:09:43,360 --> 00:09:46,080
Но повече за това в друг видеоклип.

213
00:09:46,080 --> 00:09:47,150
>> Аз съм Дъг Лойд.

214
00:09:47,150 --> 00:09:49,050
Това е CS50.

215
00:09:49,050 --> 00:09:50,877