1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] In programmering, moet ons dikwels lyste van waardes te verteenwoordig,

2
00:00:10,050 --> 00:00:12,840
soos die name van studente in 'n artikel

3
00:00:12,840 --> 00:00:15,100
of hul tellings op die jongste quiz.

4
00:00:15,100 --> 00:00:17,430
>> In die C-taal, verklaar skikkings kan gebruik word

5
00:00:17,430 --> 00:00:19,160
lyste te stoor.

6
00:00:19,160 --> 00:00:21,200
Dit is maklik om die elemente van 'n lys op te noem wat in ons omstreken

7
00:00:21,200 --> 00:00:23,390
in 'n skikking gestoor, en as jy nodig het om toegang te verkry tot

8
00:00:23,390 --> 00:00:25,050
of verander die ith lys element

9
00:00:25,050 --> 00:00:27,570
vir 'n paar arbitrêre indeks Ek,

10
00:00:27,570 --> 00:00:29,910
wat gedoen kan word in konstante tyd,

11
00:00:29,910 --> 00:00:31,660
maar skikkings nadele ook.

12
00:00:31,660 --> 00:00:33,850
>> Wanneer ons hulle verklaar, is ons verplig om te sê

13
00:00:33,850 --> 00:00:35,900
aan die voorkant hoe groot hulle is,

14
00:00:35,900 --> 00:00:38,160
dit is, hoeveel elemente hulle kan stoor

15
00:00:38,160 --> 00:00:40,780
en hoe groot hierdie elemente is, wat bepaal word deur hul soort.

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

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

18
00:00:48,220 --> 00:00:50,200
wat is die grootte van 'n int.

19
00:00:50,200 --> 00:00:52,590
>> Ons kan nie 'n skikking se grootte verander na die verklaring.

20
00:00:52,590 --> 00:00:55,290
Ons het 'n nuwe skikking te maak as ons wil meer elemente te stoor.

21
00:00:55,290 --> 00:00:57,410
Die rede waarom hierdie beperking bestaan, is dat ons

22
00:00:57,410 --> 00:00:59,040
program slaan die hele reeks

23
00:00:59,040 --> 00:01:02,310
as 'n aangrensende stuk van die geheue.

24
00:01:02,310 --> 00:01:04,500
Sê dit is die buffer waar ons in ons skikking gestoor.

25
00:01:04,500 --> 00:01:06,910
Daar is dalk ander veranderlikes

26
00:01:06,910 --> 00:01:08,310
geleë reg langs die skikking

27
00:01:08,310 --> 00:01:10,060
in die geheue, so ons kan nie

28
00:01:10,060 --> 00:01:12,060
maak net die skikking groter.

29
00:01:12,060 --> 00:01:15,700
>> Soms het ons wil die skikking se vinnige data toegang spoed om handel te dryf

30
00:01:15,700 --> 00:01:17,650
vir 'n bietjie meer buigsaamheid.

31
00:01:17,650 --> 00:01:20,380
Gee die geskakelde lys, 'n ander basiese data struktuur

32
00:01:20,380 --> 00:01:22,360
jy dalk nie so vertroud met.

33
00:01:22,360 --> 00:01:24,200
Op 'n hoë vlak,

34
00:01:24,200 --> 00:01:26,840
'n geskakelde lys stoor data in 'n reeks van nodes

35
00:01:26,840 --> 00:01:29,280
wat met mekaar verbind is met skakels,

36
00:01:29,280 --> 00:01:31,760
vandaar die naam "geskakelde lys."

37
00:01:31,760 --> 00:01:33,840
Soos ons sal sien, is hierdie verskil in die ontwerp

38
00:01:33,840 --> 00:01:35,500
lei tot verskillende voordele en nadele

39
00:01:35,500 --> 00:01:37,000
as 'n skikking.

40
00:01:37,000 --> 00:01:39,840
>> Hier is 'n paar C-kode vir 'n baie eenvoudige geskakelde lys van heelgetalle.

41
00:01:39,840 --> 00:01:42,190
Jy kan sien dat ons elke node verteenwoordig

