1
00:00:00,000 --> 00:00:03,381
>> [Muziek]

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

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

4
00:00:05,520 --> 00:00:07,860
Dus als je net klaar met dat
video op enkelvoudig gelinkte lijsten spijt

5
00:00:07,860 --> 00:00:09,568
Ik liet je af op een
beetje een cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Maar ik ben blij dat je hier bent om te voltooien
het verhaal van de dubbel-gelinkte lijsten.

7
00:00:12,790 --> 00:00:15,250
>> Dus als je te herinneren van
die video, we praatten

8
00:00:15,250 --> 00:00:18,500
hoe enkelvoudig gebonden
takenlijsten wonen ons vermogen

9
00:00:18,500 --> 00:00:22,090
te behandelen informatie
waarbij het aantal elementen

10
00:00:22,090 --> 00:00:24,442
of het aantal items in
een lijst kan groeien of krimpen.

11
00:00:24,442 --> 00:00:26,400
We kunnen nu behandelen
iets dergelijks, waarbij

12
00:00:26,400 --> 00:00:28,310
We konden niet omgaan met arrays.

13
00:00:28,310 --> 00:00:30,560
>> Maar ze last hebben van een
kritieke beperking die

14
00:00:30,560 --> 00:00:33,790
is dat met een enkelvoudig verbonden
lijst, kunnen we alleen maar verplaatsen

15
00:00:33,790 --> 00:00:36,200
in één richting door de lijst.

16
00:00:36,200 --> 00:00:39,010
De enige situatie
wanneer dat een probleem kan worden

17
00:00:39,010 --> 00:00:41,250
was toen we probeerden te
verwijderen van een enkel element.

18
00:00:41,250 --> 00:00:46,000
En we hebben niet eens bespreken hoe dit te doen
in een enkelvoudig gelinkte lijst in pseudocode.

19
00:00:46,000 --> 00:00:48,797
Het is zeker goed te doen, maar
het kan een beetje een gedoe.

20
00:00:48,797 --> 00:00:50,630
Dus als je jezelf
in een situatie waarin

21
00:00:50,630 --> 00:00:53,175
je probeert te verwijderen
enkele elementen uit de lijst

22
00:00:53,175 --> 00:00:55,430
of het gaat om verplicht
dat u zult verwijderen

23
00:00:55,430 --> 00:00:57,970
enkele elementen uit
de lijst, wil je misschien

24
00:00:57,970 --> 00:01:02,090
te overwegen het gebruik van een dubbel-linked
lijst in plaats van een enkelvoudig gelinkte lijst.

25
00:01:02,090 --> 00:01:06,320
Omdat de dubbel-gelinkte lijsten toestaan
om voorwaarts en achterwaarts verplaatsen

26
00:01:06,320 --> 00:01:09,340
door de lijst in plaats van
alleen vooruit door de list--

27
00:01:09,340 --> 00:01:13,950
alleen door het toevoegen van een extra element
onze structuurdefinitie

28
00:01:13,950 --> 00:01:16,690
voor de dubbel-gelinkte lijst node.

29
00:01:16,690 --> 00:01:19,770
>> Nogmaals, als je niet van plan om
enkele elementen te verwijderen

30
00:01:19,770 --> 00:01:24,810
van de list-- omdat we voegen
een extra veld om onze structuur

31
00:01:24,810 --> 00:01:28,340
definition, de knopen zelf
voor dubbel-gelinkte lijsten

32
00:01:28,340 --> 00:01:29,550
zullen groter zijn.

33
00:01:29,550 --> 00:01:31,600
Ze gaan nemen
up meer bytes geheugen.

34
00:01:31,600 --> 00:01:34,160
En dus als dit is niet iets
je gaat moeten doen,

35
00:01:34,160 --> 00:01:36,300
je zou kunnen besluiten dat het
niet de moeite waard de handel korting

36
00:01:36,300 --> 00:01:39,360
te hebben om de extra te besteden
bytes van het geheugen vereist

