1
00:00:00,000 --> 00:00:02,832
>> [Muziek]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, dus bij
dit punt in de loop,

4
00:00:08,560 --> 00:00:15,300
we hebben veel van de basisprincipes van C. gedekt
We weten veel over variabelen, arrays,

5
00:00:15,300 --> 00:00:17,610
pointers, dat alles goed spul.

6
00:00:17,610 --> 00:00:21,610
Die zijn allemaal een soort van ingebouwde
in te zien als de fundamenten,

7
00:00:21,610 --> 00:00:23,880
maar we kunnen meer recht doen?

8
00:00:23,880 --> 00:00:27,930
We kunnen dingen combineren
samen in interessante manieren.

9
00:00:27,930 --> 00:00:31,010
>> En zo laten we dat doen, laten we beginnen
vertakken van wat C geeft ons,

10
00:00:31,010 --> 00:00:35,270
en start van onze eigen gegevens creëren
structuren met behulp van deze gebouw

11
00:00:35,270 --> 00:00:40,590
blokken samen om iets te doen
echt waardevol, nuttig.

12
00:00:40,590 --> 00:00:43,420
Een manier kunnen we dit te doen is
om te praten over collecties.

13
00:00:43,420 --> 00:00:48,360
Tot nu toe hebben we een soort van data had
structuur voor het weergeven verzamelingen

14
00:00:48,360 --> 00:00:51,030
houd van waarden, dezelfde waarden.

15
00:00:51,030 --> 00:00:52,350
Dat zou een array zijn.

16
00:00:52,350 --> 00:00:57,020
We hebben collecties van gehele getallen, of
verzamelingen van figuren enzovoort.

17
00:00:57,020 --> 00:01:00,890
>> Structuren zijn ook een soort van data
structuur voor het verzamelen van informatie,

18
00:01:00,890 --> 00:01:03,220
maar het is niet voor het verzamelen van dergelijke waarden.

19
00:01:03,220 --> 00:01:08,090
Het combineert meestal verschillende datatypes
samen in één enkele box.

20
00:01:08,090 --> 00:01:10,750
Maar het is niet zelf
gebruikt chain elkaar

21
00:01:10,750 --> 00:01:16,920
of met elkaar te verbinden soortgelijke
items, zoals een array.

22
00:01:16,920 --> 00:01:20,960
Arrays zijn zeer geschikt voor
element opzoeken, maar recall

23
00:01:20,960 --> 00:01:24,262
dat het zeer moeilijk
te voegen in een array,

24
00:01:24,262 --> 00:01:26,470
tenzij we het invoegen op
het einde van de matrix.

25
00:01:26,470 --> 00:01:29,730
>> En het beste voorbeeld dat ik heb
want dat is het inbrengen soort.

26
00:01:29,730 --> 00:01:31,650
Als u onze video herinneren
op insertion sort,

27
00:01:31,650 --> 00:01:34,110
Er was veel
kosten die betrokken zijn in het hebben van

28
00:01:34,110 --> 00:01:37,970
te halen elementen, en verschuiven ze
uit de weg om iets te passen

29
00:01:37,970 --> 00:01:41,290
in het midden van de array.

30
00:01:41,290 --> 00:01:44,690
Arrays ook last van andere
probleem, dat is inflexibiliteit.

31
00:01:44,690 --> 00:01:47,150
Toen we verklaren een array,
we krijgen een schot op het.

32
00:01:47,150 --> 00:01:49,790
We krijgen om te zeggen, ik wil
zoveel elementen.

33
00:01:49,790 --> 00:01:51,940
Misschien 100, het misschien
zijn 1000, het misschien

34
00:01:51,940 --> 00:01:55,930
worden x waarbij x een getal die de gebruiker
gaf ons op een prompt of op bevel

35
00:01:55,930 --> 00:01:56,630
lijn.

36
00:01:56,630 --> 00:01:59,905
>> Maar we krijgen maar één kans op het, we
niet krijgen dan zeggen oh, eigenlijk heb ik

37
00:01:59,905 --> 00:02:04,360
nodig 101, of ik x plus 20 nodig.

38
00:02:04,360 --> 00:02:07,910
Te laat, hebben we al uitgeroepen tot het
array, en als we willen krijgen 101 of x

39
00:02:07,910 --> 00:02:12,050
plus 20, we moeten verklaren
Een geheel andere array,

40
00:02:12,050 --> 00:02:15,540
kopieer alle elementen van de array
over, en dan hebben we genoeg.

41
00:02:15,540 --> 00:02:19,880
En wat als we het weer mis, wat
als we eigenlijk nodig hebben 102 of x plus 40,

42
00:02:19,880 --> 00:02:21,970
We moeten dit opnieuw doen.

43
00:02:21,970 --> 00:02:26,250
Dus ze zijn zeer inflexibel
voor het wijzigen van onze gegevens,

44
00:02:26,250 --> 00:02:29,360
maar als we samen een aantal combineren
van de basis die we hebben al

45
00:02:29,360 --> 00:02:33,230
geleerd over pointers en structuren,
in het bijzonder het gebruik van dynamisch geheugen

46
00:02:33,230 --> 00:02:36,180
toewijzing met malloc, we
kunnen deze stukken samen te stellen

47
00:02:36,180 --> 00:02:40,960
een nieuwe data structure-- een aanmaken
enkelvoudig gelinkte lijst kunnen we say--

48
00:02:40,960 --> 00:02:45,400
die ons in staat stelt om te groeien en
krimpen een verzameling van waarden

49
00:02:45,400 --> 00:02:48,800
en we zullen geen verspilde ruimte.

50
00:02:48,800 --> 00:02:53,320
>> Dus nogmaals, dit idee noemen we,
dit begrip, een gekoppelde lijst.

51
00:02:53,320 --> 00:02:56,320
In het bijzonder in deze video zijn we
over enkelvoudig gelinkte lijst,

52
00:02:56,320 --> 00:02:59,185
en dan nog een video we praten
ongeveer dubbel gelinkte lijsten, die

53
00:02:59,185 --> 00:03:01,560
is gewoon een variatie op een thema hier.

54
00:03:01,560 --> 00:03:05,200
Maar een enkelvoudig gelinkte lijst
bestaat uit knooppunten

55
00:03:05,200 --> 00:03:08,559
knooppunten alleen maar een abstracte term--
het is gewoon iets wat ik bel

56
00:03:08,559 --> 00:03:10,350
dat is een soort
structuur, in feite, ik ben?

57
00:03:10,350 --> 00:03:16,190
Gewoon om het een node-- en dit noemen
knooppunt twee leden of twee velden.

58
00:03:16,190 --> 00:03:20,300
Het heeft data, meestal een
integer, een karakter vlotter,

59
00:03:20,300 --> 00:03:23,790
of kunnen een ander type data worden
die u hebt gedefinieerd met een soort def.

60
00:03:23,790 --> 00:03:29,290
En een verwijzing naar bevat
andere knoop van hetzelfde type.

