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
Даг Ллоид: У реду.

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
кроз листу уместо
само напред кроз лист--

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
од лист-- јер смо додајући
екстра поље нашој структури

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
дефинитион-- ову представу
из претходног показивачем.

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
Зато враћа дллноде звезду.

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
Последња ствар коју треба да Па--
екстра ствар коју треба да урадите, ратхер--

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
можемо да идемо напред
и бацквардс-- који

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
Сваки чвор садржи три фиелдс--
података, а Следеће показивач у црвено,

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
А понекад да би Мислим--
као што ћемо видети посебно

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

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
Ništa.

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-- ово екстра
корак смо причаш-- смо ми

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
Ми чак не морају-- кажем
Глава је још увек у свету проглашена.

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
Фирст-- то је у ствари
само пар ствари.

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
Ми смо очигледно одлучио да
желимо да избришете Кс. чвор

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

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
>> Дакле, ово ради за брисање било ког чвора
у средини лист-- оне која

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
>> Тако смо изоловани Кс Кс је чвор
желимо избрисати са листе.

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
Дакле, како сингли- и двоструко повезана
листе, као што смо видели,

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
Ослободили смо Кс-- је три операције.

177
00:08:07,915 --> 00:08:14,500
Увек је потребно три операције на
избрисати те ноде-- да ослободи чвор.

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
Зато морамо да реарранге--
у зависности од тога да ли је

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

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
>> И тако покушава да нађе
елемент у повезаном лист--

201
00:09:10,930 --> 00:09:15,880
ако је претраживање ВАЗНО
сада могу узети линеарног времена.

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
блокови Ц стављајући заједно.

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
Ово је ЦС50.

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