1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Bij het programmeren, we moeten vaak lijsten van waarden vertegenwoordigen,

2
00:00:10,050 --> 00:00:12,840
zoals de namen van de studenten in een sectie

3
00:00:12,840 --> 00:00:15,100
of hun scores op de laatste quiz.

4
00:00:15,100 --> 00:00:17,430
>> In de taal C, verklaarde arrays kunnen worden gebruikt

5
00:00:17,430 --> 00:00:19,160
lijsten te slaan.

6
00:00:19,160 --> 00:00:21,200
Het is gemakkelijk om op te noemen de elementen van een lijst

7
00:00:21,200 --> 00:00:23,390
opgeslagen in een array, en als je nodig hebt om toegang te krijgen

8
00:00:23,390 --> 00:00:25,050
of wijzigen de i-de element in de lijst

9
00:00:25,050 --> 00:00:27,570
enkele willekeurige index I,

10
00:00:27,570 --> 00:00:29,910
gedaan kan worden in constante tijd,

11
00:00:29,910 --> 00:00:31,660
maar arrays nadelen ook.

12
00:00:31,660 --> 00:00:33,850
>> Toen we ze verklaren, zijn we verplicht om te zeggen

13
00:00:33,850 --> 00:00:35,900
van te voren hoe groot ze zijn,

14
00:00:35,900 --> 00:00:38,160
dat wil zeggen, hoeveel elementen ze slaan kunnen

15
00:00:38,160 --> 00:00:40,780
en hoe groot deze elementen, die wordt bepaald door hun type.

16
00:00:40,780 --> 00:00:45,450
Zo int arr (10)

17
00:00:45,450 --> 00:00:48,220
kan 10 items

18
00:00:48,220 --> 00:00:50,200
die de grootte van een int.

19
00:00:50,200 --> 00:00:52,590
>> We kunnen een array grootte niet veranderen na aangifte.

20
00:00:52,590 --> 00:00:55,290
We moeten een nieuwe array maken als we willen meer elementen op te slaan.

21
00:00:55,290 --> 00:00:57,410
De reden bestaat deze beperking is dat onze

22
00:00:57,410 --> 00:00:59,040
programma slaat de hele reeks

23
00:00:59,040 --> 00:01:02,310
als een aaneengesloten stuk geheugen.

24
00:01:02,310 --> 00:01:04,500
Zeggen dat dit de buffer waar we opgeslagen in ons aanbod.

25
00:01:04,500 --> 00:01:06,910
Er kunnen andere variabelen

26
00:01:06,910 --> 00:01:08,310
direct naast de array gelegen

27
00:01:08,310 --> 00:01:10,060
in het geheugen, dus we kunnen niet

28
00:01:10,060 --> 00:01:12,060
gewoon de array groter.

29
00:01:12,060 --> 00:01:15,700
>> Soms willen we de array snelle toegang tot de gegevens snelheid handel

30
00:01:15,700 --> 00:01:17,650
voor een beetje meer flexibiliteit.

31
00:01:17,650 --> 00:01:20,380
Voer de gelinkte lijst, een andere fundamentele data structuur

32
00:01:20,380 --> 00:01:22,360
u misschien niet zo vertrouwd zijn met.

33
00:01:22,360 --> 00:01:24,200
Op een hoog niveau,

34
00:01:24,200 --> 00:01:26,840
een gekoppelde lijst opgeslagen gegevens in een reeks knooppunten

35
00:01:26,840 --> 00:01:29,280
die met elkaar verbonden met links,

36
00:01:29,280 --> 00:01:31,760
vandaar de naam 'gelinkte lijst.'

37
00:01:31,760 --> 00:01:33,840
Zoals we zullen zien, dit verschil in ontwerp

38
00:01:33,840 --> 00:01:35,500
leidt tot verschillende voordelen en nadelen

39
00:01:35,500 --> 00:01:37,000
dan een array.

40
00:01:37,000 --> 00:01:39,840
>> Hier zijn een paar C-code voor een zeer eenvoudige gelinkte lijst van gehele getallen.

41
00:01:39,840 --> 00:01:42,190
U kunt zien dat we elk knooppunt vertegenwoordigd

42
00:01:42,190 --> 00:01:45,520
in de lijst als een struct die 2 dingen bevat,

