1
00:00:00,000 --> 00:00:03,381
>> [Speel van musiek]

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

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Alle reg.

4
00:00:05,520 --> 00:00:07,860
So as jy klaar net dat
video op enkel-geskakelde lyste jammer

5
00:00:07,860 --> 00:00:09,568
Ek het jou af op 'n
bietjie van 'n fotonische lewe.

6
00:00:09,568 --> 00:00:12,790
Maar ek is bly dat jy hier is om te voltooi
die verhaal van dubbel-geskakelde lyste.

7
00:00:12,790 --> 00:00:15,250
>> So as jy onthou uit
dat die video, het ons gepraat

8
00:00:15,250 --> 00:00:18,500
oor hoe enkel-gekoppelde
lyste te doen by te woon ons vermoë

9
00:00:18,500 --> 00:00:22,090
om te gaan met inligting
waar die aantal elemente

10
00:00:22,090 --> 00:00:24,442
of die aantal items in
'n lys kan groei of krimp.

11
00:00:24,442 --> 00:00:26,400
Ons kan nou hanteer
iets soos dat, waar

12
00:00:26,400 --> 00:00:28,310
ons kon nie dit hanteer met skikkings.

13
00:00:28,310 --> 00:00:30,560
>> Maar hulle het ly aan een
kritieke beperking wat

14
00:00:30,560 --> 00:00:33,790
is dat met 'n enkel-gekoppelde
lys, kan ons net ooit beweeg

15
00:00:33,790 --> 00:00:36,200
in 'n enkele rigting deur die lys.

16
00:00:36,200 --> 00:00:39,010
En die enigste werklike situasie
waar wat 'n probleem kan raak

17
00:00:39,010 --> 00:00:41,250
was toe ons probeer om
verwyder 'n enkele element.

18
00:00:41,250 --> 00:00:46,000
En ons het nie eens bespreek hoe om dit te doen
in 'n enkel-geskakelde lys in pseudokode.

19
00:00:46,000 --> 00:00:48,797
Dit is beslis uitvoerbaar nie, maar
dit kan 'n bietjie van 'n probleem te wees.

20
00:00:48,797 --> 00:00:50,630
So as jy jouself
in 'n situasie waar

21
00:00:50,630 --> 00:00:53,175
jy probeer om te verwyder
enkele elemente uit die lys

22
00:00:53,175 --> 00:00:55,430
of dit gaan nodig wees
dat jy sal die verwydering

23
00:00:55,430 --> 00:00:57,970
enkele elemente van
die lys, kan jy wil

24
00:00:57,970 --> 00:01:02,090
oorweeg om 'n dubbel-gekoppelde
lys plaas van 'n enkel-geskakelde lys.

25
00:01:02,090 --> 00:01:06,320
Omdat dubbel-geskakelde lyste toelaat
beide vorentoe en agtertoe beweeg

26
00:01:06,320 --> 00:01:09,340
deur die lys plaas van
net vorentoe deur die list--

27
00:01:09,340 --> 00:01:13,950
net deur die toevoeging van 'n ekstra element
om ons struktuur definisie

28
00:01:13,950 --> 00:01:16,690
vir die dubbel-geskakelde lys knoop.

29
00:01:16,690 --> 00:01:19,770
>> Weereens, as jy nie van plan om
enkele elemente verwydering

30
00:01:19,770 --> 00:01:24,810
uit die list-- omdat ons die toevoeging
'n ekstra veld om ons struktuur

31
00:01:24,810 --> 00:01:28,340
definisie, die nodes hulself
vir dubbel-geskakelde lyste

32
00:01:28,340 --> 00:01:29,550
gaan groter wees.

33
00:01:29,550 --> 00:01:31,600
Hulle gaan neem
meer grepe van die geheue.

34
00:01:31,600 --> 00:01:34,160
En so as dit is nie iets
jy gaan nodig om te doen,

35
00:01:34,160 --> 00:01:36,300
jy kan besluit dit is
nie die moeite werd die handel af

