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
Јас ќе останев на
малку cliffhanger.

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
А ние дури и не разговараат за тоа како да го направи тоа
во одделно-поврзани листа во pseudocode а.

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

20
00:00:48,797 --> 00:00:50,630
Значи, ако се наоѓате себеси
во ситуација каде што

21
00:00:50,630 --> 00:00:53,175
што се обидувате да ги избришете
поединечни елементи од листата

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

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

24
00:00:57,970 --> 00:01:02,090
да се разгледа со користење на двојно-поврзана
листата наместо одделно-поврзани листа.

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

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

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

28
00:01:13,950 --> 00:01:16,690
за двојно-поврзани листа јазол.

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

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

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

32
00:01:28,340 --> 00:01:29,550
се ќе биде поголем.

33
00:01:29,550 --> 00:01:31,600
Тие се случува да се земе
повеќе бајти меморија.

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

35
00:01:34,160 --> 00:01:36,300
може да одлучи дека е
не вреди да се пласирам

36
00:01:36,300 --> 00:01:39,360
да треба да се трошат екстра
бајти меморија потребно

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

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

39
00:01:46,760 --> 00:01:51,260
>> Па како што реков, ние само треба да додадете
една единствена област на нашата структура

40
00:01:51,260 --> 00:01:55,360
definition-- овој поим
Назад на покажувачот.

41
00:01:55,360 --> 00:01:58,620
Па со одделно-поврзани листа, ние
има вредност и следниот покажувач,

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

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

44
00:02:04,960 --> 00:02:07,210
за овие пет од
главните работи што треба да бидат

45
00:02:07,210 --> 00:02:09,449
можност да го направите да работи со поврзани листи.

46
00:02:09,449 --> 00:02:12,880
И за повеќето од овие, фактот
дека тоа е двојно-поврзани листа

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

48
00:02:14,130 --> 00:02:17,936
Ние се уште може да пребарувате низ само со
се движат напред од почеток до крај.

49
00:02:17,936 --> 00:02:20,810
Ние се уште може да се создаде еден јазол од
воздух, прилично многу исти начин.

50
00:02:20,810 --> 00:02:23,591
Можеме да го избришете списокот прилично
на ист начин исто така.

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

52
00:02:25,340 --> 00:02:28,970
навистина, се вметнуваат
нови јазли во листата,

53
00:02:28,970 --> 00:02:33,722
и ние конечно ќе зборуваме за бришење
еден елемент од листата, како и.

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

55
00:02:35,430 --> 00:02:37,888
не одам да се зборува за нив
во моментов, бидејќи тие се само

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

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

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

59
00:02:48,750 --> 00:02:52,020
но има неколку екстра
фаќа со двојно-поврзани листи.

60
00:02:52,020 --> 00:02:55,280
Ние сме [? поминува?] во главата на
листата тука и некои произволни вредност,

61
00:02:55,280 --> 00:02:58,600
и ние сакаме да се добие нов шеф
на листата од оваа функција.

62
00:02:58,600 --> 00:03:01,414
Тоа е зошто тоа се враќа dllnode ѕвезда.

63
00:03:01,414 --> 00:03:02,330
Па што се чекори?

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

65
00:03:04,496 --> 00:03:05,670
со еден екстра прилог.

66
00:03:05,670 --> 00:03:08,900
Ние сакаме да се одвојува простор за нова
јазол и проверете, за да бидете сигурни дека тоа е валиден.

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

68
00:03:11,510 --> 00:03:12,564
сакате да се стави во неа.

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

70
00:03:15,480 --> 00:03:19,435
е да ја поправите Претходна покажувачот
на стариот шеф на листата.

71
00:03:19,435 --> 00:03:21,310
Се сеќавам дека поради
на двојно-поврзани листи,

72
00:03:21,310 --> 00:03:23,110
ние може да се движи напред
и backwards-- која

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

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

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

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

77
00:03:33,990 --> 00:03:37,420
И како и досега, ние едноставно се врати
Покажувач на новиот шеф на листата.

78
00:03:37,420 --> 00:03:38,220
>> Значи тука е листа.

79
00:03:38,220 --> 00:03:40,144
Ние сакаме да внесете 12 во оваа листа.

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

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

82
00:03:47,710 --> 00:03:50,170
Претходната и покажувачот во сина боја.

83
00:03:50,170 --> 00:03:54,059
Ништо не доаѓа пред 15 јазли,
па нејзините Претходна покажувачот е нула.

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

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

86
00:03:56,560 --> 00:04:03,350
И ништо не се доаѓа по 10 јазли, како и
па тоа е Следна покажувачот е нула, како и.

87
00:04:03,350 --> 00:04:05,616
>> Па ајде да додадете 12 на оваа листа.

88
00:04:05,616 --> 00:04:08,070
Ние треба [Беззвучен] простор за јазол.

89
00:04:08,070 --> 00:04:11,480
Ќе стави 12 во него.