43
00:01:45,520 --> 00:01:47,280
een geheel getal op te slaan genaamd 'val'

44
00:01:47,280 --> 00:01:50,460
en een link naar het volgende knooppunt in de lijst

45
00:01:50,460 --> 00:01:52,990
die wij vertegenwoordigen als een pointer genaamd 'volgende'.

46
00:01:54,120 --> 00:01:56,780
Op deze manier kunnen we volgen de hele lijst

47
00:01:56,780 --> 00:01:58,790
met slechts een enkele verwijzing naar de 1e knooppunt,

48
00:01:58,790 --> 00:02:01,270
en dan kunnen we volgen de volgende verwijzingen

49
00:02:01,270 --> 00:02:03,130
de 2e knooppunt,

50
00:02:03,130 --> 00:02:05,280
de 3e knooppunt,

51
00:02:05,280 --> 00:02:07,000
de 4e knooppunt,

52
00:02:07,000 --> 00:02:09,889
en zo verder, totdat we aan het einde van de lijst.

53
00:02:10,520 --> 00:02:12,210
>> Je zou in staat zijn om een ​​voordeel heeft dit te zien

54
00:02:12,210 --> 00:02:14,490
over de statische array structuur - met een gekoppelde lijst,

55
00:02:14,490 --> 00:02:16,450
we niet helemaal behoefte aan een groot deel van het geheugen.

56
00:02:17,400 --> 00:02:20,530
De 1e knooppunt van de lijst zou kunnen leven op deze plaats in het geheugen,

57
00:02:20,530 --> 00:02:23,160
en de 2e knooppunt kan helemaal over hier te zijn.

58
00:02:23,160 --> 00:02:25,780
We kunnen krijgen om alle knooppunten ongeacht waar in het geheugen ze zijn,

59
00:02:25,780 --> 00:02:28,890
want vanaf de 1e node, elke node's volgende pointer

60
00:02:28,890 --> 00:02:31,700
vertelt ons precies waar naar de volgende te gaan.

61
00:02:31,700 --> 00:02:33,670
>> Bovendien hoeven we niet te zeggen van te voren

62
00:02:33,670 --> 00:02:36,740
hoe groot een gekoppelde lijst zal de manier waarop we dat doen met statische arrays zijn,

63
00:02:36,740 --> 00:02:39,060
want we kunnen blijven toevoegen knooppunten om een ​​lijst

64
00:02:39,060 --> 00:02:42,600
zolang er ergens geheugenruimte voor nieuwe knooppunten.

65
00:02:42,600 --> 00:02:45,370
Daarom gelinkte lijsten zijn makkelijk te dynamisch wijzigen.

66
00:02:45,370 --> 00:02:47,950
Zeg, later in het programma moeten we meer knooppunten toe te voegen

67
00:02:47,950 --> 00:02:49,350
aan onze lijst.

68
00:02:49,350 --> 00:02:51,480
Om een ​​nieuw knooppunt te voegen aan onze lijst op de vlieg,

69
00:02:51,480 --> 00:02:53,740
alles wat we hoeven te doen is geheugen toewijzen voor dat knooppunt,

70
00:02:53,740 --> 00:02:55,630
plop in de gegevens waarde,

71
00:02:55,630 --> 00:02:59,070
en plaats het waar we willen door het aanpassen van de betreffende aanwijzingen.

72
00:02:59,070 --> 00:03:02,310
>> Bijvoorbeeld, als we een plaats tussen knooppunt

73
00:03:02,310 --> 00:03:04,020
de 2e en 3e knooppunten van de lijst,

74
00:03:04,020 --> 00:03:06,800
 zouden we niet naar de 2e of 3e nodes bewegen.

75
00:03:06,800 --> 00:03:09,190
Zeggen dat we deze rode knooppunt invoegen.

76
00:03:09,190 --> 00:03:12,890
Alles wat we zouden moeten doen is de nieuwe node volgende pointer

77
00:03:12,890 --> 00:03:14,870
om te wijzen op de 3e knooppunt

78
00:03:14,870 --> 00:03:18,580
en dan opnieuw bedraden de 2e knooppunt volgende pointer

79
00:03:18,580 --> 00:03:20,980
wijzen op nieuwe node.

80
00:03:22,340 --> 00:03:24,370
Dus kunnen we de grootte van onze lijsten op de vlieg