36
00:01:36,300 --> 00:01:39,360
om die ekstra spandeer
grepe van die geheue benodig

37
00:01:39,360 --> 00:01:43,940
vir 'n dubbel-geskakelde lys as jy nie
gaan skrap enkele elemente.

38
00:01:43,940 --> 00:01:46,760
Maar dit is ook koel
vir ander dinge ook.

39
00:01:46,760 --> 00:01:51,260
>> So as ek gesê het, het ons net om by te voeg
'n enkele veld om ons struktuur

40
00:01:51,260 --> 00:01:55,360
definition-- hierdie idee
van 'n vorige wyser.

41
00:01:55,360 --> 00:01:58,620
So met 'n enkel-geskakelde lys, ons
het die waarde en die Volgende pointer,

42
00:01:58,620 --> 00:02:02,850
so die dubbel-geskakelde lys het net
'n manier om agteruit beweeg as well.

43
00:02:02,850 --> 00:02:04,960
>> Nou in die enkel-gekoppelde
lys video, het ons gepraat

44
00:02:04,960 --> 00:02:07,210
oor hierdie is vyf van die
belangrikste dinge wat jy nodig het om te wees

45
00:02:07,210 --> 00:02:09,449
in staat wees om te doen om te werk met geskakelde lyste.

46
00:02:09,449 --> 00:02:12,880
En vir die meeste van hierdie, die feit
dat dit 'n dubbel-geskakelde lys

47
00:02:12,880 --> 00:02:14,130
is nie regtig 'n groot sprong.

48
00:02:14,130 --> 00:02:17,936
Ons kan nog steeds deur soek deur net
vorentoe beweeg van begin tot einde.

49
00:02:17,936 --> 00:02:20,810
Ons kan nog steeds skep 'n node uit
lug, pretty much dieselfde manier.

50
00:02:20,810 --> 00:02:23,591
Ons kan lyste mooi verwyder
baie dieselfde manier ook.

51
00:02:23,591 --> 00:02:25,340
Die enigste dinge wat
is subtiel verskillende,

52
00:02:25,340 --> 00:02:28,970
regtig, is die invoeging
nuwe nodes in die lys,

53
00:02:28,970 --> 00:02:33,722
en ons sal uiteindelik praat oor die verwydering van
'n enkele element van die lys as well.

54
00:02:33,722 --> 00:02:35,430
Weereens, pretty much
die ander drie, ons is

55
00:02:35,430 --> 00:02:37,888
nie gaan om te praat oor hulle
nou, want hulle is net

56
00:02:37,888 --> 00:02:43,920
baie klein tweaked op die idees bespreek
in die enkel-geskakelde lys video.

57
00:02:43,920 --> 00:02:46,292
>> So laat voeg 'n nuwe node
in 'n dubbel-geskakelde lys.

58
00:02:46,292 --> 00:02:48,750
Ons het gepraat oor hierdie vir doen
enkel-geskakelde lyste, asook,

59
00:02:48,750 --> 00:02:52,020
maar daar is 'n paar ekstra
vang met dubbel-geskakelde lyste.

60
00:02:52,020 --> 00:02:55,280
Ons is [? verby?] in die kop van die
lys hier en 'n paar arbitrêre waarde

61
00:02:55,280 --> 00:02:58,600
en ons wil hê dat die nuwe hoof kry
van die lys van hierdie funksie.

62
00:02:58,600 --> 00:03:01,414
Dit is waarom dit gee 'n dllnode ster.

63
00:03:01,414 --> 00:03:02,330
So, wat is die stappe?

64
00:03:02,330 --> 00:03:04,496
Hulle is, weer, baie soortgelyk
om enkel-geskakelde lyste

65
00:03:04,496 --> 00:03:05,670
met 'n ekstra toevoeging.

66
00:03:05,670 --> 00:03:08,900
Ons wil ruimte ken vir 'n nuwe
knoop en check om seker te maak dit is geldig.

67
00:03:08,900 --> 00:03:11,510
Ons wil hê dat die node vul
met alles wat inligting wat ons