61
00:03:29,290 --> 00:03:34,710
>> Dus hebben we twee dingen binnenkant van
Dit knooppunt data en een pointer

62
00:03:34,710 --> 00:03:36,380
een ander knooppunt.

63
00:03:36,380 --> 00:03:39,370
En als je begint te visualiseren
dit, kunt u erover nadenkt

64
00:03:39,370 --> 00:03:42,280
als een keten van knooppunten die
elkaar verbonden.

65
00:03:42,280 --> 00:03:45,070
We hebben het eerste knooppunt, is het
bevat data, en een wijzer

66
00:03:45,070 --> 00:03:49,110
met het tweede knooppunt, dat geheel
data, en een verwijzing naar het derde knooppunt.

67
00:03:49,110 --> 00:03:52,940
En dus dat is waarom we noemen het een
gelinkte lijst, zijn ze met elkaar verbonden.

68
00:03:52,940 --> 00:03:56,070
>> Wat doet deze bijzondere
knooppunt structuur eruit?

69
00:03:56,070 --> 00:04:01,120
Nou, als je te herinneren van onze video-on-
definiëren van aangepaste soorten, met type def,

70
00:04:01,120 --> 00:04:05,400
kunnen we een structure-- definiëren en
typt definiëren een structuur als deze.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, en dan ben ik
gebruik hier het woord in waarde willekeurig

72
00:04:11,240 --> 00:04:13,891
voor elk type data echt aan te geven.

73
00:04:13,891 --> 00:04:16,890
Je zou kunnen doorgeven aan een integer of float,
je zou kunnen hebben wat je wilt.

74
00:04:16,890 --> 00:04:19,389
Het is niet beperkt tot alleen
integers, of iets dergelijks.

75
00:04:19,389 --> 00:04:22,790
Dus de waarde is gewoon een willekeurige
data type, en vervolgens een pointer

76
00:04:22,790 --> 00:04:26,310
een ander knooppunt van hetzelfde type.

77
00:04:26,310 --> 00:04:29,690
>> Nu, er is een kleine vangst
Hier definiëren met een structuur

78
00:04:29,690 --> 00:04:33,030
als het een self referentiële structuur.

79
00:04:33,030 --> 00:04:35,340
Ik heb een tijdelijke hebben
naam voor mijn structuur.

80
00:04:35,340 --> 00:04:37,640
Aan het eind van de dag I
duidelijk wilt noemen

81
00:04:37,640 --> 00:04:43,030
sll knooppunt, dat is uiteindelijk de nieuwe
noem een ​​deel van mijn type definitie

82
00:04:43,030 --> 00:04:47,450
maar ik kan sll knooppunt gebruiken
in het midden van dit.

83
00:04:47,450 --> 00:04:51,430
De reden hiervoor is, dat heb ik niet
creëerde een soort genaamd SLL knooppunt

84
00:04:51,430 --> 00:04:55,200
totdat ik raakte dit laatste punt hier.

85
00:04:55,200 --> 00:04:59,720
Tot dat moment, ik heb
een andere manier om te verwijzen naar dit soort gegevens.

86
00:04:59,720 --> 00:05:02,440
>> En dit is een self
referentiële data type.

87
00:05:02,440 --> 00:05:06,314
Het; s een data type van een
structuur die data bevat,

88
00:05:06,314 --> 00:05:08,480
en een pointer naar een andere
structuur van hetzelfde type.

89
00:05:08,480 --> 00:05:11,750
Dus ik moet in staat zijn om te verwijzen naar
dit gegevenstype althans tijdelijk

90
00:05:11,750 --> 00:05:14,910
dus het geven van een tijdelijke
naam van struct sllist

91
00:05:14,910 --> 00:05:18,540
kan ik dan zeggen dat ik wil een
pointer naar een andere structuur sllist,

92
00:05:18,540 --> 00:05:24,690
een structuur sllist ster, en dan
nadat ik de definitie hebt voltooid,

93
00:05:24,690 --> 00:05:27,220
Ik kan nu noemen dit type een SLL-knooppunt.

94
00:05:27,220 --> 00:05:30,520
>> Dus dat is waarom zie je er
een tijdelijke naam hier,

95
00:05:30,520 --> 00:05:31,879
maar een permanente naam hier.

96
00:05:31,879 --> 00:05:33,920
Soms heb je zou kunnen zien
definities structuur,

97
00:05:33,920 --> 00:05:36,570
bijvoorbeeld, die niet
self referential, dat

98
00:05:36,570 --> 00:05:39,390
niet een specificatie naam niet hier hebben.

99
00:05:39,390 --> 00:05:43,040
Het zou gewoon zeggen typedef struct,
Open accolade en definieer het dan.

100
00:05:43,040 --> 00:05:45,620
Maar als je structuur is zelf
referentiële, als deze is,

101
00:05:45,620 --> 00:05:49,010
je nodig hebt om een ​​te specificeren
tijdelijke typenaam.

102
00:05:49,010 --> 00:05:51,310
Maar uiteindelijk, nu
dat we dit hebben gedaan,

103
00:05:51,310 --> 00:05:53,620
kunnen we alleen maar verwijzen naar
deze knooppunten, deze eenheden,

104
00:05:53,620 --> 00:05:57,900
als sll knooppunten voor doeleinden
van de rest van deze video.

105
00:05:57,900 --> 00:06:00,900
>> Oké, dus we weten hoe
maak een gelinkte lijst knooppunt.

106
00:06:00,900 --> 00:06:03,240
We weten hoe te definiëren
een gelinkte lijst knooppunt.

107
00:06:03,240 --> 00:06:06,670
Nu, als we gaan om te beginnen
ze te gebruiken om informatie te verzamelen,

108
00:06:06,670 --> 00:06:10,360
Er zijn een paar van de activiteiten die we
moeten begrijpen en te werken met.

109
00:06:10,360 --> 00:06:12,860
We moeten weten hoe te creëren
een gekoppelde lijst uit de lucht.

110
00:06:12,860 --> 00:06:14,901
Als er geen lijst met al,
we willen beginnen.

111
00:06:14,901 --> 00:06:16,960
Dus moeten we in staat zijn
naar een gekoppelde lijst te maken,

112
00:06:16,960 --> 00:06:19,130
moeten we waarschijnlijk zoeken
via de link lijst

113
00:06:19,130 --> 00:06:21,830
een element dat we te vinden.

114
00:06:21,830 --> 00:06:24,430
We moeten in staat zijn om in te voegen
nieuwe dingen in de lijst,

115
00:06:24,430 --> 00:06:25,930
we willen dat onze lijst om te kunnen groeien.

116
00:06:25,930 --> 00:06:28,638
En zo ook, we willen kunnen
om dingen uit onze lijst schrappen,

117
00:06:28,638 --> 00:06:30,250
we willen onze lijst om te kunnen krimpen.