37
00:01:39,360 --> 00:01:43,940
voor een dubbel-gelinkte lijst als je niet
zal worden te verwijderen losse elementen.

38
00:01:43,940 --> 00:01:46,760
Maar ze zijn ook cool
voor andere dingen ook.

39
00:01:46,760 --> 00:01:51,260
>> Dus zoals ik al zei, we moeten gewoon toe te voegen
een enkel veld in onze structuur

40
00:01:51,260 --> 00:01:55,360
definition-- dit begrip
van een Vorige pointer.

41
00:01:55,360 --> 00:01:58,620
Dus met een enkelvoudig gelinkte lijst, we
de waarde en de Next wijzer,

42
00:01:58,620 --> 00:02:02,850
zodat de dubbel-gelinkte lijst heeft net
een manier om terug te keren ook.

43
00:02:02,850 --> 00:02:04,960
>> Nu in het enkelvoudig gekoppelde
lijst video, we praatten

44
00:02:04,960 --> 00:02:07,210
over deze vijf van de
belangrijkste dingen die je moet

45
00:02:07,210 --> 00:02:09,449
kunnen doen om te werken met gekoppelde lijsten.

46
00:02:09,449 --> 00:02:12,880
En voor de meeste van deze, het feit
dat het een dubbel-gelinkte lijst

47
00:02:12,880 --> 00:02:14,130
is niet echt een grote sprong.

48
00:02:14,130 --> 00:02:17,936
We kunnen nog steeds door middel van zoeken op net
vooruit van begin tot eind.

49
00:02:17,936 --> 00:02:20,810
We kunnen nog steeds het creëren van een knooppunt uit
ijle lucht, vrijwel op dezelfde manier.

50
00:02:20,810 --> 00:02:23,591
We kunnen lijsten behoorlijk verwijderen
veel op dezelfde manier ook.

51
00:02:23,591 --> 00:02:25,340
De enige dingen die
zijn subtiele verschillen,

52
00:02:25,340 --> 00:02:28,970
echt, invoegt
nieuwe knooppunten in de lijst,

53
00:02:28,970 --> 00:02:33,722
en we zullen eindelijk praten over het verwijderen
een enkel element van de lijst ook.

54
00:02:33,722 --> 00:02:35,430
Nogmaals, vrij veel
de andere drie zijn we

55
00:02:35,430 --> 00:02:37,888
niet van plan om te praten over hen
nu omdat ze gewoon

56
00:02:37,888 --> 00:02:43,920
zeer kleine aanpassingen op de ideeën besproken
in het enkelvoudig gelinkte lijst video.

57
00:02:43,920 --> 00:02:46,292
>> Dus laten plaatst u een nieuw knooppunt
in een dubbel-gelinkte lijst.

58
00:02:46,292 --> 00:02:48,750
We spraken over dit voor het doen
enkelvoudig gelinkte lijsten als goed,

59
00:02:48,750 --> 00:02:52,020
maar er zijn een paar extra
vangt met dubbel-gelinkte lijsten.

60
00:02:52,020 --> 00:02:55,280
We zijn [? passeren?] in de kop van de
hier op te noemen en een aantal willekeurige waarde,

61
00:02:55,280 --> 00:02:58,600
en we willen het nieuwe hoofd krijgen
van de lijst van deze functie.

62
00:02:58,600 --> 00:03:01,414
Dat is waarom het geeft een dllnode ster.

63
00:03:01,414 --> 00:03:02,330
Dus wat zijn de stappen?

64
00:03:02,330 --> 00:03:04,496
Ze zijn weer vergelijkbaar
naar enkelvoudig-gekoppelde lijsten

65
00:03:04,496 --> 00:03:05,670
met een extra toevoeging.

66
00:03:05,670 --> 00:03:08,900
Wij willen ruimte toewijst voor een nieuwe
knooppunt en controleren om ervoor te zorgen dat het geldig is.

67
00:03:08,900 --> 00:03:11,510
We willen dat knooppunt vullen
met alle informatie die we

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