68
00:03:11,510 --> 00:03:12,564
wil in dit te sit.

69
00:03:12,564 --> 00:03:15,480
Die laaste ding wat ons nodig het om die do--
ekstra ding wat ons nodig het om te doen, rather--

70
00:03:15,480 --> 00:03:19,435
is om die vorige wyser los
van die ou hoof van die lys.

71
00:03:19,435 --> 00:03:21,310
Onthou dat, omdat
van dubbel-geskakelde lyste,

72
00:03:21,310 --> 00:03:23,110
kan ons vorentoe beweeg
en backwards-- wat

73
00:03:23,110 --> 00:03:27,080
beteken dat elke node eintlik wys
twee ander nodes in plaas van net een.

74
00:03:27,080 --> 00:03:29,110
En so het ons nodig het om te los
die ou hoof van die lys

75
00:03:29,110 --> 00:03:32,151
agteruit verwys na die nuwe hoof van
die geskakelde lys, wat iets

76
00:03:32,151 --> 00:03:33,990
ons het nie om voor te doen.

77
00:03:33,990 --> 00:03:37,420
En soos voorheen, het ons net terug n
wyser na die nuwe hoof van die lys.

78
00:03:37,420 --> 00:03:38,220
>> So hier is 'n lys.

79
00:03:38,220 --> 00:03:40,144
Ons wil voeg 12 in hierdie lys.

80
00:03:40,144 --> 00:03:42,060
Let daarop dat die diagram
is effens anders.

81
00:03:42,060 --> 00:03:47,710
Elke node drie fields-- bevat
data, en 'n Volgende wyser in rooi,

82
00:03:47,710 --> 00:03:50,170
en 'n Vorige wyser in blou.

83
00:03:50,170 --> 00:03:54,059
Niks kom voor die 15 node,
so sy vorige wyser is null.

84
00:03:54,059 --> 00:03:55,350
Dit is die begin van die lys.

85
00:03:55,350 --> 00:03:56,560
Daar is niks voor dit.

86
00:03:56,560 --> 00:04:03,350
En niks kom nadat die 10-knoop, en
so dit is Volgende wyser is null as well.

87
00:04:03,350 --> 00:04:05,616
>> So laat voeg 12 tot hierdie lys.

88
00:04:05,616 --> 00:04:08,070
Ons moet [onhoorbaar] ruimte vir die knoop.

89
00:04:08,070 --> 00:04:11,480
Ons het 12 binnekant van dit.

90
00:04:11,480 --> 00:04:14,840
En dan weer, moet ons werklik
versigtig wees om nie die ketting breek.

91
00:04:14,840 --> 00:04:17,144
Ons wil die herrangskik
wysers in die korrekte volgorde.

92
00:04:17,144 --> 00:04:19,519
En soms wat kan mean--
soos ons sal sien veral

93
00:04:19,519 --> 00:04:24,120
met delete-- dat ons het 'n paar
oorbodig wysers, maar dit is OK.

94
00:04:24,120 --> 00:04:25,750
>> So wat wil ons eerste om te doen?

95
00:04:25,750 --> 00:04:28,290
Ek sou aanbeveel die
dinge wat jy moet waarskynlik

96
00:04:28,290 --> 00:04:35,350
doen om die wysers van die 12 vul
node voordat jy raak enigiemand anders.

97
00:04:35,350 --> 00:04:38,640
So, wat is 12 volgende gaan wys?

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

99
00:04:39,860 --> 00:04:42,430
Wat kom voor 12?

100
00:04:42,430 --> 00:04:43,640
Niks nie.

101
00:04:43,640 --> 00:04:46,280
Nou het ons die vol
bykomende inligting in 12

102
00:04:46,280 --> 00:04:49,320
so dit het Vorige, Volgende, en waarde.

103
00:04:49,320 --> 00:04:53,505
>> Nou kan ons '15-- hierdie ekstra
stap ons about-- ons praat

104
00:04:53,505 --> 00:04:56,590
kan 15 punt terug na 12 hê.