118
00:06:30,250 --> 00:06:32,160
En aan het einde van onze
programma's, in het bijzonder

119
00:06:32,160 --> 00:06:34,550
Als u zich herinneren dat we
dynamisch toewijzen van geheugen

120
00:06:34,550 --> 00:06:38,337
deze lijsten meestal te bouwen,
we willen allemaal dat het geheugen vrij te maken

121
00:06:38,337 --> 00:06:39,670
als we klaar ermee werken.

122
00:06:39,670 --> 00:06:44,627
En dus moeten we in staat zijn om een ​​te verwijderen
gehele gekoppelde lijst in één klap niet.

123
00:06:44,627 --> 00:06:46,460
Dus laten we gaan door
een aantal van deze operaties

124
00:06:46,460 --> 00:06:51,192
en hoe we ze kunnen visualiseren,
praten in pseudo-code in het bijzonder.

125
00:06:51,192 --> 00:06:53,150
Dus we willen een maken
gelinkte lijst, dus misschien we

126
00:06:53,150 --> 00:06:56,480
een functie wilt definiëren
dit prototype.

127
00:06:56,480 --> 00:07:01,690
sll knooppunt ster, creëren, en ik ben het passeren
in één argument, wat willekeurige data

128
00:07:01,690 --> 00:07:05,530
typt weer van enkele willekeurige data type.

129
00:07:05,530 --> 00:07:10,482
Maar ik ben returning-- deze functie moet
terug naar mij een pointer, een afzonderlijk

130
00:07:10,482 --> 00:07:11,190
gelinkte lijst knooppunt.

131
00:07:11,190 --> 00:07:14,050
Nogmaals, we proberen te creëren
een gekoppelde lijst uit de lucht,

132
00:07:14,050 --> 00:07:17,900
dus ik moet een pointer naar
die lijst als ik klaar ben.

133
00:07:17,900 --> 00:07:19,420
>> Dus wat zijn de stappen die hier bij betrokken?

134
00:07:19,420 --> 00:07:20,960
Nou, het eerste wat ik ben
gaan doen is dynamisch

135
00:07:20,960 --> 00:07:22,550
toewijzen ruimte voor een nieuw knooppunt.

136
00:07:22,550 --> 00:07:26,689
Nogmaals, we maken het uit dunne
lucht, dus we moeten malloc ruimte voor.

137
00:07:26,689 --> 00:07:28,480
En natuurlijk, onmiddellijk
nadat we malloc,

138
00:07:28,480 --> 00:07:31,692
checken we altijd om ervoor te zorgen dat onze
pointer-- we niet terug null.

139
00:07:31,692 --> 00:07:33,650
Want als we proberen en
eerbied een null pointer,

140
00:07:33,650 --> 00:07:36,190
we gaan een last
segfault en we niet willen dat.

141
00:07:36,190 --> 00:07:39,510
>> Dan willen we in het veld in te vullen,
willen we het veld waarde initialiseren

142
00:07:39,510 --> 00:07:41,690
initialiseren en het volgende veld.

143
00:07:41,690 --> 00:07:45,450
En dan willen we to-- uiteindelijk als
functie prototype indicates-- we willen

144
00:07:45,450 --> 00:07:49,940
een pointer keren naar een SLL knooppunt.

145
00:07:49,940 --> 00:07:51,710
Dus wat maakt dit eruit als visueel?

146
00:07:51,710 --> 00:07:55,230
Nou, ten eerste gaan we dynamisch
toewijzen ruimte voor een nieuwe SLL knooppunt

147
00:07:55,230 --> 00:07:58,320
dus we malloc-- dat is
een visuele representatie

148
00:07:58,320 --> 00:08:00,020
van het knooppunt we zojuist hebt gemaakt.

149
00:08:00,020 --> 00:08:02,757
En we controleren om ervoor te zorgen
het is niet null-- in casu

150
00:08:02,757 --> 00:08:04,840
het beeld niet zou hebben
opdagen als het null,

151
00:08:04,840 --> 00:08:07,298
we uit het geheugen zou hebben gelopen,
dus we zijn goed om daar heen te gaan.

152
00:08:07,298 --> 00:08:10,200
Dus nu zijn we op stap C,
initialiseren het veld knooppunten waarde.

153
00:08:10,200 --> 00:08:12,280
Nou ja, op basis van deze functie
noem ik hier gebruik,

154
00:08:12,280 --> 00:08:16,700
lijkt erop dat ik wil overgaan in 6,
Dus ik zal 6 in het veld waarde.

155
00:08:16,700 --> 00:08:18,865
Nu, initialiseren het volgende veld.

156
00:08:18,865 --> 00:08:21,640
Nou, wat ga ik daar doen,
er is niets naast, rechts,

157
00:08:21,640 --> 00:08:23,600
Dit is het enige wat in de lijst.

158
00:08:23,600 --> 00:08:27,206
Dus wat is het volgende dat in de lijst?

159
00:08:27,206 --> 00:08:29,660
>> Het moet niet wijzen op iets, rechts.

160
00:08:29,660 --> 00:08:33,600
Er is niets anders is er, dus wat is
het concept die we kennen dat is nothing--

161
00:08:33,600 --> 00:08:35,638
pointers niets?

162
00:08:35,638 --> 00:08:37,929
Het moet misschien willen we
een null pointer daar te zetten,

163
00:08:37,929 --> 00:08:40,178
en ik zal de nul vertegenwoordigen
pointer als gewoon een rode doos,

164
00:08:40,178 --> 00:08:41,559
we kunnen elke niet verder gaan.

165
00:08:41,559 --> 00:08:44,430
Zoals we zullen zien wat later,
we zullen uiteindelijk ketens

166
00:08:44,430 --> 00:08:46,330
pijlen verbinden
deze knooppunten samen,

167
00:08:46,330 --> 00:08:48,480
maar als je op de
rode doos, dat is null,

168
00:08:48,480 --> 00:08:51,150
we kunnen elke niet verder gaan,
dit is het einde van de lijst.

169
00:08:51,150 --> 00:08:53,960
>> En tot slot, we willen gewoon
retourneren een pointer naar dit knooppunt.

170
00:08:53,960 --> 00:08:56,160
Dus we noemen het nieuwe,
en zal nieuwe terugkeren

171
00:08:56,160 --> 00:08:59,370
zodat het kan worden gebruikt
welke functie geschapen.

172
00:08:59,370 --> 00:09:03,100
Dus daar gaan we, hebben we een afzonderlijk geschapen
gelinkte lijst knooppunt uit de lucht,

173
00:09:03,100 --> 00:09:05,920
en nu hebben we een lijst die we kunnen werken.

174
00:09:05,920 --> 00:09:08,260
>> Nu, laten we zeggen dat we al
hebben een grote keten,

175
00:09:08,260 --> 00:09:09,800
en we willen iets in vinden.

176
00:09:09,800 --> 00:09:12,716
En we willen een functie die gaat
true of false retourneren, afhankelijk