81
00:03:24,370 --> 00:03:26,090
omdat onze computer is niet afhankelijk van indexering,

82
00:03:26,090 --> 00:03:28,990
maar eerder over het koppelen met behulp van pointers op te slaan.

83
00:03:29,120 --> 00:03:31,600
>> Een nadeel van gekoppelde lijsten

84
00:03:31,600 --> 00:03:33,370
is dat anders dan een statische array,

85
00:03:33,370 --> 00:03:36,690
de computer kan niet alleen naar het midden van de lijst.

86
00:03:38,040 --> 00:03:40,780
Omdat de computer moet elk knooppunt bezoeken in de gekoppelde lijst

87
00:03:40,780 --> 00:03:42,330
om naar het volgende,

88
00:03:42,330 --> 00:03:44,770
het gaat om langer duren om een ​​bepaald knooppunt vinden

89
00:03:44,770 --> 00:03:46,400
dan zou in een array.

90
00:03:46,400 --> 00:03:48,660
Om doorkruisen de hele lijst kost tijd evenredig

91
00:03:48,660 --> 00:03:50,580
de lengte van de lijst,

92
00:03:50,580 --> 00:03:54,630
of O (n) in asymptotische notatie.

93
00:03:54,630 --> 00:03:56,510
Gemiddeld bereikt een knooppunt

94
00:03:56,510 --> 00:03:58,800
ook tijd kost evenredig met n.

95
00:03:58,800 --> 00:04:00,700
>> Laten we nu eigenlijk wat code schrijven

96
00:04:00,700 --> 00:04:02,000
die werkt met gelinkte lijsten.

97
00:04:02,000 --> 00:04:04,220
Laten we zeggen dat we willen een gelinkte lijst van gehele getallen.

98
00:04:04,220 --> 00:04:06,140
We kunnen een knooppunt weer te vertegenwoordigen in onze lijst

99
00:04:06,140 --> 00:04:08,340
als struct met twee velden,

100
00:04:08,340 --> 00:04:10,750
een geheel getal genaamd 'val'

101
00:04:10,750 --> 00:04:13,490
en een volgende pointer naar het volgende knooppunt van de lijst.

102
00:04:13,490 --> 00:04:15,660
Nou, lijkt simpel genoeg.

103
00:04:15,660 --> 00:04:17,220
>> Laten we zeggen dat we willen een functie te schrijven

104
00:04:17,220 --> 00:04:19,329
die doorkruist de lijst en drukt de

105
00:04:19,329 --> 00:04:22,150
waarde in het laatste knooppunt van de lijst.

106
00:04:22,150 --> 00:04:24,850
Nou, dat betekent dat we moeten alle knooppunten in de lijst doorlopen

107
00:04:24,850 --> 00:04:27,310
om de laatste een te vinden, maar omdat we niet toe te voegen

108
00:04:27,310 --> 00:04:29,250
of iets te verwijderen, willen we niet veranderen

109
00:04:29,250 --> 00:04:32,210
de interne structuur van de volgende verwijzingen in de lijst.

110
00:04:32,210 --> 00:04:34,790
>> Dus zullen we specifiek behoefte aan een pointer voor traversal

111
00:04:34,790 --> 00:04:36,940
die we zullen noemen 'crawler'.

112
00:04:36,940 --> 00:04:38,870
Het zal kruipen door alle elementen van de lijst

113
00:04:38,870 --> 00:04:41,190
door de keten van volgende verwijzingen.

114
00:04:41,190 --> 00:04:43,750
Alles wat we hebben opgeslagen is een pointer naar de 1e knooppunt,

115
00:04:43,750 --> 00:04:45,730
of 'hoofd' van de lijst.

116
00:04:45,730 --> 00:04:47,370
Hoofd wijst op de 1e node.

117
00:04:47,370 --> 00:04:49,120
Het is van het type pointer-naar-knooppunt.

118
00:04:49,120 --> 00:04:51,280
>> Om de werkelijke 1e knooppunt in de lijst te krijgen,

119
00:04:51,280 --> 00:04:53,250
we dereference deze verwijzing,

120
00:04:53,250 --> 00:04:55,100
maar voordat we kunnen dereference, we moeten controleren

121
00:04:55,100 --> 00:04:57,180
als de wijzer is null eerste.