105
00:04:56,590 --> 00:04:59,634
En nou kan ons die hoof van beweeg
die geskakelde lys om ook 12.

106
00:04:59,634 --> 00:05:02,550
So dit is redelik soortgelyk aan wat ons
besig was met enkel-geskakelde lyste,

107
00:05:02,550 --> 00:05:06,940
behalwe vir die ekstra stap van
die koppeling van die ou hoof van die lys

108
00:05:06,940 --> 00:05:09,810
terug na die nuwe hoof van die lys.

109
00:05:09,810 --> 00:05:12,170
>> Nou laat uiteindelik verwyder
'n knoop van 'n geskakelde lys.

110
00:05:12,170 --> 00:05:14,350
So kom ons sê ons het
'n ander funksie wat

111
00:05:14,350 --> 00:05:18,080
is om 'n node ons wil verwyder
en het ons 'n wyser gegee om presies te

112
00:05:18,080 --> 00:05:19,710
die knoop wat ons wil verwyder.

113
00:05:19,710 --> 00:05:22,360
Ons weet nie eens need-- sê die
hoof is nog steeds globaal verklaar.

114
00:05:22,360 --> 00:05:23,590
Ons het die hoof nie hier nodig.

115
00:05:23,590 --> 00:05:26,830
Alle hierdie funksie te doen, is ons het
het 'n wyser presies die knoop ons

116
00:05:26,830 --> 00:05:28,090
wil ontslae te raak.

117
00:05:28,090 --> 00:05:28,940
Kom ons kry ontslae te raak van dit.

118
00:05:28,940 --> 00:05:31,859
Dit is 'n baie makliker met
dubbel-geskakelde lyste.

119
00:05:31,859 --> 00:05:33,650
First-- dit is eintlik
net 'n paar dinge.

120
00:05:33,650 --> 00:05:38,760
Ons moet net los die omliggende
wysers nodes 'sodat hulle slaan oor

121
00:05:38,760 --> 00:05:40,240
die knoop ons wil verwyder.

122
00:05:40,240 --> 00:05:43,484
En dan kan ons dit node verwyder.

123
00:05:43,484 --> 00:05:45,150
So weer, ons is maar net gaan deur hier.

124
00:05:45,150 --> 00:05:49,625
Ons het blykbaar besluit dat
ons wil die node X. verwyder

125
00:05:49,625 --> 00:05:51,500
En weer, wat ek
doen here-- deur die way--

126
00:05:51,500 --> 00:05:54,580
is 'n algemene saak vir 'n
node wat in die middel.

127
00:05:54,580 --> 00:05:56,547
Daar is 'n paar van
ekstra voorbehoude dat jy

128
00:05:56,547 --> 00:05:59,380
nodig om te oorweeg wanneer jy die verwydering van
die begin van die lys

129
00:05:59,380 --> 00:06:01,040
of die einde van die lys.

130
00:06:01,040 --> 00:06:03,730
Daar is 'n paar van die spesiale
hoek gevalle te hanteer is daar.

131
00:06:03,730 --> 00:06:07,960
>> So dit werk vir die verwydering van enige node
in die middel van die een wat list--

132
00:06:07,960 --> 00:06:11,550
het 'n wettige wyser vorentoe
en 'n wettige wyser agtertoe,

133
00:06:11,550 --> 00:06:14,460
wettige Volgende en Vorige wyser.

134
00:06:14,460 --> 00:06:16,530
Weereens, as jy werk
met die punte, wat jy

135
00:06:16,530 --> 00:06:18,500
moet daardie hanteer
effens anders,

136
00:06:18,500 --> 00:06:19,570
en ons is nie van plan om
praat oor wat nou.

137
00:06:19,570 --> 00:06:21,319
Maar jy kan waarskynlik
uit te vind wat nodig

138
00:06:21,319 --> 00:06:24,610
net gedoen word deur te kyk na hierdie video.

139
00:06:24,610 --> 00:06:28,910
>> Dus het ons geïsoleer X. X is die node
Ons wil verwyder uit die lys.