177
00:09:12,716 --> 00:09:15,840
Op de vraag of een waarde bestaat in die lijst.

178
00:09:15,840 --> 00:09:18,160
Een functie-prototype, of
verklaring voor die functie,

179
00:09:18,160 --> 00:09:23,320
eruit zou kunnen zien dit-- Bool te vinden, en
dan willen we nu in twee argumenten.

180
00:09:23,320 --> 00:09:26,996
>> De eerste is een verwijzing naar het
eerste element van de gekoppelde lijst.

181
00:09:26,996 --> 00:09:29,620
Dit is eigenlijk iets wat je zult
willen altijd bij te houden,

182
00:09:29,620 --> 00:09:33,110
en eigenlijk zou iets dat
je zelfs in een globale variabele.

183
00:09:33,110 --> 00:09:35,360
Zodra u een lijst te maken,
je altijd, altijd

184
00:09:35,360 --> 00:09:38,990
willen houden van de zeer
eerste element van de lijst.

185
00:09:38,990 --> 00:09:43,690
Op die manier kunt u verwijzen naar alle andere
elementen door gewoon naar aanleiding van de keten,

186
00:09:43,690 --> 00:09:47,300
zonder aanwijzingen te houden
intact elk element.

187
00:09:47,300 --> 00:09:50,920
U hoeft alleen voor het bijhouden van de eerste te houden
één als ze allemaal bij elkaar vastgeketend.

188
00:09:50,920 --> 00:09:52,460
>> En dan de tweede ding
we weer passeren in

189
00:09:52,460 --> 00:09:54,376
arbitrair some--
ongeacht het type gegevens we

190
00:09:54,376 --> 00:09:59,640
zoekt er binnenin
Hopelijk een van de knooppunten in de lijst.

191
00:09:59,640 --> 00:10:00,980
Dus wat zijn de stappen?

192
00:10:00,980 --> 00:10:04,250
Nou, het eerste wat we doen is
creëren we een transversaal wijzer

193
00:10:04,250 --> 00:10:06,015
wijzend naar de lijsten hoofd.

194
00:10:06,015 --> 00:10:08,890
Nou, waarom doen we dat doen we al
een pointer op de lijsten kop,

195
00:10:08,890 --> 00:10:10,974
waarom doen we niet bewegen alleen dat niemand in de buurt?

196
00:10:10,974 --> 00:10:13,140
Nou, zoals ik net zei,
het is echt belangrijk voor ons

197
00:10:13,140 --> 00:10:17,580
altijd bijhouden van de
eerste element van de lijst.

198
00:10:17,580 --> 00:10:21,270
En dus is het eigenlijk beter
een duplicaat van dat creëren

199
00:10:21,270 --> 00:10:25,350
en gebruik dat om rond zodat we nooit bewegen
per ongeluk af te stappen, of we altijd

200
00:10:25,350 --> 00:10:30,430
een wijzer op een bepaald punt dat is
recht op het eerste element van de lijst.

201
00:10:30,430 --> 00:10:33,290
Dus het is beter om een ​​te creëren
tweede dat we om te bewegen.

202
00:10:33,290 --> 00:10:35,877
>> Toen we net vergelijken of
het veld waarde op dat knooppunt

203
00:10:35,877 --> 00:10:38,960
is wat we zoeken, en als het
niet, we gaan naar het volgende knooppunt.

204
00:10:38,960 --> 00:10:41,040
En we blijven dat doen
over, en dan, en dan,

205
00:10:41,040 --> 00:10:44,811
totdat we ofwel vinden
het element, of we slaan

206
00:10:44,811 --> 00:10:47,310
null-- we het einde bereikt
van de lijst en het is er niet.

207
00:10:47,310 --> 00:10:50,540
Dit moet hopelijk een belletje rinkelen
om u als gewoon lineair zoeken,

208
00:10:50,540 --> 00:10:54,430
we gewoon herhalen in
een enkelvoudig gelinkte lijst structuur

209
00:10:54,430 --> 00:10:56,280
in plaats van een array te doen.

210
00:10:56,280 --> 00:10:58,210
>> Dus hier is een voorbeeld van
een enkelvoudig gelinkte lijst.

211
00:10:58,210 --> 00:11:00,043
Deze bestaat uit
vijf knooppunten, en we hebben

212
00:11:00,043 --> 00:11:04,330
een verwijzing naar het hoofd van de
lijst, die lijst wordt genoemd.

213
00:11:04,330 --> 00:11:07,385
Het eerste wat we willen doen is
nogmaals, maak dat traversal pointer.

214
00:11:07,385 --> 00:11:09,760
Dus we hebben nu twee pointers
dat punt aan het zelfde ding.

215
00:11:09,760 --> 00:11:15,025
>> Nu, let hier ook, ik deed het niet
moet iedere ruimte voor trav malloc.

216
00:11:15,025 --> 00:11:18,970
Ik heb niet gezegd trav gelijk aan malloc
iets, dat knooppunt al bestaat,

217
00:11:18,970 --> 00:11:21,160
die ruimte in het geheugen bestaat.

218
00:11:21,160 --> 00:11:24,290
Dus alles wat ik eigenlijk aan het doen is
het creëren van een pointer naar het.

219
00:11:24,290 --> 00:11:28,210
Ik ben niet mallocing een extra
ruimte, maar hebben nu twee pointers

220
00:11:28,210 --> 00:11:31,370
die aan hetzelfde.

221
00:11:31,370 --> 00:11:33,710
>> Dus is 2 wat ik zoek?

222
00:11:33,710 --> 00:11:37,220
Nou, nee, dus in plaats ik ben
ga naar de volgende.

223
00:11:37,220 --> 00:11:41,740
Dus eigenlijk zou ik zeggen,
trav gelijk trav volgende.

224
00:11:41,740 --> 00:11:43,630
3 is wat ik ben op zoek naar, nee.

225
00:11:43,630 --> 00:11:45,780
Dus ik blijven gaan
door en tot uiteindelijk

226
00:11:45,780 --> 00:11:48,690
naar 6 dat is wat ik zoek
voor op basis van de functie-oproep

227
00:11:48,690 --> 00:11:51,600
Ik heb aan de top
daar, en dus ik ben klaar.

228
00:11:51,600 --> 00:11:54,150
>> Nu, wat als het element ik ben
naar niet in de lijst,

229
00:11:54,150 --> 00:11:55,510
is het nog steeds gaat werken?

230
00:11:55,510 --> 00:11:57,120
Nou, merken dat de lijst
hier is subtiel anders,

231
00:11:57,120 --> 00:11:59,410
en dit is een ander ding dat is
belangrijk met gelinkte lijsten,

232
00:11:59,410 --> 00:12:01,780
je niet hoeft te behouden
ze in een bepaalde volgorde.

233
00:12:01,780 --> 00:12:05,390
Je kunt als je wilt, maar
je misschien al hebt gemerkt