122
00:04:57,180 --> 00:04:59,190
Als het nul, is de lijst leeg is,

123
00:04:59,190 --> 00:05:01,320
en we moeten printen een bericht dat, omdat de lijst leeg is,

124
00:05:01,320 --> 00:05:03,250
er is geen laatste knooppunt.

125
00:05:03,250 --> 00:05:05,190
Maar, laten we zeggen dat de lijst niet leeg is.

126
00:05:05,190 --> 00:05:08,340
Als het niet, dan moeten we kruipen door de hele lijst

127
00:05:08,340 --> 00:05:10,440
tot we bij de laatste knoop van de lijst,

128
00:05:10,440 --> 00:05:13,030
en hoe kunnen we zien of we kijken naar het laatste knooppunt in de lijst?

129
00:05:13,670 --> 00:05:16,660
>> Nou, als een knooppunt volgende pointer null,

130
00:05:16,660 --> 00:05:18,320
we weten dat we aan het eind

131
00:05:18,320 --> 00:05:22,390
sinds de laatste volgende pointer zou er geen volgende knooppunt in de lijst aan te wijzen.

132
00:05:22,390 --> 00:05:26,590
Het is een goede gewoonte om altijd het laatste knooppunt volgende pointer geïnitialiseerd op nul

133
00:05:26,590 --> 00:05:30,800
een gestandaardiseerde woning die ons waarschuwt als we aan het eind van de lijst te hebben.

134
00:05:30,800 --> 00:05:33,510
>> Dus, als crawler → volgende is null,

135
00:05:34,120 --> 00:05:38,270
vergeet niet dat de pijl syntax is een snelkoppeling voor dereferentie

136
00:05:38,270 --> 00:05:40,010
een pointer naar een struct, dan de toegang tot

137
00:05:40,010 --> 00:05:42,510
haar volgende veld gelijk aan het lastige:

138
00:05:42,510 --> 00:05:48,750
(* Crawler). Volgende.

139
00:05:49,820 --> 00:05:51,260
Zodra we hebben gevonden de laatste knoop,

140
00:05:51,260 --> 00:05:53,830
we willen crawler → val af te drukken,

141
00:05:53,830 --> 00:05:55,000
de waarde in het huidige knooppunt

142
00:05:55,000 --> 00:05:57,130
waarvan we weten dat de laatste.

143
00:05:57,130 --> 00:05:59,740
Anders, als we nog niet op het laatste knooppunt in de lijst,

144
00:05:59,740 --> 00:06:02,340
we hebben om verder te gaan naar het volgende knooppunt in de lijst

145
00:06:02,340 --> 00:06:04,750
en controleer of dat is de laatste.

146
00:06:04,750 --> 00:06:07,010
Om dit te doen, we zetten onze crawler wijzer

147
00:06:07,010 --> 00:06:09,840
wijzen op het huidige knooppunt volgende waarde,

148
00:06:09,840 --> 00:06:11,680
dat wil zeggen het volgende knooppunt in de lijst.

149
00:06:11,680 --> 00:06:13,030
Dit gebeurt door

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → volgende.

151
00:06:16,050 --> 00:06:18,960
Dan herhalen we dit proces, met een lus bijvoorbeeld,

152
00:06:18,960 --> 00:06:20,960
totdat we de laatste knoop.

153
00:06:20,960 --> 00:06:23,150
Dus bijvoorbeeld als crawler wees het hoofd,

154
00:06:24,050 --> 00:06:27,710
we crawler te wijzen op crawler → volgende,

155
00:06:27,710 --> 00:06:30,960
die gelijk is aan het volgende veld van het eerste knooppunt.

156
00:06:30,960 --> 00:06:33,620
Zo, nu onze crawler wijst naar de 2e knooppunt,

157
00:06:33,620 --> 00:06:35,480
en, opnieuw, herhalen we dit met een lus,

158
00:06:37,220 --> 00:06:40,610
totdat we de laatste knoop gevonden, dat wil zeggen,

159
00:06:40,610 --> 00:06:43,640
waar de node volgende pointer wijst op null.

160
00:06:43,640 --> 00:06:45,070
En daar hebben we het,

161
00:06:45,070 --> 00:06:47,620
we hebben gevonden de laatste knooppunt in de lijst, en om de waarde af te drukken,