140
00:06:28,910 --> 00:06:30,140
Wat doen ons?

141
00:06:30,140 --> 00:06:32,800
Eerstens moet ons om te herrangskik
buite wenke.

142
00:06:32,800 --> 00:06:35,815
Ons moet herrangskik
9 se volgende oor te slaan oor 13

143
00:06:35,815 --> 00:06:38,030
en punt om 10-- wat
is wat ons net gedoen het.

144
00:06:38,030 --> 00:06:41,180
En ons moet ook
herrangskik 10 se Vorige

145
00:06:41,180 --> 00:06:44,610
om te wys op 9 in plaas van wys na 13.

146
00:06:44,610 --> 00:06:46,490
>> So weer, dit was die
diagram om te begin met.

147
00:06:46,490 --> 00:06:47,730
Dit was ons ketting.

148
00:06:47,730 --> 00:06:51,027
Ons moet spring oor 13,
maar ons moet ook bewaar

149
00:06:51,027 --> 00:06:52,110
die integriteit van die lys.

150
00:06:52,110 --> 00:06:54,680
Ons wil nie enige verloor
inligting in enige rigting.

151
00:06:54,680 --> 00:06:59,620
So moet ons herrangskik
die wysers versigtig

152
00:06:59,620 --> 00:07:02,240
sodat ons nie die ketting breek nie.

153
00:07:02,240 --> 00:07:05,710
>> So kan ons 9 se Volgende wyser sê
wys na dieselfde plek

154
00:07:05,710 --> 00:07:08,040
dat dertien se Volgende
wyser wys nou.

155
00:07:08,040 --> 00:07:10,331
Want ons is uiteindelik
gaan wil slaan oor 13.

156
00:07:10,331 --> 00:07:13,750
So waar 13 punte Volgende, moet jy
wil nege wys daar plaas.

157
00:07:13,750 --> 00:07:15,200
So dit is nie.

158
00:07:15,200 --> 00:07:20,370
En dan waar 13 punte agter
om, ongeag kom voor 13,

159
00:07:20,370 --> 00:07:24,800
ons wil 10 te wys
om in plaas van 13.

160
00:07:24,800 --> 00:07:29,290
Nou sien, as jy volg
die pyle, kan ons drop 13

161
00:07:29,290 --> 00:07:32,380
sonder enige inligting eintlik verloor.

162
00:07:32,380 --> 00:07:36,002
Ons het die integriteit van die lys gehou,
beweeg beide vorentoe en agtertoe.

163
00:07:36,002 --> 00:07:38,210
En dan kan ons net soort
van skoon dit 'n bietjie

164
00:07:38,210 --> 00:07:40,930
deur saam te trek in die lys.

165
00:07:40,930 --> 00:07:43,270
Sodat ons herrangskik die
wysers aan weerskante.

166
00:07:43,270 --> 00:07:46,231
En dan het ons bevry X die
node wat 13 vervat,

167
00:07:46,231 --> 00:07:47,480
en ons het nie breek die ketting.

168
00:07:47,480 --> 00:07:50,980
So ons het 'n goeie.

169
00:07:50,980 --> 00:07:53,000
>> Finale boodskap hier op geskakelde lyste.

170
00:07:53,000 --> 00:07:55,990
Sodat beide singly- en dubbel-gekoppelde
lyste, soos ons gesien het,

171
00:07:55,990 --> 00:07:58,959
ondersteuning regtig doeltreffende invoeging
en skrap elemente.

172
00:07:58,959 --> 00:08:00,750
Jy kan pretty much doen
dit in konstante tyd.

173
00:08:00,750 --> 00:08:03,333
Wat het ons te doen het om te verwyder
'n element net 'n tweede gelede?

174
00:08:03,333 --> 00:08:04,440
Ons het verhuis een wyser.

175
00:08:04,440 --> 00:08:05,920
Ons het verhuis ander wyser.

176
00:08:05,920 --> 00:08:07,915
Ons bevry X-- het drie operasies.