69
00:03:12,564 --> 00:03:15,480
Het laatste wat we moeten de doen--
extra wat we moeten doen, rather--

70
00:03:15,480 --> 00:03:19,435
is om de vorige pointer fix
van de oude kop van de lijst.

71
00:03:19,435 --> 00:03:21,310
Vergeet niet dat, omdat
van dubbel gelinkte lijsten,

72
00:03:21,310 --> 00:03:23,110
kunnen we vooruit
en backwards-- die

73
00:03:23,110 --> 00:03:27,080
betekent dat elk knooppunt in feite wijst
twee andere knooppunten in plaats van slechts één.

74
00:03:27,080 --> 00:03:29,110
En dus moeten we op te lossen
de oude kop van de lijst

75
00:03:29,110 --> 00:03:32,151
om terug te verwijzen naar het nieuwe hoofd van
de gelinkte lijst, waarin iets was

76
00:03:32,151 --> 00:03:33,990
we hoefden niet te doen voordat.

77
00:03:33,990 --> 00:03:37,420
En als voorheen, we gewoon terug een
Pointer naar het nieuwe hoofd van de lijst.

78
00:03:37,420 --> 00:03:38,220
>> Dus hier is een lijst.

79
00:03:38,220 --> 00:03:40,144
We willen invoegen 12 in deze lijst.

80
00:03:40,144 --> 00:03:42,060
Merk op dat het diagram
is iets anders.

81
00:03:42,060 --> 00:03:47,710
Elk knooppunt drie fields-- bevat
data, en de Next wijzer in het rood,

82
00:03:47,710 --> 00:03:50,170
en een Vorige pointer in blauw.

83
00:03:50,170 --> 00:03:54,059
Niets komt voor de 15-knooppunt,
zodat de vorige pointer nul.

84
00:03:54,059 --> 00:03:55,350
Het is het begin van de lijst.

85
00:03:55,350 --> 00:03:56,560
Er is niets voor het.

86
00:03:56,560 --> 00:04:03,350
En niets komt na de 10 knooppunt, en
dus het is Volgende pointer nul ook.

87
00:04:03,350 --> 00:04:05,616
>> Dus laten we toe 12 aan deze lijst.

88
00:04:05,616 --> 00:04:08,070
We moeten [onverstaanbaar] ruimte voor het knooppunt.

89
00:04:08,070 --> 00:04:11,480
We zetten 12 binnenkant van het.

90
00:04:11,480 --> 00:04:14,840
En nogmaals, we moeten echt
Pas op dat u de ketting te breken.

91
00:04:14,840 --> 00:04:17,144
We willen het herschikken
wijzers in de juiste volgorde.

92
00:04:17,144 --> 00:04:19,519
En soms is dat misschien mean--
zoals we in het bijzonder zullen zien

93
00:04:19,519 --> 00:04:24,120
met delete-- dat we hebben een aantal
redundant pointers, maar dat is OK.

94
00:04:24,120 --> 00:04:25,750
>> Dus wat willen we eerst doen?

95
00:04:25,750 --> 00:04:28,290
Ik zou aanraden het
Dingen die je moet waarschijnlijk

96
00:04:28,290 --> 00:04:35,350
doen zijn om de wijzers van de 12 te vullen
knooppunt voordat u aanraakt iemand anders.

97
00:04:35,350 --> 00:04:38,640
Dus wat is 12 gaan naar de volgende wijzen?

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

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

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

101
00:04:43,640 --> 00:04:46,280
Nu hebben we vulden de
extra informatie in 12

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

103
00:04:49,320 --> 00:04:53,505
>> Nu kunnen we 15-- dit extra
stap die we kregen about-- we praten

104
00:04:53,505 --> 00:04:56,590
kan 15 punt terug tot 12 hebben.

105
00:04:56,590 --> 00:04:59,634
En nu kunnen we het hoofd van bewegen
de gekoppelde lijst met eveneens 12.