42
00:01:42,190 --> 00:01:45,520
in die lys as 'n struct wat bevat 2 dinge,

43
00:01:45,520 --> 00:01:47,280
'n heelgetal te slaan genaamd "val"

44
00:01:47,280 --> 00:01:50,460
en 'n skakel na die volgende nodus in die lys

45
00:01:50,460 --> 00:01:52,990
wat ons verteenwoordig, as 'n wyser 'langs. "

46
00:01:54,120 --> 00:01:56,780
Hierdie manier kan ons hou die hele lys

47
00:01:56,780 --> 00:01:58,790
met net 'n enkele wyser aan die 1ste node,

48
00:01:58,790 --> 00:02:01,270
en dan kan ons die volgende wenke volg

49
00:02:01,270 --> 00:02:03,130
na die 2de node,

50
00:02:03,130 --> 00:02:05,280
na die 3de node,

51
00:02:05,280 --> 00:02:07,000
na die 4de node,

52
00:02:07,000 --> 00:02:09,889
en so aan, totdat ons aan die einde van die lys.

53
00:02:10,520 --> 00:02:12,210
>> Jy mag dalk in staat wees om 1 voordeel dit het om te sien

54
00:02:12,210 --> 00:02:14,490
oor die statiese verskeidenheid struktuur - met 'n geskakelde lys,

55
00:02:14,490 --> 00:02:16,450
ons hoef nie 'n groot stuk van die geheue heeltemal.

56
00:02:17,400 --> 00:02:20,530
Die 1ste node van die lys kan lewe op hierdie plek in die geheue,

57
00:02:20,530 --> 00:02:23,160
en die 2de node kon al die pad hier.

58
00:02:23,160 --> 00:02:25,780
Ons kan kry om al die nodusse maak nie saak waar hulle is in die geheue,

59
00:02:25,780 --> 00:02:28,890
omdat begin op die 1ste node, elke node se volgende wyser

60
00:02:28,890 --> 00:02:31,700
vertel ons presies waar om volgende te gaan.

61
00:02:31,700 --> 00:02:33,670
>> Daarbenewens, het ons nie om te sê aan die voorkant

62
00:02:33,670 --> 00:02:36,740
hoe groot 'n geskakelde lys sal die manier waarop ons met statiese skikkings,

63
00:02:36,740 --> 00:02:39,060
want ons kan hou nodes op 'n lys voeg

64
00:02:39,060 --> 00:02:42,600
so lank as wat daar is ruimte iewers in die geheue vir 'n nuwe nodes.

65
00:02:42,600 --> 00:02:45,370
Daarom, geskakelde lyste is maklik om dinamiese grootte.

66
00:02:45,370 --> 00:02:47,950
Sê, later in die program wat ons moet meer nodes te voeg

67
00:02:47,950 --> 00:02:49,350
in ons lys.

68
00:02:49,350 --> 00:02:51,480
'N nuwe node in ons lys in te voeg op die vlieg,

69
00:02:51,480 --> 00:02:53,740
al wat ons hoef te doen, is geheue toeken vir daardie node,

70
00:02:53,740 --> 00:02:55,630
plons in die data waarde,

71
00:02:55,630 --> 00:02:59,070
en plaas dit dan waar ons wil deur die aanpassing van die toepaslike verwysings.

72
00:02:59,070 --> 00:03:02,310
>> Byvoorbeeld, as ons wou 'n node te plaas tussen

73
00:03:02,310 --> 00:03:04,020
die 2de en 3de nodes van die lys,

74
00:03:04,020 --> 00:03:06,800
 ons wil nie hê die 2de of 3de nodes te skuif.

75
00:03:06,800 --> 00:03:09,190
Sê dat ons is die invoeging van die rooi node.

76
00:03:09,190 --> 00:03:12,890
Al wat ons wil hê om dit te doen is die nuwe node se volgende wyser

77
00:03:12,890 --> 00:03:14,870
om te wys op die 3de node

78
00:03:14,870 --> 00:03:18,580
en dan ReWire die 2de node se volgende wyser

