1
00:00:00,000 --> 00:00:03,381
>> [Musik spiller]

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

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

4
00:00:05,520 --> 00:00:07,860
Så hvis du lige blevet færdig, at
video på enkeltvis forbundne lister sorry

5
00:00:07,860 --> 00:00:09,568
Jeg forlod dig ud på en
lidt af en cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Men jeg er glad for du er her for at afslutte
historien om dobbelt forbundne lister.

7
00:00:12,790 --> 00:00:15,250
>> Så hvis du husker fra
at video, vi talte

8
00:00:15,250 --> 00:00:18,500
om, hvordan enkeltvis forbundne
lister gør deltage i vores evne

9
00:00:18,500 --> 00:00:22,090
at behandle oplysninger
hvor antallet af elementer

10
00:00:22,090 --> 00:00:24,442
eller antallet af elementer i
en liste kan vokse eller skrumpe.

11
00:00:24,442 --> 00:00:26,400
Vi kan nu håndtere
noget lignende, hvor

12
00:00:26,400 --> 00:00:28,310
vi ikke kunne håndtere det med arrays.

13
00:00:28,310 --> 00:00:30,560
>> Men de lider af en
kritisk begrænsning som

14
00:00:30,560 --> 00:00:33,790
er, at med en enkelt-koblet
liste, kan vi kun nogensinde flytte

15
00:00:33,790 --> 00:00:36,200
i en enkelt retning gennem listen.

16
00:00:36,200 --> 00:00:39,010
Og den eneste virkelige situation
hvor der kan blive et problem

17
00:00:39,010 --> 00:00:41,250
var, da vi forsøgte at
slette et enkelt element.

18
00:00:41,250 --> 00:00:46,000
Og vi ikke engang diskutere, hvordan man gør det
i et enkelt-linket liste i pseudokode.

19
00:00:46,000 --> 00:00:48,797
Det er helt sikkert gennemførligt, men
det kan være lidt af en besværet.

20
00:00:48,797 --> 00:00:50,630
Så hvis du finder dig selv
i en situation, hvor

21
00:00:50,630 --> 00:00:53,175
du forsøger at slette
enkelte elementer fra listen

22
00:00:53,175 --> 00:00:55,430
eller det vil blive krævet
at du vil være at slette

23
00:00:55,430 --> 00:00:57,970
enkelte elementer fra
listen, kan du

24
00:00:57,970 --> 00:01:02,090
overveje at anvende en dobbelt-bundet
listen i stedet for en enkelt-linket liste.

25
00:01:02,090 --> 00:01:06,320
Fordi dobbelt forbundne lister giver dig mulighed
at flytte både forlæns og baglæns

26
00:01:06,320 --> 00:01:09,340
gennem listen i stedet for
lige fremad gennem list--

27
00:01:09,340 --> 00:01:13,950
bare ved at tilføje en ekstra element
til vores struktur definition

28
00:01:13,950 --> 00:01:16,690
for den dobbelt-linkede liste node.

29
00:01:16,690 --> 00:01:19,770
>> Igen, hvis du ikke kommer til at
være at slette enkelte elementer

30
00:01:19,770 --> 00:01:24,810
fra list-- fordi vi tilføjer
et ekstra felt til vores struktur

31
00:01:24,810 --> 00:01:28,340
definition, knudepunkterne selv
for dobbelt-hægtede lister

32
00:01:28,340 --> 00:01:29,550
vil være større.

33
00:01:29,550 --> 00:01:31,600
De kommer til at tage
op flere bytes hukommelse.

34
00:01:31,600 --> 00:01:34,160
Og så hvis dette ikke er noget
du får brug for at gøre,

35
00:01:34,160 --> 00:01:36,300
du kan beslutte, det er
ikke værd at afvejningen

36
00:01:36,300 --> 00:01:39,360
nødt til at bruge de ekstra
bytes hukommelse kræves