90
00:04:11,480 --> 00:04:14,840
А потоа повторно, ние треба да биде навистина
внимателни да не се скрши синџирот.

91
00:04:14,840 --> 00:04:17,144
Ние сакаме да ги преуредите
покажувачи во правилен ред.

92
00:04:17,144 --> 00:04:19,519
А понекогаш и кои би можеле да mean--
како што ќе видиме, особено

93
00:04:19,519 --> 00:04:24,120
со delete-- дека ние имаме некои
излишни покажувачи, но тоа е во ред.

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

95
00:04:25,750 --> 00:04:28,290
Јас ќе им препорачаат на
работи што требаше

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

97
00:04:35,350 --> 00:04:38,640
Значи, што е 12 случува да се укаже на следно?

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

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

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

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

102
00:04:46,280 --> 00:04:49,320
така што има Претходно, Напред, и вредност.

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

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

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

106
00:04:59,634 --> 00:05:02,550
Така, тоа е прилично слична на она што го
прават во одделно-поврзани листи,

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

108
00:05:06,940 --> 00:05:09,810
назад на новиот шеф на листата.

109
00:05:09,810 --> 00:05:12,170
>> Сега ајде да конечно бришење
еден јазол од поврзани листа.

110
00:05:12,170 --> 00:05:14,350
Па да речеме имаме
некоја друга функција што

111
00:05:14,350 --> 00:05:18,080
е да се најде еден јазол што сакаме да го избришете
и ни даде покажувач точно

112
00:05:18,080 --> 00:05:19,710
јазол дека сакате да ја избришете.

113
00:05:19,710 --> 00:05:22,360
Ние дури и не need-- велат дека
главата се уште глобално декларирана.

114
00:05:22,360 --> 00:05:23,590
Ние не треба главата тука.

115
00:05:23,590 --> 00:05:26,830
Сите оваа функција се прави е да имаме
Пронајдени покажувач токму ние јазол

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

117
00:05:28,090 --> 00:05:28,940
Ајде да се ослободи од неа.

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

119
00:05:31,859 --> 00:05:33,650
First-- тоа е всушност
само неколку работи.

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

121
00:05:38,760 --> 00:05:40,240
јазол што сакаме да го избришете.

122
00:05:40,240 --> 00:05:43,484
И потоа можеме да го избришете тој јазол.

123
00:05:43,484 --> 00:05:45,150
Значи, повторно, ние сме само ќе низ овде.

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

125
00:05:49,625 --> 00:05:51,500
И повторно, она што јас сум
прави here-- од way--

126
00:05:51,500 --> 00:05:54,580
е општ случај за
јазол кој е во средината.

127
00:05:54,580 --> 00:05:56,547
Постојат неколку
дополнителни ограничувања кои ви

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

129
00:05:59,380 --> 00:06:01,040
или на самиот крај на листата.

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

131
00:06:03,730 --> 00:06:07,960
>> Па тоа работи за бришење на јазол
во средината на list-- оној кој

132
00:06:07,960 --> 00:06:11,550
има легитимно покажувачот напред
и легитимен покажувачот наназад,

133
00:06:11,550 --> 00:06:14,460
легитимни Претходната и следната покажувачот.

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

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

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

137
00:06:19,570 --> 00:06:21,319
Но вие веројатно може да
дознаам што треба

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

139
00:06:24,610 --> 00:06:28,910
>> Значи ние сме изолирани 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 Претходни

145
00:06:41,180 --> 00:06:44,610
да се упати на 9 наместо да укажува до 13.

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

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

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

149
00:06:51,027 --> 00:06:52,110
интегритетот на листата.

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

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

152
00:06:59,620 --> 00:07:02,240
па ние не се скрши синџирот на сите.

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

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

155
00:07:08,040 --> 00:07:10,331
Бидејќи ние сме на крајот
ќе сакате да го прескокнете над 13.

156
00:07:10,331 --> 00:07:13,750
Значи каде и 13 поени Следно,
сакате девет до точка таму, наместо.

157
00:07:13,750 --> 00:07:15,200
Значи тоа е тоа.

158
00:07:15,200 --> 00:07:20,370
А потоа каде 13 поени назад
да, она што доаѓа пред 13,

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

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

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

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

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

164
00:07:38,210 --> 00:07:40,930
со повлекување на листата заедно.

165
00:07:40,930 --> 00:07:43,270
Па ние преуредува на
покажувачи на двете страни.

166
00:07:43,270 --> 00:07:46,231
А потоа ние ослободени Х
јазли, кои се содржани 13,

167
00:07:46,231 --> 00:07:47,480
а ние не се скрши синџирот.

168
00:07:47,480 --> 00:07:50,980
Па ние го сторивме добро.

169
00:07:50,980 --> 00:07:53,000
>> Последната забелешка тука на поврзани листи.

170
00:07:53,000 --> 00:07:55,990
Па и двете 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
Па, ние сме само секогаш
tacking на почетокот

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
тоа е секогаш три или четири операции-
исто како и бришење е секогаш

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
Значи има трговски off.

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