177
00:08:07,915 --> 00:08:14,500
Dit vind altyd drie operasies om
dat node-- verwyder om 'n knoop te bevry.

178
00:08:14,500 --> 00:08:15,280
>> Hoe weet ons plaas?

179
00:08:15,280 --> 00:08:17,280
Wel, ons is net altyd
rygwerk op die begin

180
00:08:17,280 --> 00:08:19,400
as ons doeltreffend te voeg.

181
00:08:19,400 --> 00:08:21,964
So moet ons rearrange--
afhangende van of dit

182
00:08:21,964 --> 00:08:24,380
'n singly- of dubbel-gekoppelde
lys, kan ons nodig het om te doen drie

183
00:08:24,380 --> 00:08:26,824
of vier operasies max.

184
00:08:26,824 --> 00:08:28,365
Maar weereens, dit is altyd drie of vier.

185
00:08:28,365 --> 00:08:30,531
Dit maak nie saak hoeveel
elemente is in ons lys,

186
00:08:30,531 --> 00:08:33,549
dit is altyd drie of vier operations--
net soos skrap is altyd

187
00:08:33,549 --> 00:08:35,320
drie of vier bedrywighede.

188
00:08:35,320 --> 00:08:36,919
Dit is konstante tyd.

189
00:08:36,919 --> 00:08:38,169
So dit is regtig baie goed.

190
00:08:38,169 --> 00:08:40,620
>> Met skikkings, ons doen
iets soos invoeging soort.

191
00:08:40,620 --> 00:08:44,739
Jy onthou seker dat invoeging
soort is nie 'n konstante tyd algoritme.

192
00:08:44,739 --> 00:08:46,030
Dit is eintlik redelik duur.

193
00:08:46,030 --> 00:08:48,840
So, dit is 'n baie beter vir die inbring.

194
00:08:48,840 --> 00:08:51,840
Maar soos ek in die genoemde
enkel-geskakelde lys video,

195
00:08:51,840 --> 00:08:54,030
ons het 'n nadeel het ook hier, reg?

196
00:08:54,030 --> 00:08:57,580
Ons het die vermoë om te verloor
lukraak toegang elemente.

197
00:08:57,580 --> 00:09:02,310
Ons kan nie sê, ek wil element nommer vier
of element nommer 10 van 'n geskakelde lys

198
00:09:02,310 --> 00:09:04,990
dieselfde manier wat ons kan
doen met 'n verskeidenheid

199
00:09:04,990 --> 00:09:08,630
Of ons kan net direk indeks
in ons verskeidenheid element se.

200
00:09:08,630 --> 00:09:10,930
>> En so probeer om 'n te vind
element in 'n gekoppelde list--

201
00:09:10,930 --> 00:09:15,880
As soek is important--
kan nou lineêre tyd.

202
00:09:15,880 --> 00:09:18,330
As die lys langer kry, is dit
dalk een addisionele stap

203
00:09:18,330 --> 00:09:22,644
vir elke enkele element in die lys in
om uit te vind wat ons soek.

204
00:09:22,644 --> 00:09:23,560
So is daar handel offs.

205
00:09:23,560 --> 00:09:25,780
Daar is 'n bietjie van 'n pro
en con element hier.

206
00:09:25,780 --> 00:09:29,110
>> En dubbel-geskakelde lyste is nie die
laaste soort data struktuur kombinasie

207
00:09:29,110 --> 00:09:32,840
dat ons sal praat oor,
neem al die basiese bou

208
00:09:32,840 --> 00:09:34,865
blokke van C 'n plaas saam.

209
00:09:34,865 --> 00:09:37,900
Want in werklikheid, kan ons
selfs beter as dit doen

210
00:09:37,900 --> 00:09:41,970
om 'n struktuur te skep wat data
jy dalk in staat wees om te soek deur

211
00:09:41,970 --> 00:09:43,360
in konstante tyd ook.

212
00:09:43,360 --> 00:09:46,080
Maar meer oor dit in 'n ander video.

213
00:09:46,080 --> 00:09:47,150
>> Ek is Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Dit is CS50.

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