37
00:01:39,360 --> 00:01:43,940
for en dobbelt-linked liste, hvis du ikke er
vil være at slette enkelte elementer.

38
00:01:43,940 --> 00:01:46,760
Men de er også køligt
til andre ting også.

39
00:01:46,760 --> 00:01:51,260
>> Så som jeg sagde, vi bare nødt til at tilføje
én enkelt felt til vores struktur

40
00:01:51,260 --> 00:01:55,360
definition-- dette begreb
af en tidligere pointer.

41
00:01:55,360 --> 00:01:58,620
Så med en enkelt-linket liste, vi
har værdi og næste pointer,

42
00:01:58,620 --> 00:02:02,850
så den dobbelt-linkede liste har blot
en måde at bevæge sig baglæns så godt.

43
00:02:02,850 --> 00:02:04,960
>> Nu i enkelt-bundet
Listen video, vi talte

44
00:02:04,960 --> 00:02:07,210
om disse er fem af de
vigtigste ting, du skal være

45
00:02:07,210 --> 00:02:09,449
kan gøre for at arbejde med hægtede lister.

46
00:02:09,449 --> 00:02:12,880
Og for de fleste af disse er den omstændighed,
at det er en dobbelt-linked liste

47
00:02:12,880 --> 00:02:14,130
er egentlig ikke et stort spring.

48
00:02:14,130 --> 00:02:17,936
Vi kan stadig søge gennem ved blot
bevæger sig fremad fra start til slut.

49
00:02:17,936 --> 00:02:20,810
Vi kan stadig skabe et knudepunkt ud af
blå luft, temmelig meget på samme måde.

50
00:02:20,810 --> 00:02:23,591
Vi kan slette lister temmelig
meget på samme måde også.

51
00:02:23,591 --> 00:02:25,340
De eneste ting,
er subtilt anderledes,

52
00:02:25,340 --> 00:02:28,970
virkelig, indsætter
nye noder i listen,

53
00:02:28,970 --> 00:02:33,722
og vi vil endelig taler om sletning
et enkelt element fra listen samt.

54
00:02:33,722 --> 00:02:35,430
Igen, temmelig meget
de tre andre, men vi er

55
00:02:35,430 --> 00:02:37,888
ikke kommer til at tale om dem
lige nu, fordi de er bare

56
00:02:37,888 --> 00:02:43,920
meget mindre tweaks på de ideer, diskuteret
i enkelt-linkede liste video.

57
00:02:43,920 --> 00:02:46,292
>> Så lad os indsætte en ny knude
i en dobbelt-bundet listen.

58
00:02:46,292 --> 00:02:48,750
Vi talte om at gøre dette til
enkeltvis-linked lister så godt,

59
00:02:48,750 --> 00:02:52,020
men der er et par ekstra
fangster med dobbelt-hægtede lister.

60
00:02:52,020 --> 00:02:55,280
Vi er [? passerer?] i spidsen for
liste her og nogle arbitrær værdi,

61
00:02:55,280 --> 00:02:58,600
og vi ønsker at få den nye leder
af listen ud af denne funktion.

62
00:02:58,600 --> 00:03:01,414
Det er derfor, den returnerer en dllnode stjerne.

63
00:03:01,414 --> 00:03:02,330
Så hvad er de skridt?

64
00:03:02,330 --> 00:03:04,496
De er, igen, meget lignende
til enkeltvis forbundne lister

65
00:03:04,496 --> 00:03:05,670
med en ekstra tilsætning.

66
00:03:05,670 --> 00:03:08,900
Vi vil allokerer plads til en ny
node og kontrol for at sikre, at det er gyldigt.

67
00:03:08,900 --> 00:03:11,510
Vi ønsker at udfylde denne node op
med de oplysninger, vi

68
00:03:11,510 --> 00:03:12,564
ønsker at lægge i det.

69
00:03:12,564 --> 00:03:15,480
Det sidste, vi har brug for at do-- den
ekstra ting, vi skal gøre, rather--

