1
00:00:00,000 --> 00:00:03,381
>> [MUSIC SPILLE]

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

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

4
00:00:05,520 --> 00:00:07,860
Så hvis du nettopp ferdig som
video på enkeltvis-lenkede lister beklager

5
00:00:07,860 --> 00:00:09,568
Jeg forlot deg av på en
litt av en cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Men jeg er glad for at du er her for å fullføre
historien om dobbelt-lenkede lister.

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

8
00:00:15,250 --> 00:00:18,500
om hvordan enkeltvis bundet
lister gjør delta på vår evne

9
00:00:18,500 --> 00:00:22,090
å forholde seg til informasjon
hvor antallet elementer

10
00:00:22,090 --> 00:00:24,442
eller antall elementer i
en liste kan vokse eller krympe.

11
00:00:24,442 --> 00:00:26,400
Vi kan nå håndtere
noe sånt, der

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

13
00:00:28,310 --> 00:00:30,560
>> Men de har lider av én
kritisk begrensning som

14
00:00:30,560 --> 00:00:33,790
er det med en enkeltvis bundet
listen, kan vi bare noensinne flytte

15
00:00:33,790 --> 00:00:36,200
i én retning gjennom listen.

16
00:00:36,200 --> 00:00:39,010
Og den eneste virkelige situasjonen
hvor det kan bli et problem

17
00:00:39,010 --> 00:00:41,250
var da vi prøvde å
slette en enkelt element.

18
00:00:41,250 --> 00:00:46,000
Og vi hadde ikke engang diskutere hvordan vi skal gjøre det
i en enkeltvis-lenket liste i pseudokode.

19
00:00:46,000 --> 00:00:48,797
Det er absolutt gjennomførbart, men
det kan være litt av en problemfri.

20
00:00:48,797 --> 00:00:50,630
Så hvis du finner deg selv
i en situasjon der

21
00:00:50,630 --> 00:00:53,175
du prøver å slette
enkeltelementer fra listen

22
00:00:53,175 --> 00:00:55,430
eller det kommer til å være nødvendig
at du skal slette

23
00:00:55,430 --> 00:00:57,970
enkeltelementer fra
listen, kan det være lurt

24
00:00:57,970 --> 00:01:02,090
vurdere å bruke en dobbelt-linked
liste i stedet for en enkeltvis-lenket liste.

25
00:01:02,090 --> 00:01:06,320
Fordi dobbelt-lenkede lister tillate deg
å flytte både forover og bakover

26
00:01:06,320 --> 00:01:09,340
gjennom listen i stedet for
bare frem gjennom list--

27
00:01:09,340 --> 00:01:13,950
bare ved å legge en ekstra element
til vår struktur definisjon

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

29
00:01:16,690 --> 00:01:19,770
>> Igjen, hvis du ikke kommer til å
være å slette enkeltelementer

30
00:01:19,770 --> 00:01:24,810
fra list-- fordi vi legger
et ekstra felt til vår struktur

31
00:01:24,810 --> 00:01:28,340
definisjon, nodene selv
for dobbelt-lenkede lister

32
00:01:28,340 --> 00:01:29,550
kommer til å bli større.

33
00:01:29,550 --> 00:01:31,600
De kommer til å ta
opp flere byte med minne.

34
00:01:31,600 --> 00:01:34,160
Og så hvis dette ikke er noe
du kommer til å trenge å gjøre,

35
00:01:34,160 --> 00:01:36,300
du kan bestemme det er
ikke verdt trade off

36
00:01:36,300 --> 00:01:39,360
å måtte bruke ekstra
byte minne kreves

37
00:01:39,360 --> 00:01:43,940
for en dobbelt-lenket liste hvis du ikke er
kommer til å være å slette enkeltelementer.

38
00:01:43,940 --> 00:01:46,760
Men de er også kult
for andre ting også.

39
00:01:46,760 --> 00:01:51,260
>> Så som jeg sa, vi må bare legge til
én enkelt felt i vår struktur