79
00:03:18,580 --> 00:03:20,980
om te verwys na ons nuwe node.

80
00:03:22,340 --> 00:03:24,370
Dus, kan ons die grootte van ons lyste op die vlieg

81
00:03:24,370 --> 00:03:26,090
sedert ons rekenaar nie staatmaak op indeksering,

82
00:03:26,090 --> 00:03:28,990
maar eerder op 'n skakel met wenke om hulle te slaan.

83
00:03:29,120 --> 00:03:31,600
>> Egter 'n nadeel van geskakelde lyste

84
00:03:31,600 --> 00:03:33,370
is dat, in teenstelling met 'n statiese skikking,

85
00:03:33,370 --> 00:03:36,690
die rekenaar kan nie net spring na die middel van die lys.

86
00:03:38,040 --> 00:03:40,780
Sedert die rekenaar het elke node te besoek in die geskakelde lys

87
00:03:40,780 --> 00:03:42,330
te kry na die volgende een,

88
00:03:42,330 --> 00:03:44,770
dit gaan langer neem om 'n spesifieke node te vind

89
00:03:44,770 --> 00:03:46,400
as wat dit sou in 'n skikking.

90
00:03:46,400 --> 00:03:48,660
Die hele lys te verken neem tyd eweredig

91
00:03:48,660 --> 00:03:50,580
die lengte van die lys,

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

93
00:03:54,630 --> 00:03:56,510
Op die gemiddelde, die bereik van enige node

94
00:03:56,510 --> 00:03:58,800
ook neem tyd eweredig aan n.

95
00:03:58,800 --> 00:04:00,700
>> Nou, laat ons eintlik skryf 'n paar kode

96
00:04:00,700 --> 00:04:02,000
wat werk met geskakelde lyste.

97
00:04:02,000 --> 00:04:04,220
Kom ons sê ons wil 'n geskakelde lys van heelgetalle.

98
00:04:04,220 --> 00:04:06,140
Ons kan 'n node verteenwoordig weer in ons lys

99
00:04:06,140 --> 00:04:08,340
as 'n struct met 2 velde,

100
00:04:08,340 --> 00:04:10,750
'n heelgetal waarde genoem "val"

101
00:04:10,750 --> 00:04:13,490
en 'n volgende wyser na die volgende node van die lys.

102
00:04:13,490 --> 00:04:15,660
Wel, lyk eenvoudig genoeg.

103
00:04:15,660 --> 00:04:17,220
>> Kom ons sê ons wil 'n funksie te skryf

104
00:04:17,220 --> 00:04:19,329
wat deurkruis die lys en druk die

105
00:04:19,329 --> 00:04:22,150
waarde gestoor in die laaste node van die lys.

106
00:04:22,150 --> 00:04:24,850
Wel, dit beteken dat ons sal moet al die nodusse in die lys te verken

107
00:04:24,850 --> 00:04:27,310
die laaste een te vind, maar omdat ons nie toe te voeg

108
00:04:27,310 --> 00:04:29,250
of verwyder enigiets, doen ons nie wil verander

109
00:04:29,250 --> 00:04:32,210
die interne struktuur van die volgende wenke in die lys.

110
00:04:32,210 --> 00:04:34,790
>> So, sal ons 'n wyser spesifiek nodig het vir traversal

111
00:04:34,790 --> 00:04:36,940
wat ons noem "kruiper.

112
00:04:36,940 --> 00:04:38,870
Dit sal deur al die elemente van die lys kruip

113
00:04:38,870 --> 00:04:41,190
deur die ketting van die volgende wenke.

114
00:04:41,190 --> 00:04:43,750
Al wat ons het gestoor is 'n wyser na die 1ste node,

115
00:04:43,750 --> 00:04:45,730
of "kop" van die lys.

116
00:04:45,730 --> 00:04:47,370
Hoof punte na die 1ste node.

117
00:04:47,370 --> 00:04:49,120
Dit is van die tipe pointer-tot-node.

118
00:04:49,120 --> 00:04:51,280
>> Die werklike 1ste node in die lys te kry,