70
00:03:15,480 --> 00:03:19,435
er at fastsætte den Forrige pointer
af den gamle leder af listen.

71
00:03:19,435 --> 00:03:21,310
Husk, at fordi
af dobbelt forbundne lister,

72
00:03:21,310 --> 00:03:23,110
vi kan komme videre
og backwards-- som

73
00:03:23,110 --> 00:03:27,080
betyder, at hvert knudepunkt faktisk peger
til to andre knudepunkter i stedet for kun én.

74
00:03:27,080 --> 00:03:29,110
Og så er vi nødt til at fastsætte
den gamle leder af listen

75
00:03:29,110 --> 00:03:32,151
til at pege bagud til den nye leder af
den linkede liste, hvilket var noget

76
00:03:32,151 --> 00:03:33,990
Vi behøvede ikke at gøre før.

77
00:03:33,990 --> 00:03:37,420
Og som før, vi bare returnere en
pointer til den nye leder af listen.

78
00:03:37,420 --> 00:03:38,220
>> Så her er en liste.

79
00:03:38,220 --> 00:03:40,144
Vi vil indsætte 12 ind i denne liste.

80
00:03:40,144 --> 00:03:42,060
Bemærk, at diagrammet
er lidt anderledes.

81
00:03:42,060 --> 00:03:47,710
Hvert knudepunkt indeholder tre fields--
data, og en næste pointer i rødt,

82
00:03:47,710 --> 00:03:50,170
og et Forrige pointer i blåt.

83
00:03:50,170 --> 00:03:54,059
Intet kommer før 15 node,
så dens Forrige pointer er null.

84
00:03:54,059 --> 00:03:55,350
Det er begyndelsen af ​​listen.

85
00:03:55,350 --> 00:03:56,560
Der er ikke noget, før det.

86
00:03:56,560 --> 00:04:03,350
Og intet kommer efter 10 node, og
så det er næste pointer er null så godt.

87
00:04:03,350 --> 00:04:05,616
>> Så lad os tilføje 12 til denne liste.

88
00:04:05,616 --> 00:04:08,070
Vi har brug for [uhørligt] plads til node.

89
00:04:08,070 --> 00:04:11,480
Vi sætter 12 inde i den.

90
00:04:11,480 --> 00:04:14,840
Og så igen, er vi nødt til at være virkelig
Pas på ikke at bryde kæden.

91
00:04:14,840 --> 00:04:17,144
Vi ønsker at omarrangere
pejlemærker i den rigtige rækkefølge.

92
00:04:17,144 --> 00:04:19,519
Og nogle gange, der kan mean--
som vi vil se særligt

93
00:04:19,519 --> 00:04:24,120
med delete-- at vi har nogle
redundante pegepinde, men det er OK.

94
00:04:24,120 --> 00:04:25,750
>> Så hvad gør vi ønsker at gøre først?

95
00:04:25,750 --> 00:04:28,290
Jeg vil anbefale
ting bør du sandsynligvis

96
00:04:28,290 --> 00:04:35,350
gøre er at udfylde pointerne af 12
node, før du rører nogen anden.

97
00:04:35,350 --> 00:04:38,640
Så hvad der 12 kommer til at pege på næste?

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

99
00:04:39,860 --> 00:04:42,430
Hvad kommer før 12?

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

101
00:04:43,640 --> 00:04:46,280
Nu har vi fyldt den
ekstra information i 12

102
00:04:46,280 --> 00:04:49,320
så det har Forrige, Næste, og værdi.

103
00:04:49,320 --> 00:04:53,505
>> Nu kan vi få 15-- denne ekstra
skridt vi talte om-- vi

104
00:04:53,505 --> 00:04:56,590
kan have 15 point tilbage til 12.

105
00:04:56,590 --> 00:04:59,634
Og nu kan vi flytte lederen af
den linkede liste også være 12.