162
00:06:47,620 --> 00:06:50,800
gebruiken we gewoon crawler → val.

163
00:06:50,800 --> 00:06:53,130
>> Traverseren is niet zo erg, maar hoe zit het met het invoegen van?

164
00:06:53,130 --> 00:06:56,290
Laten we zeggen dat we willen een geheel getal in te voegen in de 4e positie

165
00:06:56,290 --> 00:06:58,040
in een geheel getal lijst.

166
00:06:58,040 --> 00:07:01,280
Dat tussen de huidige 3e en 4e nodes.

167
00:07:01,280 --> 00:07:03,760
Nogmaals, we de lijst doorlopen gewoon

168
00:07:03,760 --> 00:07:06,520
naar de 3e element, degene die we het invoegen na.

169
00:07:06,520 --> 00:07:09,300
Dus hebben we opnieuw een crawler pointer naar de lijst doorkruisen,

170
00:07:09,300 --> 00:07:11,400
controleren of ons hoofd aanwijzer null,

171
00:07:11,400 --> 00:07:14,810
en als het niet zo is, wijzen onze crawler pointer aan het hoofd node.

172
00:07:16,880 --> 00:07:18,060
Dus, we zijn in het 1e element.

173
00:07:18,060 --> 00:07:21,020
We moeten gaan voor 2 meer elementen voordat we kunnen invoegen,

174
00:07:21,020 --> 00:07:23,390
dus we kunnen gebruik maken van een for-lus

175
00:07:23,390 --> 00:07:26,430
int i = 1; i <3; i + +

176
00:07:26,430 --> 00:07:28,590
en elke iteratie van de lus,

177
00:07:28,590 --> 00:07:31,540
vooruit vooruit onze crawler pointer met 1 knoop

178
00:07:31,540 --> 00:07:34,570
controleren of het huidige knooppunt volgende veld nul is,

179
00:07:34,570 --> 00:07:37,550
en als het dat niet is, bewegen onze crawler aanwijzer naar het volgende knooppunt

180
00:07:37,550 --> 00:07:41,810
door het gelijk aan naast de huidige knooppunt aanwijzer.

181
00:07:41,810 --> 00:07:45,210
Dus, omdat onze lus zegt om dat te doen

182
00:07:45,210 --> 00:07:47,550
tweemaal

183
00:07:49,610 --> 00:07:51,190
we hebben bereikt de 3e knooppunt,

184
00:07:51,190 --> 00:07:53,110
en zodra onze crawler pointer heeft bereikt het knooppunt na

185
00:07:53,110 --> 00:07:55,270
die we willen onze nieuwe integer te voegen,

186
00:07:55,270 --> 00:07:57,050
hoe kunnen we eigenlijk de plaatsen?

187
00:07:57,050 --> 00:07:59,440
>> Nou, onze nieuwe integer moet worden ingevoegd in de lijst

188
00:07:59,440 --> 00:08:01,250
als onderdeel van haar eigen knooppunt struct,

189
00:08:01,250 --> 00:08:03,140
aangezien dit echt een reeks knooppunten.

190
00:08:03,140 --> 00:08:05,690
Dus, laten we een nieuwe pointer te leveren aan knooppunt

191
00:08:05,690 --> 00:08:08,910
genaamd 'new_node,'

192
00:08:08,910 --> 00:08:11,800
en zet deze om te wijzen op het geheugen dat we nu kennen

193
00:08:11,800 --> 00:08:14,270
op de hoop voor de knoop zelf,

194
00:08:14,270 --> 00:08:16,000
en hoeveel geheugen hebben we nodig om toe te wijzen?

195
00:08:16,000 --> 00:08:18,250
En de grootte van een knooppunt,

196
00:08:20,450 --> 00:08:23,410
en we willen haar val veld is ingesteld op het gehele getal dat we willen invoegen.

197
00:08:23,410 --> 00:08:25,590
Laten we zeggen, 6.

198
00:08:25,590 --> 00:08:27,710
Nu, het knooppunt omvat ons geheel getal.

199
00:08:27,710 --> 00:08:30,650
Het is ook een goede gewoonte om te initialiseren van de nieuwe node volgende veld

200
00:08:30,650 --> 00:08:33,690
te wijzen op null,