119
00:04:51,280 --> 00:04:53,250
ons moet dereference hierdie pointer,

120
00:04:53,250 --> 00:04:55,100
maar voordat ons dit kan dereference, ons nodig het om te kyk

121
00:04:55,100 --> 00:04:57,180
indien die wyser is null eerste.

122
00:04:57,180 --> 00:04:59,190
As dit is null, die lys is leeg,

123
00:04:59,190 --> 00:05:01,320
en ons moet die druk van 'n boodskap dat, omdat die lys is leeg,

124
00:05:01,320 --> 00:05:03,250
Daar is geen verlede node.

125
00:05:03,250 --> 00:05:05,190
Maar, laat ons sê dat die lys nie is leeg.

126
00:05:05,190 --> 00:05:08,340
As dit is nie, dan moet ons kruip deur die hele lys

127
00:05:08,340 --> 00:05:10,440
totdat ons kry om te die laaste knoop van die lys,

128
00:05:10,440 --> 00:05:13,030
en hoe kan ons sê as ons kyk na die laaste nodus in die lys?

129
00:05:13,670 --> 00:05:16,660
>> Wel, as 'n node se volgende wyser is van nul,

130
00:05:16,660 --> 00:05:18,320
ons weet ons is aan die einde

131
00:05:18,320 --> 00:05:22,390
sedert die laaste volgende wyser sou geen volgende nodus in die lys te wys.

132
00:05:22,390 --> 00:05:26,590
Dit is goeie praktyk om altyd die laaste node se volgende wyser geïnisialiseer aan nul

133
00:05:26,590 --> 00:05:30,800
'n gestandaardiseerde eiendom wat waarskuwings wanneer ons die einde van die lys bereik het.

134
00:05:30,800 --> 00:05:33,510
>> So, as kruiper → volgende is null,

135
00:05:34,120 --> 00:05:38,270
onthou dat die pyltjie sintaksis is 'n kortpad vir ontwysing

136
00:05:38,270 --> 00:05:40,010
'n wyser na 'n struct, dan toegang tot

137
00:05:40,010 --> 00:05:42,510
sy volgende veld gelykstaande aan die ongemaklike:

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

139
00:05:49,820 --> 00:05:51,260
Sodra ons het gevind die laaste knoop,

140
00:05:51,260 --> 00:05:53,830
ons wil kruiper → val te druk,

141
00:05:53,830 --> 00:05:55,000
die waarde in die huidige node

142
00:05:55,000 --> 00:05:57,130
wat ons weet is die laaste een.

143
00:05:57,130 --> 00:05:59,740
Andersins, as ons nog nie by die laaste nodus in die lys,

144
00:05:59,740 --> 00:06:02,340
ons het om aan te beweeg na die volgende nodus in die lys

145
00:06:02,340 --> 00:06:04,750
en kyk of dit is die laaste een.

146
00:06:04,750 --> 00:06:07,010
Om dit te doen, het ons net ons kruiper pointer

147
00:06:07,010 --> 00:06:09,840
om te verwys na die huidige node se waarde,

148
00:06:09,840 --> 00:06:11,680
dit is die volgende nodus in die lys.

149
00:06:11,680 --> 00:06:13,030
Dit word gedoen deur die oprigting

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

151
00:06:16,050 --> 00:06:18,960
Dan sal ons hierdie proses herhaal, met 'n lus byvoorbeeld,

152
00:06:18,960 --> 00:06:20,960
totdat ons vind die laaste knoop.

153
00:06:20,960 --> 00:06:23,150
So, byvoorbeeld, indien kruiper wys aan kop,

154
00:06:24,050 --> 00:06:27,710
ons kruiper te wys aan kruiper → volgende,

155
00:06:27,710 --> 00:06:30,960
wat dieselfde is as die volgende gebied van die 1ste node.

156
00:06:30,960 --> 00:06:33,620
So, nou is ons kruiper verwys na die 2de node,

157
00:06:33,620 --> 00:06:35,480
en weer, ons herhaal dit met 'n lus,