106
00:04:59,634 --> 00:05:02,550
Så det er temmelig svarer til, hvad vi
gjorde med enkeltvis forbundne lister,

107
00:05:02,550 --> 00:05:06,940
bortset fra det ekstra trin af
forbinder den gamle leder af listen

108
00:05:06,940 --> 00:05:09,810
tilbage til den nye leder af listen.

109
00:05:09,810 --> 00:05:12,170
>> Lad os nu endelig slette
en knude fra en sammenkædet liste.

110
00:05:12,170 --> 00:05:14,350
Så lad os sige, vi har
en anden funktion,

111
00:05:14,350 --> 00:05:18,080
er at finde en node, vi ønsker at slette
og har givet os en pointer til præcis

112
00:05:18,080 --> 00:05:19,710
node, som vi ønsker at slette.

113
00:05:19,710 --> 00:05:22,360
Vi behøver ikke engang need-- sige det
hoved er stadig globalt erklæret.

114
00:05:22,360 --> 00:05:23,590
Vi har ikke brug hovedet her.

115
00:05:23,590 --> 00:05:26,830
Alt dette funktion gør, er at vi har
fundet en pointer til præcis knudepunktet vi

116
00:05:26,830 --> 00:05:28,090
ønsker at slippe af med.

117
00:05:28,090 --> 00:05:28,940
Lad os slippe af med det.

118
00:05:28,940 --> 00:05:31,859
Det er meget nemmere med
dobbelt-bundet lister.

119
00:05:31,859 --> 00:05:33,650
First-- det er faktisk
blot et par ting.

120
00:05:33,650 --> 00:05:38,760
Vi skal bare ordne det omgivende
knudepunkters pointers så de springe over

121
00:05:38,760 --> 00:05:40,240
node, vi ønsker at slette.

122
00:05:40,240 --> 00:05:43,484
Og så kan vi slette denne node.

123
00:05:43,484 --> 00:05:45,150
Så igen, vi bare går igennem her.

124
00:05:45,150 --> 00:05:49,625
Vi har tilsyneladende besluttet, at
vi ønsker at slette node X.

125
00:05:49,625 --> 00:05:51,500
Og igen, hvad jeg er
gør her-- ved way--

126
00:05:51,500 --> 00:05:54,580
er et generelt tilfældet for en
node, der er i midten.

127
00:05:54,580 --> 00:05:56,547
Der er et par af
ekstra advarsler, som du

128
00:05:56,547 --> 00:05:59,380
nødt til at overveje, når du sletter
begyndelsen af ​​listen

129
00:05:59,380 --> 00:06:01,040
eller meget slutningen af ​​listen.

130
00:06:01,040 --> 00:06:03,730
Der er et par særligt
corner tilfælde at behandle der.

131
00:06:03,730 --> 00:06:07,960
>> Så det virker for at slette enhver node
i midten af ​​list-- en,

132
00:06:07,960 --> 00:06:11,550
har en legitim pointer fremad
og en legitim pointer baglæns,

133
00:06:11,550 --> 00:06:14,460
legitim Forrige og Næste pointer.

134
00:06:14,460 --> 00:06:16,530
Igen, hvis du arbejder
med enderne, du

135
00:06:16,530 --> 00:06:18,500
nødt til at håndtere dem
lidt anderledes,

136
00:06:18,500 --> 00:06:19,570
og vi vil ikke
tale om det nu.

137
00:06:19,570 --> 00:06:21,319
Men du kan nok
regne ud, hvad der skal

138
00:06:21,319 --> 00:06:24,610
skal gøres lige ved at se denne video.

139
00:06:24,610 --> 00:06:28,910
>> Så vi har isoleret X. X er node
Vi ønsker at slette fra listen.

140
00:06:28,910 --> 00:06:30,140
Hvad gør vi?

141
00:06:30,140 --> 00:06:32,800
Først har vi brug for at omarrangere
de udvendige pointere.