40
00:01:51,260 --> 00:01:55,360
definition-- denne oppfatningen
av en tidligere pekeren.

41
00:01:55,360 --> 00:01:58,620
Så med en enkeltvis-lenket liste, vi
har verdien og Neste pekeren,

42
00:01:58,620 --> 00:02:02,850
så dobbelt-lenket liste bare har
en måte å bevege seg bakover også.

43
00:02:02,850 --> 00:02:04,960
>> Nå i det enkeltvis bundet
liste video, vi snakket

44
00:02:04,960 --> 00:02:07,210
om disse er fem av
viktigste tingene du trenger å være

45
00:02:07,210 --> 00:02:09,449
i stand til å gjøre for å jobbe med koblede lister.

46
00:02:09,449 --> 00:02:12,880
Og for de fleste av disse, det faktum
at det er en dobbelt-lenket liste

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

48
00:02:14,130 --> 00:02:17,936
Vi kan fortsatt søke gjennom etter bare
fremover fra start til slutt.

49
00:02:17,936 --> 00:02:20,810
Vi kan fortsatt lage en node ut av
tynn luft, ganske mye på samme måte.

50
00:02:20,810 --> 00:02:23,591
Vi kan slette lister pen
mye på samme måte også.

51
00:02:23,591 --> 00:02:25,340
De eneste tingene som
er litt forskjellig,

52
00:02:25,340 --> 00:02:28,970
egentlig, setter inn
nye noder i listen,

53
00:02:28,970 --> 00:02:33,722
og vi vil endelig snakke om sletting
ett element fra listen også.

54
00:02:33,722 --> 00:02:35,430
Igjen, ganske mye
de tre andre, vi er

55
00:02:35,430 --> 00:02:37,888
ikke kommer til å snakke om dem
akkurat nå, fordi de er bare

56
00:02:37,888 --> 00:02:43,920
meget mindre tilpasninger på de ideer diskutert
i enkeltvis-lenket liste video.

57
00:02:43,920 --> 00:02:46,292
>> Så la oss sette inn en ny node
inn i en dobbelt-lenket liste.

58
00:02:46,292 --> 00:02:48,750
Vi snakket om å gjøre dette for
enkeltvis bundet lister også,

59
00:02:48,750 --> 00:02:52,020
men det er et par ekstra
fanger med dobbelt-lenkede lister.

60
00:02:52,020 --> 00:02:55,280
Vi er [? passerer?] i hodet av
liste her og litt vilkårlig verdi,

61
00:02:55,280 --> 00:02:58,600
og vi ønsker å få den nye sjefen
av listen ut av denne funksjonen.

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

63
00:03:01,414 --> 00:03:02,330
Så hva er fremgangsmåten?

64
00:03:02,330 --> 00:03:04,496
De er, igjen, svært lik
til enkeltvis bundet lister

65
00:03:04,496 --> 00:03:05,670
med en ekstra tillegg.

66
00:03:05,670 --> 00:03:08,900
Vi ønsker å tildeler plass for en ny
node og sjekk for å sikre at det er gyldig.

67
00:03:08,900 --> 00:03:11,510
Vi ønsker å fylle det node opp
med den informasjonen vi

68
00:03:11,510 --> 00:03:12,564
ønsker å legge i det.

69
00:03:12,564 --> 00:03:15,480
Det siste vi trenger å do-- den
ekstra ting vi trenger å gjøre, rather--

70
00:03:15,480 --> 00:03:19,435
er å fikse Forrige pekeren
av den gamle hodet av listen.

71
00:03:19,435 --> 00:03:21,310
Husk at på grunn
av dobbelt-lenkede lister,

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

73
00:03:23,110 --> 00:03:27,080
betyr at hver node faktisk peker
til to andre noder i stedet for bare én.

74
00:03:27,080 --> 00:03:29,110
Og så må vi fikse
den gamle hodet av listen

75
00:03:29,110 --> 00:03:32,151
å peke bakover til den nye sjefen for
den lenket liste, som var noe

76
00:03:32,151 --> 00:03:33,990
vi trengte ikke å gjøre før.