158
00:06:37,220 --> 00:06:40,610
totdat ons die laaste knoop gevind het, dit is,

159
00:06:40,610 --> 00:06:43,640
waar die node se volgende wyser wys aan nul.

160
00:06:43,640 --> 00:06:45,070
En daar het ons dit,

161
00:06:45,070 --> 00:06:47,620
het ons gevind die laaste nodus in die lys, en die waarde daarvan te druk,

162
00:06:47,620 --> 00:06:50,800
gebruik ons ​​net kruiper → val.

163
00:06:50,800 --> 00:06:53,130
>> Dwarsbalke is nie so sleg nie, maar wat oor die invoeging van?

164
00:06:53,130 --> 00:06:56,290
Kom ons sê ons wil 'n heelgetal in die 4de posisie in te voeg

165
00:06:56,290 --> 00:06:58,040
in 'n heelgetal lys.

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

167
00:07:01,280 --> 00:07:03,760
Weereens, ons het die lys om net te verken

168
00:07:03,760 --> 00:07:06,520
kry die 3de element, die een wat ons invoeging na.

169
00:07:06,520 --> 00:07:09,300
Dus, het ons weer 'n kruiper wyser om die lys te verken,

170
00:07:09,300 --> 00:07:11,400
seker as ons kop null,

171
00:07:11,400 --> 00:07:14,810
en as dit nie, wys ons kruiper wyser op die kop node.

172
00:07:16,880 --> 00:07:18,060
So, ons is op die 1ste element.

173
00:07:18,060 --> 00:07:21,020
Ons het 2 meer elemente om te gaan vorentoe voordat ons kan plaas,

174
00:07:21,020 --> 00:07:23,390
sodat ons dit kan gebruik om 'n 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 in elke iterasie van die lus,

177
00:07:28,590 --> 00:07:31,540
bevorder ons kruiper wyser deur 1 node

178
00:07:31,540 --> 00:07:34,570
deur te kyk as die huidige node se volgende veld, is van nul,

179
00:07:34,570 --> 00:07:37,550
en as dit nie, ons kruiper wyser beweeg na die volgende node

180
00:07:37,550 --> 00:07:41,810
deur dit gelyk is aan die huidige node se volgende wyser.

181
00:07:41,810 --> 00:07:45,210
So, aangesien ons vir lus sê om dit te doen

182
00:07:45,210 --> 00:07:47,550
twee keer,

183
00:07:49,610 --> 00:07:51,190
het ons bereik die 3de node,

184
00:07:51,190 --> 00:07:53,110
en sodra ons kruiper wyser het die knoop bereik nadat

185
00:07:53,110 --> 00:07:55,270
wat ons wil ons nuwe heelgetal te voeg,

186
00:07:55,270 --> 00:07:57,050
hoe ons eintlik nie die invoeging?

187
00:07:57,050 --> 00:07:59,440
>> Wel, ons nuwe heelgetal word ingevoeg in die lys

188
00:07:59,440 --> 00:08:01,250
as deel van sy eie node struct,

189
00:08:01,250 --> 00:08:03,140
want dit is regtig 'n reeks van nodes.

190
00:08:03,140 --> 00:08:05,690
So, kom ons maak 'n nuwe wyser node

191
00:08:05,690 --> 00:08:08,910
genoem "new_node,

192
00:08:08,910 --> 00:08:11,800
en sit dit om te verwys na geheue wat ons nou ken

193
00:08:11,800 --> 00:08:14,270
op die hoop vir die knoop self,

194
00:08:14,270 --> 00:08:16,000
en hoeveel geheue moet ons ken?

195
00:08:16,000 --> 00:08:18,250
Wel, die grootte van 'n node,

196
00:08:20,450 --> 00:08:23,410
en ons wil sy val veld te stel aan die heelgetal wat ons wil voeg.

197
00:08:23,410 --> 00:08:25,590
Kom ons sê, 6.

198
00:08:25,590 --> 00:08:27,710
Nou, die node bevat ons heelgetalwaarde.