234
00:12:05,390 --> 00:12:09,310
dat we niet bijhouden
welk nummer element we op.

235
00:12:09,310 --> 00:12:13,150
>> En dat is een soort van een handel die we
hebben met gekoppelde lijst verzen arrays,

236
00:12:13,150 --> 00:12:15,300
het is hebben we niet
random access meer.

237
00:12:15,300 --> 00:12:18,150
We kunnen niet zomaar zeggen: ik wil
naar de 0-element,

238
00:12:18,150 --> 00:12:21,410
of 6 element van mijn array,
die ik kan doen in een array.

239
00:12:21,410 --> 00:12:25,080
Ik kan niet zeggen dat ik wil naar de
0 element, of de 6-element,

240
00:12:25,080 --> 00:12:30,360
of de 25ste element van mijn gekoppelde lijst,
er is geen index in verband met hen.

241
00:12:30,360 --> 00:12:33,660
En dus is het niet echt van belang
als we onze lijst te bewaren in orde.

242
00:12:33,660 --> 00:12:36,080
Als u wilt u
kan zeker, maar er is

243
00:12:36,080 --> 00:12:38,567
geen reden waarom ze nodig hebben om
worden bewaard in elke volgorde.

244
00:12:38,567 --> 00:12:40,400
Dus nogmaals, laten we proberen en
vind 6 in deze lijst.

245
00:12:40,400 --> 00:12:43,200
Nou, we beginnen bij de
beginnen, doen we niet vinden 6,

246
00:12:43,200 --> 00:12:47,690
en dan blijven we niet vinden
6, tot we uiteindelijk hier.

247
00:12:47,690 --> 00:12:52,790
Dus nu trav punten aan het knooppunt
met 8, en zes is er niet in.

248
00:12:52,790 --> 00:12:55,250
>> Dus de volgende stap zou zijn
naar de volgende pointer,

249
00:12:55,250 --> 00:12:57,440
dus zeggen trav gelijk trav volgende.

250
00:12:57,440 --> 00:13:00,750
Nou, trav volgende, aangegeven door
de rode doos er is nul.

251
00:13:00,750 --> 00:13:03,020
Dus er is nergens anders
gaan, en dus op dit punt

252
00:13:03,020 --> 00:13:06,120
kunnen we concluderen dat we hebben bereikt
het einde van de gekoppelde lijst,

253
00:13:06,120 --> 00:13:07,190
en 6 is er niet in.

254
00:13:07,190 --> 00:13:10,980
En het zou worden teruggegeven
false in dit geval.

255
00:13:10,980 --> 00:13:14,540
>> OK, hoe kunnen we plaats een nieuwe
knooppunt in de gelinkte lijst?

256
00:13:14,540 --> 00:13:17,310
Daarom hebben we in staat om te creëren geweest
een gekoppelde lijst uit het niets,

257
00:13:17,310 --> 00:13:19,370
maar we willen waarschijnlijk
bouwen van een keten en niet

258
00:13:19,370 --> 00:13:22,620
het creëren van een heleboel verschillende lijsten.

259
00:13:22,620 --> 00:13:25,700
We willen een lijst die
heeft een heleboel knooppunten in het,

260
00:13:25,700 --> 00:13:28,040
niet een bos van lijsten met een enkel knooppunt.

261
00:13:28,040 --> 00:13:31,260
Dus we kunnen niet gewoon blijven met de Create
functie die we eerder gedefinieerd, nu zijn we

262
00:13:31,260 --> 00:13:33,860
wilt invoegen in een
lijst die al bestaat.

263
00:13:33,860 --> 00:13:36,499
>> Dus dit geval, we gaan
geschiedde in twee argumenten,

264
00:13:36,499 --> 00:13:39,290
de aanwijzer naar het hoofd van die
gelinkte lijst die we willen toevoegen.

265
00:13:39,290 --> 00:13:40,910
Nogmaals, dat is waarom het zo
belangrijk dat we altijd

266
00:13:40,910 --> 00:13:43,400
bijhouden, want
het is de enige manier waarop we echt

267
00:13:43,400 --> 00:13:46,690
hebben betrekking op de gehele lijst is
alleen door een pointer naar het eerste element.

268
00:13:46,690 --> 00:13:49,360
Dus we willen passeren in een
pointer om die eerste element,

269
00:13:49,360 --> 00:13:52,226
en welke waarde we
wilt toevoegen aan de lijst.

270
00:13:52,226 --> 00:13:54,600
En uiteindelijk deze functie
gaat een pointer terug

271
00:13:54,600 --> 00:13:57,980
tot het nieuwe hoofd van een gekoppelde lijst.

272
00:13:57,980 --> 00:13:59,700
>> Wat zijn de stappen die hier bij betrokken?

273
00:13:59,700 --> 00:14:02,249
Nou, net als bij te creëren,
we moeten dynamisch toewijzen

274
00:14:02,249 --> 00:14:05,540
ruimte voor een nieuw knooppunt en controleer
zeker dat we niet uit het geheugen lopen, opnieuw,

275
00:14:05,540 --> 00:14:07,150
omdat we met behulp van malloc.

276
00:14:07,150 --> 00:14:09,080
Dan willen we bevolken
en steek het knooppunt,

277
00:14:09,080 --> 00:14:12,730
dus zet het nummer, ongeacht
val is, naar het knooppunt.

278
00:14:12,730 --> 00:14:17,310
We willen het knooppunt invoegen op
het begin van de gekoppelde lijst.

279
00:14:17,310 --> 00:14:19,619
>> Er is een reden dat ik
dit wilt doen, en het

280
00:14:19,619 --> 00:14:21,910
de moeite waard een tweede zou kunnen zijn
de video hier pauzeren

281
00:14:21,910 --> 00:14:25,860
en na te denken over de reden waarom ik zou willen
invoegen aan het begin van een gekoppelde

282
00:14:25,860 --> 00:14:26,589
lijst.

283
00:14:26,589 --> 00:14:28,630
Nogmaals, ik eerder noemde
dat het niet echt

284
00:14:28,630 --> 00:14:33,020
uit of we te behouden in een
bestelling, dus misschien is dat een aanwijzing.

285
00:14:33,020 --> 00:14:36,040
En je zag wat er zou gebeuren als we
wilde to-- of van slechts een seconde

286
00:14:36,040 --> 00:14:37,360
geleden, toen we gingen
door middel van je zoekopdracht

287
00:14:37,360 --> 00:14:39,235
wat kon zien zou
er gebeuren als we probeerden

288
00:14:39,235 --> 00:14:41,330
te voegen aan het einde van de lijst.

289
00:14:41,330 --> 00:14:44,750
Omdat we niet een hebben
wijzer naar het einde van de lijst.

290
00:14:44,750 --> 00:14:47,490
>> Dus de reden dat ik zou willen
te voegen aan het begin,

291
00:14:47,490 --> 00:14:49,380
is omdat ik het onmiddellijk kan doen.