77
00:03:33,990 --> 00:03:37,420
Og som før, vi bare returnere en
Peker til ny leder av 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 ønsker å sette 12 inn i denne listen.

80
00:03:40,144 --> 00:03:42,060
Legg merke til at diagrammet
er litt annerledes.

81
00:03:42,060 --> 00:03:47,710
Hver node inneholder tre fields--
data, og en Neste peker i rødt,

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

83
00:03:50,170 --> 00:03:54,059
Ingenting kommer før 15 node,
så sin Forrige pekeren er null.

84
00:03:54,059 --> 00:03:55,350
Det er begynnelsen av listen.

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

86
00:03:56,560 --> 00:04:03,350
Og ingenting kommer etter 10 node, og
så det er Neste pekeren er null også.

87
00:04:03,350 --> 00:04:05,616
>> Så la oss legge 12 til denne listen.

88
00:04:05,616 --> 00:04:08,070
Vi trenger [uhørbart] plass til noden.

89
00:04:08,070 --> 00:04:11,480
Vi satt 12 på innsiden av det.

90
00:04:11,480 --> 00:04:14,840
Og så igjen, må vi være veldig
Pass på å ikke bryte kjeden.

91
00:04:14,840 --> 00:04:17,144
Vi ønsker å omorganisere
pekere i riktig rekkefølge.

92
00:04:17,144 --> 00:04:19,519
Og noen ganger at kanskje mean--
som vi skal se spesielt

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

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

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

96
00:04:28,290 --> 00:04:35,350
gjøre er å fylle pekere til 12
node før du berører noen andre.

97
00:04:35,350 --> 00:04:38,640
Så hva er 12 kommer til å peke på neste?

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

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

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

101
00:04:43,640 --> 00:04:46,280
Nå har vi fylt
ekstra informasjon i 12

102
00:04:46,280 --> 00:04:49,320
så det har Forrige, Neste, og verdi.

103
00:04:49,320 --> 00:04:53,505
>> Nå kan vi ha 15-- denne ekstra
skrittet vi snakket om-- vi

104
00:04:53,505 --> 00:04:56,590
kan ha 15 poeng tilbake til 12.

105
00:04:56,590 --> 00:04:59,634
Og nå kan vi bevege hodet
den lenket liste til også å være 12.

106
00:04:59,634 --> 00:05:02,550
Så det er ganske likt det vi
gjorde med enkeltvis-lenkede lister,

107
00:05:02,550 --> 00:05:06,940
med unntak for det ekstra trinnet
koble den gamle hodet av listen

108
00:05:06,940 --> 00:05:09,810
tilbake til ny leder av listen.

109
00:05:09,810 --> 00:05:12,170
>> La oss nå endelig slette
en node fra en lenket liste.

110
00:05:12,170 --> 00:05:14,350
Så la oss si at vi har
noen annen funksjon som

111
00:05:14,350 --> 00:05:18,080
er å finne en node vi ønsker å slette
og har gitt oss en peker til nøyaktig

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

113
00:05:19,710 --> 00:05:22,360
Vi trenger ikke engang need-- si
Hodet er fremdeles globalt erklært.

114
00:05:22,360 --> 00:05:23,590
Vi trenger ikke hodet her.

115
00:05:23,590 --> 00:05:26,830
All denne funksjonen gjør er vi har
funnet en peker til nøyaktig noden vi

116
00:05:26,830 --> 00:05:28,090
ønsker å bli kvitt.

117
00:05:28,090 --> 00:05:28,940
La oss bli kvitt det.

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

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

120
00:05:33,650 --> 00:05:38,760
Vi trenger bare å fikse det omliggende
noder 'pekere slik at de hoppe over

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

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

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

124
00:05:45,150 --> 00:05:49,625
Vi har tydeligvis bestemt seg for at
vi vil slette noden X.

125
00:05:49,625 --> 00:05:51,500
Og igjen, hva jeg er
gjør her-- av måte--

126
00:05:51,500 --> 00:05:54,580
er en generell sak for en
node som er i midten.