201
00:08:33,690 --> 00:08:35,080
maar wat nu?

202
00:08:35,080 --> 00:08:37,179
>> We moeten de interne structuur van de lijst te wijzigen

203
00:08:37,179 --> 00:08:40,409
en de volgende verwijzingen in de bestaande van de lijst

204
00:08:40,409 --> 00:08:42,950
3e en 4e nodes.

205
00:08:42,950 --> 00:08:46,560
Omdat de volgende verwijzingen bepalen de volgorde van de lijst,

206
00:08:46,560 --> 00:08:48,650
en aangezien we het plaatsen van onze nieuwe knooppunt

207
00:08:48,650 --> 00:08:50,510
recht in het midden van de lijst,

208
00:08:50,510 --> 00:08:52,010
het kan een beetje lastig.

209
00:08:52,010 --> 00:08:54,250
Dit is te onthouden, omdat,, onze computer

210
00:08:54,250 --> 00:08:56,250
alleen weet waar knooppunten in de lijst

211
00:08:56,250 --> 00:09:00,400
door de volgende verwijzingen opgeslagen in de vorige nodes.

212
00:09:00,400 --> 00:09:03,940
Dus, als we ooit verloren spoor van een van deze locaties,

213
00:09:03,940 --> 00:09:06,860
zeggen door het veranderen van een van de volgende verwijzingen in onze lijst,

214
00:09:06,860 --> 00:09:09,880
bijvoorbeeld zeggen dat we veranderd

215
00:09:09,880 --> 00:09:12,920
de 3e knooppunt volgende veld

216
00:09:12,920 --> 00:09:15,610
om te wijzen op een aantal knooppunten hier.

217
00:09:15,610 --> 00:09:17,920
We zouden pech, want we zouden niet

218
00:09:17,920 --> 00:09:20,940
enig idee waar de rest van de lijst te vinden,

219
00:09:20,940 --> 00:09:23,070
en dat is natuurlijk heel slecht.

220
00:09:23,070 --> 00:09:25,080
Dus, we moeten echt voorzichtig zijn over de volgorde

221
00:09:25,080 --> 00:09:28,360
waarin we manipuleren onze volgende aanwijzingen tijdens het inbrengen.

222
00:09:28,360 --> 00:09:30,540
>> Dus, om dit te vereenvoudigen, laten we zeggen dat

223
00:09:30,540 --> 00:09:32,220
onze eerste 4 knopen

224
00:09:32,220 --> 00:09:36,200
genoemd A, B, C en D, met de pijlen die de keten van pointers

225
00:09:36,200 --> 00:09:38,070
de knooppunten verbinden.

226
00:09:38,070 --> 00:09:40,050
Dus, moeten we onze nieuwe knooppunt plaatst

227
00:09:40,050 --> 00:09:42,070
tussen knooppunten C en D.

228
00:09:42,070 --> 00:09:45,060
Het is essentieel om het te doen in de juiste volgorde, en ik zal je laten zien waarom.

229
00:09:45,060 --> 00:09:47,500
>> Laten we eens kijken naar de verkeerde weg naar de eerste te doen.

230
00:09:47,500 --> 00:09:49,490
Hey, we weten dat de nieuwe node heeft het recht te komen na C,

231
00:09:49,490 --> 00:09:51,910
dus laten we stellen volgende pointer C's

232
00:09:51,910 --> 00:09:54,700
te wijzen op new_node.

233
00:09:56,530 --> 00:09:59,180
Oke, oke lijkt, we moeten nu af te maken door

234
00:09:59,180 --> 00:10:01,580
het maken van de nieuwe node volgende pointer wijzen naar D,

235
00:10:01,580 --> 00:10:03,250
maar wacht, hoe kunnen we dat doen?

236
00:10:03,250 --> 00:10:05,170
Het enige dat ons kan vertellen waar D was,

237
00:10:05,170 --> 00:10:07,630
werd de volgende pointer eerder opgeslagen in C,

238
00:10:07,630 --> 00:10:09,870
maar we herschreven dat wijzer

239
00:10:09,870 --> 00:10:11,170
verwijzen naar de nieuwe knooppunt

240
00:10:11,170 --> 00:10:14,230
dus we hebben niet langer enig idee waar D is in het geheugen,

241
00:10:14,230 --> 00:10:17,020
en we hebben verloren de rest van de lijst.