292
00:14:49,380 --> 00:14:52,730
Ik heb een pointer aan het begin en
we zullen zien in een visuele in een tweede.

293
00:14:52,730 --> 00:14:55,605
Maar als ik wil voegen aan het eind,
Ik moet beginnen bij het begin,

294
00:14:55,605 --> 00:14:58,760
doorkruisen de hele weg naar de
end, en overstag vervolgens op.

295
00:14:58,760 --> 00:15:01,420
Dus dat zou betekenen dat
inbrengen aan het einde van de lijst

296
00:15:01,420 --> 00:15:04,140
zou een o n geworden
operatie, terug te gaan

297
00:15:04,140 --> 00:15:06,720
naar onze bespreking van
computationele complexiteit.

298
00:15:06,720 --> 00:15:10,140
Het zou een o n operatie, waarbij geworden
als de lijst werd groter en groter,

299
00:15:10,140 --> 00:15:13,310
en groter, zal het meer geworden en
moeilijker om iets tack

300
00:15:13,310 --> 00:15:14,661
op eind.

301
00:15:14,661 --> 00:15:17,410
Maar het is altijd heel makkelijk om
overstag iets op aan het begin,

302
00:15:17,410 --> 00:15:19,060
je bent altijd aan het begin.

303
00:15:19,060 --> 00:15:21,620
>> En we zullen zien weer een visuele van deze.

304
00:15:21,620 --> 00:15:24,100
En toen we eenmaal klaar bent, zodra
we hebben het nieuwe knooppunt geplaatst,

305
00:15:24,100 --> 00:15:26,880
we willen onze pointer terug te keren naar
het nieuwe hoofd van een gelinkte lijst, die

306
00:15:26,880 --> 00:15:29,213
aangezien we het invoegen op de
begin zal eigenlijk

307
00:15:29,213 --> 00:15:31,060
een verwijzing naar het knooppunt we zojuist hebt gemaakt.

308
00:15:31,060 --> 00:15:33,280
Laten we dit visualiseren,
omdat ik denk dat het zal helpen.

309
00:15:33,280 --> 00:15:36,661
>> Dus hier is onze lijst, het bestaat uit
vier elementen, een knooppunt met 15,

310
00:15:36,661 --> 00:15:38,410
die wijst op een knooppunt
met 9, waarbij

311
00:15:38,410 --> 00:15:41,370
verwijst naar een knooppunt met 13,
die wijst op een knooppunt met

312
00:15:41,370 --> 00:15:44,840
10, waarbij de nulhypothese heeft
pointer als zijn volgende pointer

313
00:15:44,840 --> 00:15:47,010
dat is het einde van de lijst.

314
00:15:47,010 --> 00:15:50,200
Dus we willen een voegen
nieuw knooppunt met de waarde 12

315
00:15:50,200 --> 00:15:52,720
aan het begin van deze
lijst, wat doen we?

316
00:15:52,720 --> 00:15:58,770
Nou, ten eerste malloc we ruimte voor de
knooppunt, en dan zetten we 12 in.

317
00:15:58,770 --> 00:16:02,211
>> Dus nu hebben we bereikt een
beslispunt, toch?

318
00:16:02,211 --> 00:16:03,960
We hebben een paar
aanwijzingen dat we konden

319
00:16:03,960 --> 00:16:06,770
bewegen, welke moeten we eerst verhuizen?

320
00:16:06,770 --> 00:16:09,250
Moeten we maken 12 punt
het nieuwe hoofd van de list--

321
00:16:09,250 --> 00:16:13,020
of neem me niet kwalijk, moeten we 12
wijzen op de oude kop van de lijst?

322
00:16:13,020 --> 00:16:15,319
Of moeten we zeggen dat de
lijst begint nu op 12.

323
00:16:15,319 --> 00:16:17,110
Er is een onderscheid
daar, en we zullen kijken

324
00:16:17,110 --> 00:16:19,870
wat er gebeurt met zowel een seconde.

325
00:16:19,870 --> 00:16:23,350
>> Maar dit leidt tot een
groot onderwerp voor zijbalk,

326
00:16:23,350 --> 00:16:26,280
namelijk dat een van de
lastigste dingen met gekoppelde lijsten

327
00:16:26,280 --> 00:16:30,980
wordt naar de pointers te regelen
in de juiste volgorde.

328
00:16:30,980 --> 00:16:34,520
Als je dingen verplaatst buiten de orde,
kunt u per ongeluk belanden

329
00:16:34,520 --> 00:16:36,050
orphaning de rest van de lijst.

330
00:16:36,050 --> 00:16:37,300
En hier is een voorbeeld van.

331
00:16:37,300 --> 00:16:40,540
Dus laten we gaan met het idee van--
goed, we hebben zojuist 12.

332
00:16:40,540 --> 00:16:43,180
We weten dat 12 gaat worden
het nieuwe hoofd van de lijst,

333
00:16:43,180 --> 00:16:47,660
en dus waarom niet we gewoon bewegen
de lijst pointer om daar te wijzen.

334
00:16:47,660 --> 00:16:49,070
>> OK, dus dat is goed.

335
00:16:49,070 --> 00:16:51,560
Dus nu waar komt 12 volgende punt?

336
00:16:51,560 --> 00:16:54,580
Ik bedoel, visueel kunnen we zien
dat zal verwijzen naar 15,

337
00:16:54,580 --> 00:16:57,250
als mensen het is echt ons duidelijk.

338
00:16:57,250 --> 00:17:00,300
Hoe werkt de computer weet?

339
00:17:00,300 --> 00:17:02,720
We hebben niets
wijzend naar 15 meer, toch?

340
00:17:02,720 --> 00:17:05,869
>> We hebben elke mogelijkheid om te verwijzen naar 15 verloren.

341
00:17:05,869 --> 00:17:11,460
We kunnen geen nieuwe pijl naast gelijken zeggen
iets, er is niets daar.

342
00:17:11,460 --> 00:17:13,510
In feite hebben we verweesd
de rest van de lijst

343
00:17:13,510 --> 00:17:16,465
door dit te doen, we hebben
per ongeluk gebroken ketting.

344
00:17:16,465 --> 00:17:18,089
En we willen zeker niet om dat te doen.

345
00:17:18,089 --> 00:17:20,000
>> Dus laten we teruggaan en probeer dit opnieuw.

346
00:17:20,000 --> 00:17:24,060
Misschien is het juiste ding om te doen
is tot en met 12 van de volgende pointer ingesteld

347
00:17:24,060 --> 00:17:28,290
de oude kop van de eerste lijst,
dan kunnen we de lijst bewegen over.

348
00:17:28,290 --> 00:17:30,420
En in feite, dat is de
juiste volgorde dat wij

349
00:17:30,420 --> 00:17:32,836
moet volgen wanneer we
werken met enkelvoudig gelinkte lijst.