106
00:04:59,634 --> 00:05:02,550
Dus het is vrij vergelijkbaar met wat we
deden met enkelvoudig gelinkte lijsten,

107
00:05:02,550 --> 00:05:06,940
met uitzondering van de extra stap van
het aansluiten van de oude kop van de lijst

108
00:05:06,940 --> 00:05:09,810
terug naar het nieuwe hoofd van de lijst.

109
00:05:09,810 --> 00:05:12,170
>> Laten we nu eens eindelijk verwijderen
een knooppunt van een gekoppelde lijst.

110
00:05:12,170 --> 00:05:14,350
Dus laten we zeggen dat we hebben
een andere functie die

111
00:05:14,350 --> 00:05:18,080
is het vinden van een knooppunt we willen verwijderen
en heeft ons een aanwijzing gegeven om precies te

112
00:05:18,080 --> 00:05:19,710
het knooppunt dat we willen verwijderen.

113
00:05:19,710 --> 00:05:22,360
We weten niet eens need-- zeggen dat de
hoofd is nog steeds wereldwijd verklaard.

114
00:05:22,360 --> 00:05:23,590
We hebben het hoofd hier niet nodig.

115
00:05:23,590 --> 00:05:26,830
Alle deze functie doet is we hebben
vond een pointer precies knooppunt we

116
00:05:26,830 --> 00:05:28,090
wil om zich te ontdoen van te krijgen.

117
00:05:28,090 --> 00:05:28,940
Laten we van af.

118
00:05:28,940 --> 00:05:31,859
Het is een stuk makkelijker met
dubbel-gelinkte lijsten.

119
00:05:31,859 --> 00:05:33,650
First-- het is eigenlijk
slechts een paar dingen.

120
00:05:33,650 --> 00:05:38,760
We hoeven alleen maar te bevestigen de omringende
pointers nodes ', zodat ze over te slaan

121
00:05:38,760 --> 00:05:40,240
het knooppunt we willen verwijderen.

122
00:05:40,240 --> 00:05:43,484
En dan kunnen we dat knooppunt te verwijderen.

123
00:05:43,484 --> 00:05:45,150
Dus nogmaals, we gewoon door hier.

124
00:05:45,150 --> 00:05:49,625
We hebben blijkbaar besloten
we willen het knooppunt X. schrappen

125
00:05:49,625 --> 00:05:51,500
En nogmaals, wat ik ben
doet hier-- door de way--

126
00:05:51,500 --> 00:05:54,580
is een algemeen geval voor een
knooppunt, dat is in het midden.

127
00:05:54,580 --> 00:05:56,547
Er zijn een paar van
extra waarschuwingen dat u

128
00:05:56,547 --> 00:05:59,380
moet overwegen wanneer u het verwijderen
het begin van de lijst

129
00:05:59,380 --> 00:06:01,040
of het einde van de lijst.

130
00:06:01,040 --> 00:06:03,730
Er zijn een paar van de speciale
grensgevallen te behandelen zijn.

131
00:06:03,730 --> 00:06:07,960
>> Dus dit werkt voor het verwijderen van elk knooppunt
in het midden van de list-- die

132
00:06:07,960 --> 00:06:11,550
heeft een legitieme pointer vooruit
en een legitieme wijzer achteruit,

133
00:06:11,550 --> 00:06:14,460
legitieme vorige en volgende pointer.

134
00:06:14,460 --> 00:06:16,530
Nogmaals, als je werkt
met de uiteinden, u

135
00:06:16,530 --> 00:06:18,500
moeten die verwerken
iets anders,

136
00:06:18,500 --> 00:06:19,570
en we zijn niet van plan om
over praten nu.

137
00:06:19,570 --> 00:06:21,319
Maar je kan waarschijnlijk
erachter te komen wat er moet

138
00:06:21,319 --> 00:06:24,610
gewoon gedaan worden door te kijken naar deze video.

139
00:06:24,610 --> 00:06:28,910
>> Dus we hebben geïsoleerd X. X is het knooppunt
we willen verwijderen uit de lijst.

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