242
00:10:17,020 --> 00:10:19,000
Helemaal niet goed.

243
00:10:19,000 --> 00:10:21,090
>> Dus, hoe doen we dit recht?

244
00:10:22,360 --> 00:10:25,090
Ten eerste, richt de nieuwe node volgende pointer bij D.

245
00:10:26,170 --> 00:10:28,990
Nu zowel het nieuwe knooppunt C en de volgende verwijzingen

246
00:10:28,990 --> 00:10:30,660
verwijzen naar dezelfde knooppunt D,

247
00:10:30,660 --> 00:10:32,290
maar dat is prima.

248
00:10:32,290 --> 00:10:35,680
Nu kunnen we wijzen volgende pointer C's op de nieuwe node.

249
00:10:37,450 --> 00:10:39,670
Dus hebben we dit gedaan zonder gegevens te verliezen.

250
00:10:39,670 --> 00:10:42,280
In code, C is het huidige knooppunt

251
00:10:42,280 --> 00:10:45,540
dat de traversal wijzer crawler wordt verwezen,

252
00:10:45,540 --> 00:10:50,400
en D wordt vertegenwoordigd door het knooppunt naar wijst naast het huidige knooppunt veld,

253
00:10:50,400 --> 00:10:52,600
of rupsbanden → volgende.

254
00:10:52,600 --> 00:10:55,460
Dus, we eerst de nieuwe node volgende pointer

255
00:10:55,460 --> 00:10:57,370
om te wijzen op crawler → volgende,

256
00:10:57,370 --> 00:11:00,880
op dezelfde manier waarop we zeiden volgende pointer new_node's moeten

257
00:11:00,880 --> 00:11:02,780
wijzen op D in de afbeelding.

258
00:11:02,780 --> 00:11:04,540
Dan kunnen we het huidige knooppunt van de volgende pointer

259
00:11:04,540 --> 00:11:06,330
op onze nieuwe knooppunt,

260
00:11:06,330 --> 00:11:10,980
net zoals we moesten wachten om C wijzen op new_node in de tekening.

261
00:11:10,980 --> 00:11:12,250
Nu alles is in orde, en we hebben niet verliezen

262
00:11:12,250 --> 00:11:14,490
bijhouden van alle gegevens, en we waren in staat om gewoon

263
00:11:14,490 --> 00:11:16,200
blijven nieuwe knoop in het midden van de lijst

264
00:11:16,200 --> 00:11:19,330
zonder de wederopbouw van de hele zaak, of zelfs verschuiven alle elementen

265
00:11:19,330 --> 00:11:22,490
de manier waarop we zouden hebben gehad om met een vaste lengte array.

266
00:11:22,490 --> 00:11:26,020
>> Dus, gelinkte lijsten zijn een eenvoudige, maar belangrijke, dynamische datastructuur

267
00:11:26,020 --> 00:11:29,080
die zowel voor-en nadelen

268
00:11:29,080 --> 00:11:31,260
vergelijking met arrays en andere datastructuren,

269
00:11:31,260 --> 00:11:33,350
en zoals vaak het geval is in de informatica,

270
00:11:33,350 --> 00:11:35,640
is het belangrijk om te weten wanneer elk instrument te gebruiken,

271
00:11:35,640 --> 00:11:37,960
zodat u kunt kiezen het juiste gereedschap voor de juiste baan.

272
00:11:37,960 --> 00:11:40,060
>> Voor meer oefening, proberen het schrijven van functies

273
00:11:40,060 --> 00:11:42,080
knooppunten verwijderen uit een gekoppelde lijst -

274
00:11:42,080 --> 00:11:44,050
vergeet niet om voorzichtig te zijn over de volgorde waarin u herschikken

275
00:11:44,050 --> 00:11:47,430
uw volgende aanwijzingen om ervoor te zorgen dat je niet een stuk van uw lijst te verliezen -

276
00:11:47,430 --> 00:11:50,200
of een functie aan de knooppunten tellen in een verbonden lijst,

277
00:11:50,200 --> 00:11:53,280
of een leuke een, de volgorde van alle knooppunten in een gekoppelde lijst keren.

278
00:11:53,280 --> 00:11:56,090
>> Mijn naam is Jackson Steinkamp, ​​dit is CS50.