127
00:05:54,580 --> 00:05:56,547
Det er et par av
ekstra begrensninger som du

128
00:05:56,547 --> 00:05:59,380
må vurdere når du sletter
Helt i begynnelsen av listen

129
00:05:59,380 --> 00:06:01,040
eller helt på slutten av listen.

130
00:06:01,040 --> 00:06:03,730
Det er et par spesielle
hjørne saker å forholde seg til det.

131
00:06:03,730 --> 00:06:07,960
>> Så dette fungerer for å slette noen node
i midten av den ene som list--

132
00:06:07,960 --> 00:06:11,550
har en legitim peker fremover
og en legitim peker bakover,

133
00:06:11,550 --> 00:06:14,460
legitim Forrige og Neste pekeren.

134
00:06:14,460 --> 00:06:16,530
Igjen, hvis du jobber
med endene, du

135
00:06:16,530 --> 00:06:18,500
trenger for å håndtere de
litt annerledes,

136
00:06:18,500 --> 00:06:19,570
og vi ikke kommer til å
snakke om det nå.

137
00:06:19,570 --> 00:06:21,319
Men du kan sannsynligvis
finne ut hva som må

138
00:06:21,319 --> 00:06:24,610
gjøres bare ved å se denne videoen.

139
00:06:24,610 --> 00:06:28,910
>> Så vi har isolert X. X er node
vi vil slette fra listen.

140
00:06:28,910 --> 00:06:30,140
Hva skal vi gjøre?

141
00:06:30,140 --> 00:06:32,800
Først må vi omorganisere
utsiden pekere.

142
00:06:32,800 --> 00:06:35,815
Vi trenger å omorganisere
9 neste å hoppe over 13

143
00:06:35,815 --> 00:06:38,030
og peker på 10-- som
er det vi nettopp har gjort.

144
00:06:38,030 --> 00:06:41,180
Og vi må også
omorganisere 10s Forrige

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

146
00:06:44,610 --> 00:06:46,490
>> Så igjen, dette var den
diagram til å begynne med.

147
00:06:46,490 --> 00:06:47,730
Dette var vår kjede.

148
00:06:47,730 --> 00:06:51,027
Vi trenger å hoppe over 13,
men vi må også bevare

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

150
00:06:52,110 --> 00:06:54,680
Vi ønsker ikke å miste noen
Informasjonen i begge retninger.

151
00:06:54,680 --> 00:06:59,620
Så vi trenger å omorganisere
pekere nøye

152
00:06:59,620 --> 00:07:02,240
slik at vi ikke bryte kjeden i det hele tatt.

153
00:07:02,240 --> 00:07:05,710
>> Så vi kan si 9 Next pekeren
peker til samme sted

154
00:07:05,710 --> 00:07:08,040
at tretten Next
pekeren peker akkurat nå.

155
00:07:08,040 --> 00:07:10,331
Fordi vi er slutt
skal du ønsker å hoppe over 13.

156
00:07:10,331 --> 00:07:13,750
Så uansett hvor 13 poeng neste, du
Vil ni til punkt 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å uansett hvor 13 poeng tilbake
til, det som kommer før 13,

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

160
00:07:24,800 --> 00:07:29,290
Nå legger merke til, hvis du følger
pilene, kan vi slippe 13

161
00:07:29,290 --> 00:07:32,380
uten egentlig å miste informasjon.

162
00:07:32,380 --> 00:07:36,002
Vi har holdt integriteten av listen,
flytting både forover og bakover.

163
00:07:36,002 --> 00:07:38,210
Og så kan vi bare liksom
av rydde opp litt

164
00:07:38,210 --> 00:07:40,930
ved å trekke listen sammen.

165
00:07:40,930 --> 00:07:43,270
Så vi omorganisert
pekere på hver side.

166
00:07:43,270 --> 00:07:46,231
Og da er vi frigjort X den
node som inneholdt 13,

167
00:07:46,231 --> 00:07:47,480
og vi ikke bryte kjeden.

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