141
00:06:30,140 --> 00:06:32,800
Eerst moeten we te herschikken
buiten pointers.

142
00:06:32,800 --> 00:06:35,815
We moeten herschikken
9's volgende over te slaan 13

143
00:06:35,815 --> 00:06:38,030
en wijzen op 10-- die
is wat we net hebben gedaan.

144
00:06:38,030 --> 00:06:41,180
En we moeten ook
herschikken 10's Vorige

145
00:06:41,180 --> 00:06:44,610
te wijzen op 9 in plaats van naar een 13.

146
00:06:44,610 --> 00:06:46,490
>> Dus nogmaals, dit was de
diagram te beginnen.

147
00:06:46,490 --> 00:06:47,730
Dit was onze keten.

148
00:06:47,730 --> 00:06:51,027
We moeten overslaan 13,
maar we moeten ook behouden

149
00:06:51,027 --> 00:06:52,110
de integriteit van de lijst.

150
00:06:52,110 --> 00:06:54,680
We willen niet elke verliezen
informatie in beide richtingen.

151
00:06:54,680 --> 00:06:59,620
Dus moeten we herschikken
de wijzers zorgvuldig

152
00:06:59,620 --> 00:07:02,240
zodat we niet de ketting breekt helemaal.

153
00:07:02,240 --> 00:07:05,710
>> Dus we kunnen 9's Next wijzer zeggen
naar dezelfde plaats

154
00:07:05,710 --> 00:07:08,040
dat dertien's Next
pointer wijst nu.

155
00:07:08,040 --> 00:07:10,331
Omdat we uiteindelijk
gaat te willen overslaan 13.

156
00:07:10,331 --> 00:07:13,750
Dus waar 13 punten naast u
wil negen wijzen er in plaats.

157
00:07:13,750 --> 00:07:15,200
Dus dat is dat.

158
00:07:15,200 --> 00:07:20,370
En dan waar 13 punten terug
aan, wat komt vóór 13,

159
00:07:20,370 --> 00:07:24,800
we willen 10 wijzen
dat in plaats van 13.

160
00:07:24,800 --> 00:07:29,290
Nu merken, als je de volgende
de pijlen, kunnen we laten vallen 13

161
00:07:29,290 --> 00:07:32,380
zonder enige informatie daadwerkelijk te verliezen.

162
00:07:32,380 --> 00:07:36,002
We hebben de integriteit van de lijst gehouden,
bewegen zowel vooruit als achteruit.

163
00:07:36,002 --> 00:07:38,210
En dan kunnen we gewoon soort
van opruimen een beetje

164
00:07:38,210 --> 00:07:40,930
door samen te trekken van de lijst.

165
00:07:40,930 --> 00:07:43,270
Dus we herschikt de
wijzers aan beide zijden.

166
00:07:43,270 --> 00:07:46,231
En dan hebben we bevrijd van de X
knooppunt 13 bevatte,

167
00:07:46,231 --> 00:07:47,480
en we niet breken de keten.

168
00:07:47,480 --> 00:07:50,980
Dus hebben we goed.

169
00:07:50,980 --> 00:07:53,000
>> Laatste opmerking hier op gelinkte lijsten.

170
00:07:53,000 --> 00:07:55,990
Dus zowel singly- en dubbel-linked
lijsten, zoals we hebben gezien,

171
00:07:55,990 --> 00:07:58,959
ondersteuning echt efficiënt inbrengen
en verwijderen van elementen.

172
00:07:58,959 --> 00:08:00,750
U kunt vrij veel doen
in constante tijd.

173
00:08:00,750 --> 00:08:03,333
Wat hebben we moeten doen om te verwijderen
een element slechts een seconde geleden?

174
00:08:03,333 --> 00:08:04,440
Verhuisden we een pointer.

175
00:08:04,440 --> 00:08:05,920
We verhuisden een andere pointer.

176
00:08:05,920 --> 00:08:07,915
We bevrijd x-- duurde drie operaties.