350
00:17:32,836 --> 00:17:36,460
Wij willen altijd het sluiten
nieuw element in de lijst,

351
00:17:36,460 --> 00:17:41,010
voordat we dat soort nemen
belangrijke stap van het veranderen

352
00:17:41,010 --> 00:17:43,360
wanneer het hoofd van de gekoppelde lijst.

353
00:17:43,360 --> 00:17:46,740
Nogmaals, dat is zo'n fundamentele ding,
we willen niet te houden van het te verliezen.

354
00:17:46,740 --> 00:17:49,310
>> Dus we willen ervoor zorgen dat
alles wordt aan elkaar geketend,

355
00:17:49,310 --> 00:17:52,040
voordat we verder dat pointer.

356
00:17:52,040 --> 00:17:55,300
En dus zou dit de juiste volgorde te zijn,
die verbinding 12 op de lijst,

357
00:17:55,300 --> 00:17:57,630
dan zeggen dat de lijst begint een 12.

358
00:17:57,630 --> 00:18:00,860
Als we zei dat de lijst begint bij 12 en
Vervolgens probeerde te verbinden 12 van de lijst,

359
00:18:00,860 --> 00:18:02,193
We hebben al gezien wat er gebeurt.

360
00:18:02,193 --> 00:18:04,920
We verliezen de lijst per vergissing.

361
00:18:04,920 --> 00:18:06,740
>> OK, dus nog een ding om over te praten.

362
00:18:06,740 --> 00:18:09,750
Wat als we willen om zich te ontdoen van
een hele tegelijk gelinkte lijst?

363
00:18:09,750 --> 00:18:11,750
Nogmaals, we mallocing
al deze ruimte, en dus hebben we

364
00:18:11,750 --> 00:18:13,351
nodig om het te bevrijden als we klaar zijn.

365
00:18:13,351 --> 00:18:15,350
Dus nu willen we verwijderen
de gehele gelinkte lijst.

366
00:18:15,350 --> 00:18:16,850
Nou, wat willen we doen?

367
00:18:16,850 --> 00:18:20,460
>> Als we de null pointer hebt bereikt, we
willen stoppen, anders gewoon verwijderen

368
00:18:20,460 --> 00:18:23,420
de rest van de lijst en vervolgens bevrijd mij.

369
00:18:23,420 --> 00:18:28,890
Verwijdert u de rest van de lijst,
en bevrijd dan het huidige knooppunt.

370
00:18:28,890 --> 00:18:32,850
Wat klinkt dat,
welke techniek hebben we gesproken

371
00:18:32,850 --> 00:18:35,440
over eerder klinkt dat?

372
00:18:35,440 --> 00:18:39,560
Delete iedereen, dan
terug te komen en me te verwijderen.

373
00:18:39,560 --> 00:18:42,380
>> Dat is recursie, hebben we de
probleem een ​​beetje kleiner,

374
00:18:42,380 --> 00:18:46,910
we zeggen schrappen iedereen
anders, dan kunt u mij verwijderen.

375
00:18:46,910 --> 00:18:50,940
En verder op de weg, dat knooppunt
zal zeggen, iedereen verwijderen.

376
00:18:50,940 --> 00:18:53,940
Maar uiteindelijk zullen we naar het krijgen
punt waar de lijst is nul,

377
00:18:53,940 --> 00:18:55,310
en dat is ons basisscenario.

378
00:18:55,310 --> 00:18:57,010
>> Dus laten we een kijkje nemen op deze,
en hoe dit zou kunnen werken.

379
00:18:57,010 --> 00:18:59,759
Dus hier is onze lijst, het is hetzelfde
geven we hadden het net over,

380
00:18:59,759 --> 00:19:00,980
en er is de stappen.

381
00:19:00,980 --> 00:19:04,200
Er is veel tekst hier, maar
hopelijk de visualisatie zal helpen.

382
00:19:04,200 --> 00:19:08,557
>> Dus we have-- en ik heb ook trok
onze stack frames illustratie

383
00:19:08,557 --> 00:19:10,890
van onze video-on-call stacks,
en hopelijk alles

384
00:19:10,890 --> 00:19:13,260
samen zullen je laten zien wat er gaande is.

385
00:19:13,260 --> 00:19:14,510
Dus hier is onze pseudo-code.

386
00:19:14,510 --> 00:19:17,830
Als we een nul bereiken
wijzer, stoppen, anders

387
00:19:17,830 --> 00:19:21,320
Verwijder de rest van de lijst,
vrij dan het huidige knooppunt.

388
00:19:21,320 --> 00:19:25,700
Dus nu, list--
de aanwijzer dat we

389
00:19:25,700 --> 00:19:28,410
passeren in de punten 12 vernietigen.

390
00:19:28,410 --> 00:19:33,340
12 is niet een null pointer, dus we zijn
naar de rest van de lijst.

391
00:19:33,340 --> 00:19:35,450
>> Wat is het verwijderen van de
rest van ons betrokken zijn?

392
00:19:35,450 --> 00:19:37,950
Nou, het betekent dat het maken van een
bellen om te vernietigen, zeggende

393
00:19:37,950 --> 00:19:42,060
15 is dat het begin van de
rest van de lijst die we willen vernietigen.

394
00:19:42,060 --> 00:19:47,480
En zo de oproep om te vernietigen
12 is een soort van in de wacht.

395
00:19:47,480 --> 00:19:52,690
Het is er bevroren, in afwachting van de
bellen om te vernietigen 15, om zijn werk af te maken.

396
00:19:52,690 --> 00:19:56,280
>> Nou, 15 is niet een null pointer en
dus het gaat om te zeggen, oke,

397
00:19:56,280 --> 00:19:58,450
goed, verwijdert u de rest van de lijst.

398
00:19:58,450 --> 00:20:00,760
De rest van de lijst begint
9, en dus zullen we net

399
00:20:00,760 --> 00:20:04,514
wachten tot je alles verwijderen dat
spul, kom dan terug en me te verwijderen.

400
00:20:04,514 --> 00:20:06,680
Nou 9 gaat zeggen, goed,
Ik ben niet een null pointer,

401
00:20:06,680 --> 00:20:09,020
dus verwijder de rest van de lijst van hier.

402
00:20:09,020 --> 00:20:11,805
En dus proberen en te vernietigen 13.

403
00:20:11,805 --> 00:20:15,550
13 zegt, ik ben niet null pointer,
hetzelfde, het passeren van de bok.

404
00:20:15,550 --> 00:20:17,930
10 is niet null pointer, 10
bevat een null pointer,

405
00:20:17,930 --> 00:20:20,200
10 maar zelf geen
null nu wijzer,

406
00:20:20,200 --> 00:20:22,470
en zo gaat de bok ook.

407
00:20:22,470 --> 00:20:25,560
>> En nu een lijst van punten daar, het
echt zou wijzen op some--

408
00:20:25,560 --> 00:20:28,710
als ik meer ruimte in het beeld,
het zou wijzen op een aantal willekeurige ruimte