169
00:07:50,980 --> 00:07:53,000
>> Endelig notat her på lenkede lister.

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

171
00:07:55,990 --> 00:07:58,959
support virkelig effektiv innsetting
og sletting av elementer.

172
00:07:58,959 --> 00:08:00,750
Du kan stort sett gjøre
det i konstant tid.

173
00:08:00,750 --> 00:08:03,333
Hva gjorde vi må gjøre for å slette
et element bare et sekund siden?

174
00:08:03,333 --> 00:08:04,440
Vi flyttet én pekeren.

175
00:08:04,440 --> 00:08:05,920
Vi flyttet en annen pekeren.

176
00:08:05,920 --> 00:08:07,915
Vi frigjort X- tok tre operasjoner.

177
00:08:07,915 --> 00:08:14,500
Det tar alltid tre operasjoner til
slett at node-- å frigjøre en node.

178
00:08:14,500 --> 00:08:15,280
>> Hvordan setter vi?

179
00:08:15,280 --> 00:08:17,280
Vel, vi er bare alltid
vinne på begynnelsen

180
00:08:17,280 --> 00:08:19,400
hvis vi setter effektivt.

181
00:08:19,400 --> 00:08:21,964
Så vi må rearrange--
avhengig av om det er

182
00:08:21,964 --> 00:08:24,380
en singly- eller dobbelt bundet
liste, kanskje vi trenger å gjøre tre

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

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

185
00:08:28,365 --> 00:08:30,531
Det spiller ingen rolle hvor mange
elementene er på vår liste,

186
00:08:30,531 --> 00:08:33,549
det er alltid tre eller fire operations--
akkurat som sletting er alltid

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

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 flott.

190
00:08:38,169 --> 00:08:40,620
>> Med arrays, ble vi gjør
noe som innsetting sort.

191
00:08:40,620 --> 00:08:44,739
Du husker sikkert at innsetting
sorter er ikke en konstant tid algoritme.

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

193
00:08:46,030 --> 00:08:48,840
Så dette er mye bedre for å sette inn.

194
00:08:48,840 --> 00:08:51,840
Men som jeg nevnte i
enkeltvis-lenket liste video,

195
00:08:51,840 --> 00:08:54,030
vi har en ulemper her også, ikke sant?

196
00:08:54,030 --> 00:08:57,580
Vi har mistet evnen til å
tilfeldig tilgang elementer.

197
00:08:57,580 --> 00:09:02,310
Vi kan ikke si, jeg ønsker element nummer fire
eller element nummer 10 av en lenket liste

198
00:09:02,310 --> 00:09:04,990
På samme måte som vi kan
gjøre det med en rekke

199
00:09:04,990 --> 00:09:08,630
Eller vi kan bare direkte index
inn i vårt utvalg er element.

200
00:09:08,630 --> 00:09:10,930
>> Og så prøver å finne en
element i en koblet list--

201
00:09:10,930 --> 00:09:15,880
dersom søker er important--
kan nå ta lineær tid.

202
00:09:15,880 --> 00:09:18,330
Som listen blir lengre, det
kan ta ett ekstra trinn

203
00:09:18,330 --> 00:09:22,644
for hvert enkelt element i listen i
For å finne det vi leter etter.

204
00:09:22,644 --> 00:09:23,560
Så det er avveininger.

205
00:09:23,560 --> 00:09:25,780
Det er litt av en pro
og con element her.

206
00:09:25,780 --> 00:09:29,110
>> Og dobbelt-lenkede lister er ikke den
siste slags datastruktur kombinasjon

207
00:09:29,110 --> 00:09:32,840
at vi skal snakke om,
tar alle de grunnleggende bygge

208
00:09:32,840 --> 00:09:34,865
blokker av C en sette sammen.

209
00:09:34,865 --> 00:09:37,900
Fordi faktisk, kan vi
gjøre det enda bedre enn dette

210
00:09:37,900 --> 00:09:41,970
for å opprette en datastruktur som
du kan være i stand til å søke gjennom

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

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

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

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

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