177
00:08:07,915 --> 00:08:14,500
Het duurt altijd drie operaties aan
dat node-- verwijderen om een ​​knoop te bevrijden.

178
00:08:14,500 --> 00:08:15,280
>> Hoe kunnen we voegen?

179
00:08:15,280 --> 00:08:17,280
Nou, we zijn gewoon altijd
hechten aan het begin

180
00:08:17,280 --> 00:08:19,400
als we efficiënt inbrengen.

181
00:08:19,400 --> 00:08:21,964
Dus moeten we rearrange--
afhankelijk van of het

182
00:08:21,964 --> 00:08:24,380
een singly- of dubbel-linked
lijst, zouden we moeten doen drie

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

184
00:08:26,824 --> 00:08:28,365
Maar nogmaals, het is altijd drie of vier.

185
00:08:28,365 --> 00:08:30,531
Het maakt niet uit hoeveel
elementen zijn in onze lijst,

186
00:08:30,531 --> 00:08:33,549
het is altijd drie of vier operations--
net zoals verwijdering is altijd

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

188
00:08:35,320 --> 00:08:36,919
Het is een constante tijd.

189
00:08:36,919 --> 00:08:38,169
Dus dat is echt geweldig.

190
00:08:38,169 --> 00:08:40,620
>> Met arrays, we deden
zoiets als insertion sort.

191
00:08:40,620 --> 00:08:44,739
Herinnert u zich waarschijnlijk dat het inbrengen
sorteren is geen constante tijd algoritme.

192
00:08:44,739 --> 00:08:46,030
Het is eigenlijk vrij duur.

193
00:08:46,030 --> 00:08:48,840
Dus dit is veel beter voor invoegen.

194
00:08:48,840 --> 00:08:51,840
Maar zoals ik in de genoemde
enkelvoudig gelinkte lijst video,

195
00:08:51,840 --> 00:08:54,030
we hebben ook een keerzijde hebben hier ook, toch?

196
00:08:54,030 --> 00:08:57,580
We hebben de mogelijkheid om verloren
willekeurige toegang elementen.

197
00:08:57,580 --> 00:09:02,310
We kunnen niet zeggen, ik wil element nummer vier
of element nummer 10 van een gekoppelde lijst

198
00:09:02,310 --> 00:09:04,990
Net zoals we kunnen
die met een array

199
00:09:04,990 --> 00:09:08,630
of we kunnen gewoon rechtstreeks index
element in ons aanbod is.

200
00:09:08,630 --> 00:09:10,930
>> En zo proberen om een ​​te vinden
element in een gekoppelde list--

201
00:09:10,930 --> 00:09:15,880
Als zoeken is important--
kan nu nemen lineaire tijd.

202
00:09:15,880 --> 00:09:18,330
Aangezien de lijst wordt langer het
misschien een extra stap te zetten

203
00:09:18,330 --> 00:09:22,644
voor elk element in de lijst
Om te vinden wat we zoeken.

204
00:09:22,644 --> 00:09:23,560
Dus er is de handel offs.

205
00:09:23,560 --> 00:09:25,780
Er is een beetje een pro
en con element hier.

206
00:09:25,780 --> 00:09:29,110
>> En dubbel-gelinkte lijsten zijn niet de
laatste soort gegevens structuur combinatie

207
00:09:29,110 --> 00:09:32,840
dat we praten over,
het nemen van alle fundamentele gebouw

208
00:09:32,840 --> 00:09:34,865
blokken van C een samenstellen.

209
00:09:34,865 --> 00:09:37,900
Want in feite, kunnen we
zelfs beter dan dit

210
00:09:37,900 --> 00:09:41,970
een data structuur te creëren dat
je zou in staat zijn om door middel van

211
00:09:41,970 --> 00:09:43,360
in constante tijd ook.

212
00:09:43,360 --> 00:09:46,080
Maar meer daarover in een andere video.

213
00:09:46,080 --> 00:09:47,150
>> Ik ben Doug Lloyd.

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

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