142
00:06:32,800 --> 00:06:35,815
Vi er nødt til at omarrangere
9 næste at springe over 13

143
00:06:35,815 --> 00:06:38,030
og pege på 10-- hvilke
er det, vi lige har gjort.

144
00:06:38,030 --> 00:06:41,180
Og vi har også brug for
omarrangere 10 s Forrige

145
00:06:41,180 --> 00:06:44,610
at pege på 9 i stedet for at pege på 13.

146
00:06:44,610 --> 00:06:46,490
>> Så igen, var det
diagram til at begynde med.

147
00:06:46,490 --> 00:06:47,730
Dette var vores kæde.

148
00:06:47,730 --> 00:06:51,027
Vi er nødt til at springe over 13,
men vi skal også bevare

149
00:06:51,027 --> 00:06:52,110
integriteten af ​​listen.

150
00:06:52,110 --> 00:06:54,680
Vi ønsker ikke at miste nogen
information i begge retninger.

151
00:06:54,680 --> 00:06:59,620
Så vi er nødt til at omarrangere
pegepinde omhyggeligt

152
00:06:59,620 --> 00:07:02,240
så vi ikke bryder kæden overhovedet.

153
00:07:02,240 --> 00:07:05,710
>> Så vi kan sige 9 s næste pointer
peger på det samme sted

154
00:07:05,710 --> 00:07:08,040
at tretten Next
pointer peger lige nu.

155
00:07:08,040 --> 00:07:10,331
Fordi vi er i sidste ende
vil ønsker at springe over 13.

156
00:07:10,331 --> 00:07:13,750
Så uanset hvor 13 point næste, du
vil ni at pege der i stedet.

157
00:07:13,750 --> 00:07:15,200
Så det er det.

158
00:07:15,200 --> 00:07:20,370
Og så uanset hvor 13 point tilbage
til, hvad der kommer før den 13.,

159
00:07:20,370 --> 00:07:24,800
vi ønsker 10 til punkt
til at i stedet for 13.

160
00:07:24,800 --> 00:07:29,290
Bemærk nu, hvis du følger
pilene, kan vi slippe 13

161
00:07:29,290 --> 00:07:32,380
uden faktisk at miste nogen oplysninger.

162
00:07:32,380 --> 00:07:36,002
Vi har holdt integriteten af ​​listen,
flytte både fremad og bagud.

163
00:07:36,002 --> 00:07:38,210
Og så kan vi bare slags
af rense det en lille smule op

164
00:07:38,210 --> 00:07:40,930
ved at trække listen sammen.

165
00:07:40,930 --> 00:07:43,270
Så vi omarrangeres
pejlemærker på begge sider.

166
00:07:43,270 --> 00:07:46,231
Og så har vi befriet X den
node, der indeholdt 13,

167
00:07:46,231 --> 00:07:47,480
og vi ikke bryde kæden.

168
00:07:47,480 --> 00:07:50,980
Så vi gjorde det godt.

169
00:07:50,980 --> 00:07:53,000
>> Sidste bemærkning her på hægtede lister.

170
00:07:53,000 --> 00:07:55,990
Så både singly- og dobbelt-bundet
lister, som vi har set,

171
00:07:55,990 --> 00:07:58,959
støtte virkelig effektiv indsættelse
og sletning af elementer.

172
00:07:58,959 --> 00:08:00,750
Du kan stort set gøre
den i konstant tid.

173
00:08:00,750 --> 00:08:03,333
Hvad gjorde vi nødt til at gøre for at slette
et element blot et sekund siden?

174
00:08:03,333 --> 00:08:04,440
Vi flyttede en pointer.

175
00:08:04,440 --> 00:08:05,920
Vi flyttede en anden pointer.

176
00:08:05,920 --> 00:08:07,915
Vi befriede X-- tog tre operationer.

177
00:08:07,915 --> 00:08:14,500
Det tager altid tre operationer til
slette node-- at frigøre en node.