409
00:20:28,710 --> 00:20:29,960
dat we niet weten wat het is.

410
00:20:29,960 --> 00:20:34,680
Het is de null pointer hoewel, de lijst
is letterlijk nu ingesteld is het waarden null.

411
00:20:34,680 --> 00:20:36,820
Het is naar rechts in die rode doos.

412
00:20:36,820 --> 00:20:39,960
We bereikten een null pointer, dus
we kunnen stoppen, en we zijn klaar.

413
00:20:39,960 --> 00:20:46,230
>> En zodat paars frame now-- op
top van stack-- dat is het actieve frame,

414
00:20:46,230 --> 00:20:47,017
maar het heeft gedaan.

415
00:20:47,017 --> 00:20:48,600
Als we een null pointer hebt bereikt, stop.

416
00:20:48,600 --> 00:20:51,290
We doen niets, we
kan er niet een null pointer,

417
00:20:51,290 --> 00:20:55,070
we hadden geen malloc
ruimte, en dus zijn we klaar.

418
00:20:55,070 --> 00:20:57,590
Zodat de functie kader
wordt vernietigd, en we

419
00:20:57,590 --> 00:21:00,930
resume-- we halen waar we gebleven
af met de volgende hoogste een, die

420
00:21:00,930 --> 00:21:02,807
Dit is donkerblauw lijst hier.

421
00:21:02,807 --> 00:21:04,390
Dus halen we precies waar we gebleven waren.

422
00:21:04,390 --> 00:21:06,598
We verwijderde de rest van de
lijst al, dus nu zijn we

423
00:21:06,598 --> 00:21:08,000
naar de huidige nodes bevrijden.

424
00:21:08,000 --> 00:21:12,920
Dus nu kunnen we vrij dit knooppunt, en nu
we hebben het einde van de functie bereikt.

425
00:21:12,920 --> 00:21:16,810
En zodat functie frame vernietigd
en we ophalen op de licht blauwe.

426
00:21:16,810 --> 00:21:20,650
>> Dus het says-- Ik heb al done--
verwijderen van de rest van de lijst, zodat

427
00:21:20,650 --> 00:21:23,140
vrij het huidige knooppunt.

428
00:21:23,140 --> 00:21:26,520
En nu de gele frame
weer bovenop de stapel.

429
00:21:26,520 --> 00:21:29,655
En zo zie je, we zijn nu
vernietigen van de lijst van rechts naar links.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Wat zou er gebeurd zijn, maar,
als we dingen hadden gedaan de verkeerde manier?

432
00:21:37,280 --> 00:21:39,410
Net als toen we probeerden
een element toe te voegen.

433
00:21:39,410 --> 00:21:41,909
Als we messed up van de keten, indien
we niet de pointers verbinden

434
00:21:41,909 --> 00:21:44,690
in de juiste volgorde, als we
alleen het eerste element bevrijd,

435
00:21:44,690 --> 00:21:47,420
als we net bevrijd van de
hoofd van de lijst, nu zijn we

436
00:21:47,420 --> 00:21:49,642
hebben geen manier om te verwijzen naar
de rest van de lijst.

437
00:21:49,642 --> 00:21:51,350
En dus zouden we
wees alles,

438
00:21:51,350 --> 00:21:53,880
we zouden hebben gehad wat is
riep een geheugenlek.

439
00:21:53,880 --> 00:21:56,800
Misschien herinner je je van onze video
op dynamisch geheugen toewijzing,

440
00:21:56,800 --> 00:21:58,650
dat is niet erg goede zaak.

441
00:21:58,650 --> 00:22:00,810
>> Dus zoals ik al zei, is er
zijn verschillende bewerkingen

442
00:22:00,810 --> 00:22:04,010
dat we gebruiken werken
met gekoppelde lijst effectief.

443
00:22:04,010 --> 00:22:08,430
En u misschien opgevallen ik weggelaten één,
verwijderen van een enkel element van een gekoppelde

444
00:22:08,430 --> 00:22:09,064
lijst.

445
00:22:09,064 --> 00:22:10,980
De reden dat ik dat deed
is het is eigenlijk soort

446
00:22:10,980 --> 00:22:14,360
lastig om na te denken over hoe om te verwijderen
een enkel element van een enkelvoudig

447
00:22:14,360 --> 00:22:15,600
gelinkte lijst.

448
00:22:15,600 --> 00:22:19,950
We moeten in staat zijn om over te slaan
iets in de lijst, die

449
00:22:19,950 --> 00:22:22,975
middelen krijgen we een point-- we
wil dit node-- verwijderen

450
00:22:22,975 --> 00:22:25,350
maar om het zo te maken dat we
geen informatie niet te verliezen,

451
00:22:25,350 --> 00:22:30,530
we nodig hebben om dit aan te sluiten
knooppunt dan hier, hier.

452
00:22:30,530 --> 00:22:33,390
>> Dus ik waarschijnlijk wel wat mis
visueel perspectief.

453
00:22:33,390 --> 00:22:36,830
Dus we zijn aan het begin van onze
lijst, zijn we te gaan door middel van,

454
00:22:36,830 --> 00:22:40,510
we willen dit knooppunt te verwijderen.

455
00:22:40,510 --> 00:22:43,440
Als we gewoon verwijderen,
we hebben de keten verbroken.

456
00:22:43,440 --> 00:22:45,950
Dit knooppunt hier
verwijst naar al het andere,

457
00:22:45,950 --> 00:22:48,260
het bevat de keten van hier op uit.

458
00:22:48,260 --> 00:22:51,190
>> Dus wat moeten we eigenlijk doen
nadat we op dit punt,

459
00:22:51,190 --> 00:22:56,670
is dat we nodig hebben om een ​​stap terug, en
sluit dit knooppunt naar dit knooppunt,

460
00:22:56,670 --> 00:22:58,590
dus we kunnen dan verwijderen
de een in het midden.

461
00:22:58,590 --> 00:23:02,120
Maar afzonderlijk gelinkte lijsten niet
bieden ons een manier om achteruit te gaan.

462
00:23:02,120 --> 00:23:05,160
Dus moeten we ofwel blijven
twee pointers, en verplaats

463
00:23:05,160 --> 00:23:09,527
soort van off stap achter
andere als we gaan, of naar een punt

464
00:23:09,527 --> 00:23:11,110
en stuur vervolgens een ander aanwijzer door.

465
00:23:11,110 --> 00:23:13,150
En zoals je kunt zien,
kan een beetje rommelig.

466
00:23:13,150 --> 00:23:15,360
Gelukkig hebben we
een andere manier op te lossen dat,

467
00:23:15,360 --> 00:23:17,810
als we praten over dubbel gelinkte lijsten.

468
00:23:17,810 --> 00:23:20,720
>> Ik ben Doug Lloyd, dit is CS50.

469
00:23:20,720 --> 00:23:22,298