199
00:08:27,710 --> 00:08:30,650
Dit is ook 'n goeie praktyk om die nuwe node se volgende veld te inisialiseer

200
00:08:30,650 --> 00:08:33,690
om te wys aan nul,

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

202
00:08:35,080 --> 00:08:37,179
>> Ons het die interne struktuur van die lys te verander

203
00:08:37,179 --> 00:08:40,409
en die volgende verwysings in die lys se bestaande

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

205
00:08:42,950 --> 00:08:46,560
Sedert die volgende wenke bepaal die volgorde van die lys,

206
00:08:46,560 --> 00:08:48,650
en omdat ons die invoeging van ons nuwe node

207
00:08:48,650 --> 00:08:50,510
reg in die middel van die lys,

208
00:08:50,510 --> 00:08:52,010
dit kan 'n bietjie lastig.

209
00:08:52,010 --> 00:08:54,250
Dit is omdat, onthou, ons rekenaar

210
00:08:54,250 --> 00:08:56,250
weet net die plek van die nodusse in die lys

211
00:08:56,250 --> 00:09:00,400
as gevolg van die volgende wenke gestoor in die vorige nodes.

212
00:09:00,400 --> 00:09:03,940
Dus, as ons ooit verlore spoor van enige van hierdie plekke,

213
00:09:03,940 --> 00:09:06,860
sê deur die verandering van een van die volgende wenke in ons lys,

214
00:09:06,860 --> 00:09:09,880
byvoorbeeld, sê ons verander

215
00:09:09,880 --> 00:09:12,920
die 3de node se volgende veld

216
00:09:12,920 --> 00:09:15,610
om te verwys na 'n node hier.

217
00:09:15,610 --> 00:09:17,920
Ons sal uit van geluk, want ons wil nie

218
00:09:17,920 --> 00:09:20,940
'n idee waar die res van die lys te vind,

219
00:09:20,940 --> 00:09:23,070
en dit is natuurlik regtig sleg is.

220
00:09:23,070 --> 00:09:25,080
So, ons moet baie versigtig oor die volgorde

221
00:09:25,080 --> 00:09:28,360
wat ons manipuleer ons volgende wenke tydens die invoeging.

222
00:09:28,360 --> 00:09:30,540
>> So, om dit te vereenvoudig, laat ons sê dat

223
00:09:30,540 --> 00:09:32,220
ons eerste 4 nodes

224
00:09:32,220 --> 00:09:36,200
A, B, C, en D is geroep, met die pyle wat die ketting van verwysings

225
00:09:36,200 --> 00:09:38,070
wat die nodusse verbind.

226
00:09:38,070 --> 00:09:40,050
So, moet ons ons nuwe node te voeg

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

228
00:09:42,070 --> 00:09:45,060
Dit is van kritieke belang om dit te doen in die korrekte volgorde, en ek sal jou wys hoekom.

229
00:09:45,060 --> 00:09:47,500
>> Kom ons kyk op die verkeerde manier om dit eers te doen.

230
00:09:47,500 --> 00:09:49,490
Hey, ons weet dat die nuwe node het om reg te kom na C,

231
00:09:49,490 --> 00:09:51,910
so laat ons stel C se volgende wyser

232
00:09:51,910 --> 00:09:54,700
om te wys te new_node.

233
00:09:56,530 --> 00:09:59,180
Alle reg, lyk okay, ons het net eenvoudig te voltooi nou deur

234
00:09:59,180 --> 00:10:01,580
die maak van die nuwe node se volgende wyser punt D

235
00:10:01,580 --> 00:10:03,250
Maar wag, hoe kan ons dit doen?

236
00:10:03,250 --> 00:10:05,170
Die enigste ding wat ons kan vertel waar D was,

237
00:10:05,170 --> 00:10:07,630
is die volgende wyser voorheen gestoor in C,

238
00:10:07,630 --> 00:10:09,870
maar ons het net oorgeskryf dat wyser

239
00:10:09,870 --> 00:10:11,170
om te verwys na die nuwe node,

240
00:10:11,170 --> 00:10:14,230
sodat ons nie meer 'n clue waar D is in die geheue,