178
00:08:14,500 --> 00:08:15,280
>> Hvordan vi indsætter?

179
00:08:15,280 --> 00:08:17,280
Nå, men vi er bare altid
tacking på begyndelsen

180
00:08:17,280 --> 00:08:19,400
hvis vi indsætter effektivt.

181
00:08:19,400 --> 00:08:21,964
Så vi er nødt til at rearrange--
afhængigt af om det er

182
00:08:21,964 --> 00:08:24,380
en singly- eller dobbelt-bundet
liste, kan vi nødt til at gøre tre

183
00:08:24,380 --> 00:08:26,824
eller fire operationer max.

184
00:08:26,824 --> 00:08:28,365
Men igen, det er altid tre eller fire.

185
00:08:28,365 --> 00:08:30,531
Det er ligegyldigt, hvor mange
elementer er i vores liste,

186
00:08:30,531 --> 00:08:33,549
det er altid tre eller fire operations--
ligesom deletion er altid

187
00:08:33,549 --> 00:08:35,320
tre eller fire operationer.

188
00:08:35,320 --> 00:08:36,919
Det er konstant tid.

189
00:08:36,919 --> 00:08:38,169
Så det er virkelig stor.

190
00:08:38,169 --> 00:08:40,620
>> Med arrays, vi gør
noget indsættelse slags.

191
00:08:40,620 --> 00:08:44,739
Du husker formentlig, at indsættelse
sortering er ikke en konstant tid algoritme.

192
00:08:44,739 --> 00:08:46,030
Det er faktisk temmelig dyrt.

193
00:08:46,030 --> 00:08:48,840
Så dette er meget bedre til at indsætte.

194
00:08:48,840 --> 00:08:51,840
Men som jeg nævnte i
enkelt-sammenkædet liste video,

195
00:08:51,840 --> 00:08:54,030
vi har fået en ulempe også her, ikke?

196
00:08:54,030 --> 00:08:57,580
Vi har mistet evnen til at
tilfældigt adgang elementer.

197
00:08:57,580 --> 00:09:02,310
Vi kan ikke sige, jeg ønsker element nummer fire
eller element nummer 10 i en sammenkædet liste

198
00:09:02,310 --> 00:09:04,990
på samme måde, som vi kan
gøre det med et array

199
00:09:04,990 --> 00:09:08,630
eller vi kan bare direkte indeks
ind i vores arrayets element.

200
00:09:08,630 --> 00:09:10,930
>> Og så forsøge at finde en
element i en lænket list--

201
00:09:10,930 --> 00:09:15,880
hvis søgning er important--
kan nu tage lineær tid.

202
00:09:15,880 --> 00:09:18,330
Da listen bliver længere, det
kan tage et yderligere trin

203
00:09:18,330 --> 00:09:22,644
for hver enkelt element i listen i
for at finde, hvad vi leder efter.

204
00:09:22,644 --> 00:09:23,560
Så der er trade offs.

205
00:09:23,560 --> 00:09:25,780
Der er lidt af en pro
og con element her.

206
00:09:25,780 --> 00:09:29,110
>> Og dobbelt forbundne lister er ikke den
sidste slags datastruktur kombination

207
00:09:29,110 --> 00:09:32,840
at vi vil snakke om,
tager alle de grundlæggende bygning

208
00:09:32,840 --> 00:09:34,865
blokke af C en at sammensætte.

209
00:09:34,865 --> 00:09:37,900
Fordi i virkeligheden, kan vi
selv gøre det bedre end dette

210
00:09:37,900 --> 00:09:41,970
at skabe en datastruktur,
du måske være i stand til at søge gennem

211
00:09:41,970 --> 00:09:43,360
i konstant tid også.

212
00:09:43,360 --> 00:09:46,080
Men mere om det i en anden video.

213
00:09:46,080 --> 00:09:47,150
>> Jeg er Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Det er CS50.

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