241
00:10:14,230 --> 00:10:17,020
en ons het die res van die lys verloor.

242
00:10:17,020 --> 00:10:19,000
Glad nie goed nie.

243
00:10:19,000 --> 00:10:21,090
>> So, hoe doen ons dit reg?

244
00:10:22,360 --> 00:10:25,090
Eerstens, wys die nuwe node se volgende wyser by D.

245
00:10:26,170 --> 00:10:28,990
Nou, beide die nuwe node's en C's volgende verwysings

246
00:10:28,990 --> 00:10:30,660
wys na dieselfde node, D,

247
00:10:30,660 --> 00:10:32,290
maar dit is goed.

248
00:10:32,290 --> 00:10:35,680
Nou kan ons wys C se volgende wyser op die nuwe node.

249
00:10:37,450 --> 00:10:39,670
So, ons het dit gedoen sonder om enige data te verloor.

250
00:10:39,670 --> 00:10:42,280
In die kode, C is die huidige node

251
00:10:42,280 --> 00:10:45,540
dat die traversal pointer kruiper wys,

252
00:10:45,540 --> 00:10:50,400
en D word verteenwoordig deur die node uitgewys deur die huidige node se volgende veld,

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

254
00:10:52,600 --> 00:10:55,460
So, moet ons eers die nuwe node se volgende wyser

255
00:10:55,460 --> 00:10:57,370
te wys aan kruiper → volgende,

256
00:10:57,370 --> 00:11:00,880
op dieselfde manier het ons gesê new_node se volgende wyser

257
00:11:00,880 --> 00:11:02,780
verwys na D in die illustrasie.

258
00:11:02,780 --> 00:11:04,540
Dan kan ons stel die huidige node se volgende wyser

259
00:11:04,540 --> 00:11:06,330
na ons nuwe node,

260
00:11:06,330 --> 00:11:10,980
net soos ons het om te wag tot punt C new_node in die tekening.

261
00:11:10,980 --> 00:11:12,250
Nou is alles in orde, en ons het nie verloor nie

262
00:11:12,250 --> 00:11:14,490
hou van enige data, en ons was in staat om net

263
00:11:14,490 --> 00:11:16,200
hou ons nuwe node in die middel van die lys

264
00:11:16,200 --> 00:11:19,330
sonder om die hele ding te herbou of selfs verskuiwing enige elemente

265
00:11:19,330 --> 00:11:22,490
die manier waarop ons sou gehad het om met 'n vaste-lengte skikking.

266
00:11:22,490 --> 00:11:26,020
>> So, geskakelde lyste is 'n basiese, maar belangrike, dinamiese data struktuur

267
00:11:26,020 --> 00:11:29,080
wat beide voordele en nadele

268
00:11:29,080 --> 00:11:31,260
in vergelyking met skikkings en ander data strukture,

269
00:11:31,260 --> 00:11:33,350
en so dikwels die geval in die rekenaar wetenskap,

270
00:11:33,350 --> 00:11:35,640
Dit is belangrik om te weet wanneer om elke instrument te gebruik,

271
00:11:35,640 --> 00:11:37,960
sodat jy kan kies die regte gereedskap vir die regte werk.

272
00:11:37,960 --> 00:11:40,060
>> Vir meer oefening, probeer skryf funksies te

273
00:11:40,060 --> 00:11:42,080
verwyder nodes van 'n geskakelde lys -

274
00:11:42,080 --> 00:11:44,050
onthou om versigtig te wees oor die volgorde waarin jy herrangskik

275
00:11:44,050 --> 00:11:47,430
jou volgende wenke om seker te maak dat jy nie 'n stuk van jou lys verloor -

276
00:11:47,430 --> 00:11:50,200
of 'n funksie om die nodusse in 'n geskakelde lys te tel,

277
00:11:50,200 --> 00:11:53,280
of 'n prettige, die einde van al die nodusse in 'n geskakelde lys om te keer.

278
00:11:53,280 --> 00:11:56,090
>> My naam is Jackson STEINKAMP, dit is CS50.