1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] I programmering, vi ofte behov for å representere lister over verdier,

2
00:00:10,050 --> 00:00:12,840
slik som navn på elevene i en del

3
00:00:12,840 --> 00:00:15,100
eller deres score på den siste quiz.

4
00:00:15,100 --> 00:00:17,430
>> I C-språk, erklærte arrayer kan brukes

5
00:00:17,430 --> 00:00:19,160
for å lagre lister.

6
00:00:19,160 --> 00:00:21,200
Det er lett å oppsummere elementene i en liste

7
00:00:21,200 --> 00:00:23,390
lagret i en matrise, og hvis du trenger tilgang til

8
00:00:23,390 --> 00:00:25,050
eller endre ed listeelement

9
00:00:25,050 --> 00:00:27,570
for noen vilkårlig indeks I,

10
00:00:27,570 --> 00:00:29,910
som kan gjøres i konstant tid,

11
00:00:29,910 --> 00:00:31,660
men arrays har ulemper også.

12
00:00:31,660 --> 00:00:33,850
>> Når vi erklære dem, er vi forpliktet til å si

13
00:00:33,850 --> 00:00:35,900
opp foran hvor store de er,

14
00:00:35,900 --> 00:00:38,160
det vil si hvor mange elementer de kan lagre

15
00:00:38,160 --> 00:00:40,780
og hvor store disse elementene er, som bestemmes av type.

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

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

18
00:00:48,220 --> 00:00:50,200
som er på størrelse med en int.

19
00:00:50,200 --> 00:00:52,590
>> Vi kan ikke endre en rekke størrelse etter erklæringen.

20
00:00:52,590 --> 00:00:55,290
Vi må lage en ny rekke hvis vi ønsker å lagre flere elementer.

21
00:00:55,290 --> 00:00:57,410
Grunnen denne begrensningen eksisterer er at vår

22
00:00:57,410 --> 00:00:59,040
Programmet lagrer hel rekke

23
00:00:59,040 --> 00:01:02,310
som en sammenhengende del av minnet.

24
00:01:02,310 --> 00:01:04,500
Si dette er den buffer der vi lagret i array vår.

25
00:01:04,500 --> 00:01:06,910
Det kan være andre variabler

26
00:01:06,910 --> 00:01:08,310
ligger rett ved siden av tabellen

27
00:01:08,310 --> 00:01:10,060
i minnet, slik at vi ikke kan

28
00:01:10,060 --> 00:01:12,060
bare gjøre array større.

29
00:01:12,060 --> 00:01:15,700
>> Noen ganger vi ønsker å handle array rask datatilgang hastighet

30
00:01:15,700 --> 00:01:17,650
for litt mer fleksibilitet.

31
00:01:17,650 --> 00:01:20,380
Skriv inn lenket liste, en annen grunnleggende datastruktur

32
00:01:20,380 --> 00:01:22,360
du kanskje ikke være så kjent med.

33
00:01:22,360 --> 00:01:24,200
På et høyt nivå,

34
00:01:24,200 --> 00:01:26,840
en lenket liste lagrer data i en sekvens av noder

35
00:01:26,840 --> 00:01:29,280
som er koblet til hverandre med koblinger,

36
00:01:29,280 --> 00:01:31,760
derav navnet "lenket liste.

37
00:01:31,760 --> 00:01:33,840
Som vi vil se, denne forskjellen i design

38
00:01:33,840 --> 00:01:35,500
fører til forskjellige fordeler og ulemper

39
00:01:35,500 --> 00:01:37,000
enn en matrise.

40
00:01:37,000 --> 00:01:39,840
>> Her er noen C-kode for en veldig enkel lenket liste av heltall.

41
00:01:39,840 --> 00:01:42,190
Du kan se at vi har representert hver node

42
00:01:42,190 --> 00:01:45,520
i listen som en struct som inneholder to ting,

43
00:01:45,520 --> 00:01:47,280
et heltall for å lagre kalt 'val'

44
00:01:47,280 --> 00:01:50,460
og en link til neste node i listen

45
00:01:50,460 --> 00:01:52,990
som vi representerer som en peker som heter "neste".

46
00:01:54,120 --> 00:01:56,780
På denne måten kan vi spore hele listen

47
00:01:56,780 --> 00:01:58,790
med bare en enkelt peker til første node,

48
00:01:58,790 --> 00:02:01,270
og så kan vi følge de neste pekere

49
00:02:01,270 --> 00:02:03,130
til 2. node,

50
00:02:03,130 --> 00:02:05,280
til 3. node,

51
00:02:05,280 --> 00:02:07,000
til 4. node,

52
00:02:07,000 --> 00:02:09,889
og så videre, helt til vi kommer til slutten av listen.

53
00:02:10,520 --> 00:02:12,210
>> Du kan være i stand til å se en fordel dette har

54
00:02:12,210 --> 00:02:14,490
over statisk array struktur - med en lenket liste,

55
00:02:14,490 --> 00:02:16,450
Vi trenger ikke en stor del av minnet helt.

56
00:02:17,400 --> 00:02:20,530
Den første noden i listen kunne leve på dette stedet i minnet,

57
00:02:20,530 --> 00:02:23,160
og andre node kan være hele veien hit.

58
00:02:23,160 --> 00:02:25,780
Vi kan få til alle nodene uansett hvor i minnet er de,

59
00:02:25,780 --> 00:02:28,890
fordi starter på første node, hver node neste pekeren

60
00:02:28,890 --> 00:02:31,700
forteller oss nøyaktig hvor du skal gå neste.

61
00:02:31,700 --> 00:02:33,670
>> I tillegg har vi ikke å si opp foran

62
00:02:33,670 --> 00:02:36,740
hvor stor en lenket liste vil være måten vi gjør med statiske arrays,

63
00:02:36,740 --> 00:02:39,060
siden vi kan fortsette å legge noder i en liste

64
00:02:39,060 --> 00:02:42,600
så lenge det er plass et sted i minnet for nye noder.

65
00:02:42,600 --> 00:02:45,370
Derfor lenkede lister er lett å endre størrelsen dynamisk.

66
00:02:45,370 --> 00:02:47,950
Si, senere i programmet må vi legge til flere noder

67
00:02:47,950 --> 00:02:49,350
til listen vår.

68
00:02:49,350 --> 00:02:51,480
Å sette inn en ny node i vår liste på sparket,

69
00:02:51,480 --> 00:02:53,740
alt vi trenger å gjøre er å allokere minne for den noden,

70
00:02:53,740 --> 00:02:55,630
plop i dataverdi,

71
00:02:55,630 --> 00:02:59,070
og deretter plassere den der vi ønsker ved å justere de nødvendige pekere.

72
00:02:59,070 --> 00:03:02,310
>> For eksempel, hvis vi ønsket å plassere en node i mellom

73
00:03:02,310 --> 00:03:04,020
2. og 3. noder i listen,

74
00:03:04,020 --> 00:03:06,800
 vi ville ikke ha å flytte andre eller tredje noder i det hele tatt.

75
00:03:06,800 --> 00:03:09,190
Si at vi setter denne røde noden.

76
00:03:09,190 --> 00:03:12,890
Alt vi måtte gjøre er å sette den nye nodens neste pekeren

77
00:03:12,890 --> 00:03:14,870
å peke på den tredje node

78
00:03:14,870 --> 00:03:18,580
og deretter ReWire andre nodens neste pekeren

79
00:03:18,580 --> 00:03:20,980
å peke på vår nye node.

80
00:03:22,340 --> 00:03:24,370
Så kan vi endre størrelsen våre lister på fly

81
00:03:24,370 --> 00:03:26,090
siden vår datamaskin ikke stole på indeksering,

82
00:03:26,090 --> 00:03:28,990
men heller på å knytte bruke pekere til å lagre dem.

83
00:03:29,120 --> 00:03:31,600
>> Imidlertid, en ulempe med koblede lister

84
00:03:31,600 --> 00:03:33,370
er at, i motsetning til en statisk array,

85
00:03:33,370 --> 00:03:36,690
maskinen kan ikke bare hoppe til midten av listen.

86
00:03:38,040 --> 00:03:40,780
Siden maskinen har å besøke hver node i lenket liste

87
00:03:40,780 --> 00:03:42,330
å komme til neste,

88
00:03:42,330 --> 00:03:44,770
det kommer til å ta lengre tid å finne en bestemt node

89
00:03:44,770 --> 00:03:46,400
enn det ville i en matrise.

90
00:03:46,400 --> 00:03:48,660
Å traversere hele listen tar tid proporsjonal

91
00:03:48,660 --> 00:03:50,580
til lengden av listen,

92
00:03:50,580 --> 00:03:54,630
eller O (n) i asymptotisk notasjon.

93
00:03:54,630 --> 00:03:56,510
I gjennomsnitt, nå noen node

94
00:03:56,510 --> 00:03:58,800
også tar tid proporsjonal med n.

95
00:03:58,800 --> 00:04:00,700
>> Nå, la oss faktisk skrive noen kode

96
00:04:00,700 --> 00:04:02,000
som fungerer med koblede lister.

97
00:04:02,000 --> 00:04:04,220
La oss si at vi en lenket liste av heltall.

98
00:04:04,220 --> 00:04:06,140
Vi kan representere en node i vår liste igjen

99
00:04:06,140 --> 00:04:08,340
som en struct med 2 felt,

100
00:04:08,340 --> 00:04:10,750
et heltall kalles 'val'

101
00:04:10,750 --> 00:04:13,490
og en neste pekeren til neste node i listen.

102
00:04:13,490 --> 00:04:15,660
Vel, synes enkel nok.

103
00:04:15,660 --> 00:04:17,220
>> La oss si vi ønsker å skrive en funksjon

104
00:04:17,220 --> 00:04:19,329
som gjennomgår listen og skriver ut

105
00:04:19,329 --> 00:04:22,150
som er lagret i den siste noden i listen.

106
00:04:22,150 --> 00:04:24,850
Vel, det betyr at vi må traversere alle nodene i listen

107
00:04:24,850 --> 00:04:27,310
å finne den siste, men siden vi ikke legger

108
00:04:27,310 --> 00:04:29,250
eller slette noe, ønsker vi ikke å endre

109
00:04:29,250 --> 00:04:32,210
den interne strukturen av de neste pekere i listen.

110
00:04:32,210 --> 00:04:34,790
>> Så trenger vi en peker spesielt for traversering

111
00:04:34,790 --> 00:04:36,940
som vi kaller 'crawler.

112
00:04:36,940 --> 00:04:38,870
Den kryper gjennom alle elementene i listen

113
00:04:38,870 --> 00:04:41,190
ved å følge kjeden av neste pekere.

114
00:04:41,190 --> 00:04:43,750
Alt vi har lagret er en peker til første node,

115
00:04:43,750 --> 00:04:45,730
eller "hodet" på listen.

116
00:04:45,730 --> 00:04:47,370
Hodet peker til første node.

117
00:04:47,370 --> 00:04:49,120
Det er av typen pointer-til-node.

118
00:04:49,120 --> 00:04:51,280
>> For å få den faktiske første node i listen,

119
00:04:51,280 --> 00:04:53,250
vi må dereferanse denne pekeren,

120
00:04:53,250 --> 00:04:55,100
men før vi kan dereferanse det, må vi sjekke

121
00:04:55,100 --> 00:04:57,180
hvis pekeren er null først.

122
00:04:57,180 --> 00:04:59,190
Hvis det er null, er listen tom,

123
00:04:59,190 --> 00:05:01,320
og vi bør skrive ut en melding om at, fordi listen er tom,

124
00:05:01,320 --> 00:05:03,250
det er ingen siste noden.

125
00:05:03,250 --> 00:05:05,190
Men, la oss si at listen er ikke tom.

126
00:05:05,190 --> 00:05:08,340
Hvis det ikke er det, så vi bør gjennomgå hele listen

127
00:05:08,340 --> 00:05:10,440
før vi kommer til den siste noden i listen,

128
00:05:10,440 --> 00:05:13,030
og hvordan kan vi vite at vi ser på den siste noden i listen?

129
00:05:13,670 --> 00:05:16,660
>> Vel, hvis en node neste pekeren er null,

130
00:05:16,660 --> 00:05:18,320
Vi vet at vi på slutten

131
00:05:18,320 --> 00:05:22,390
siden siste neste pekeren ville ha noe neste node i listen for å vise til.

132
00:05:22,390 --> 00:05:26,590
Det er god praksis å alltid holde den siste noden neste pekeren initialisert til null

133
00:05:26,590 --> 00:05:30,800
å ha en standardisert egenskap som varsler oss når vi har nådd slutten av listen.

134
00:05:30,800 --> 00:05:33,510
>> Så hvis crawler → neste er null,

135
00:05:34,120 --> 00:05:38,270
husk at pilen syntaksen er en snarvei for dereferencing

136
00:05:38,270 --> 00:05:40,010
en peker til en struct, deretter tilgang

137
00:05:40,010 --> 00:05:42,510
dens neste felt tilsvarer klosset:

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

139
00:05:49,820 --> 00:05:51,260
Når vi har funnet den siste noden,

140
00:05:51,260 --> 00:05:53,830
Vi vil skrive ut crawler → val,

141
00:05:53,830 --> 00:05:55,000
verdien i gjeldende node

142
00:05:55,000 --> 00:05:57,130
som vi vet er den siste.

143
00:05:57,130 --> 00:05:59,740
Ellers, hvis vi er ennå ikke i siste node i listen,

144
00:05:59,740 --> 00:06:02,340
vi må gå videre til neste node i listen

145
00:06:02,340 --> 00:06:04,750
og sjekk om det er den siste.

146
00:06:04,750 --> 00:06:07,010
For å gjøre dette, vi bare sette vår crawler pekeren

147
00:06:07,010 --> 00:06:09,840
å peke på gjeldende node neste verdi,

148
00:06:09,840 --> 00:06:11,680
det vil si den neste node i listen.

149
00:06:11,680 --> 00:06:13,030
Dette gjøres ved å sette

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

151
00:06:16,050 --> 00:06:18,960
Så vi gjentar denne prosessen, med en løkke for eksempel,

152
00:06:18,960 --> 00:06:20,960
til vi finner den siste noden.

153
00:06:20,960 --> 00:06:23,150
Så, for eksempel, hvis crawler pekte på hodet,

154
00:06:24,050 --> 00:06:27,710
vi satt crawler til å peke på crawler → neste,

155
00:06:27,710 --> 00:06:30,960
som er det samme som det neste feltet i første noden.

156
00:06:30,960 --> 00:06:33,620
Så nå søkeroboten peker til andre node,

157
00:06:33,620 --> 00:06:35,480
og, igjen, gjentar vi dette med en løkke,

158
00:06:37,220 --> 00:06:40,610
før vi har funnet den siste noden, er at

159
00:06:40,610 --> 00:06:43,640
hvor noden neste pekeren peker til null.

160
00:06:43,640 --> 00:06:45,070
Og der har vi det,

161
00:06:45,070 --> 00:06:47,620
vi har funnet den siste noden i listen, og til å skrive ut sin verdi,

162
00:06:47,620 --> 00:06:50,800
vi bare bruke crawler → val.

163
00:06:50,800 --> 00:06:53,130
>> Traversering er ikke så ille, men hva med å sette inn?

164
00:06:53,130 --> 00:06:56,290
La oss si at vi ønsker å sette et heltall i fjerde posisjon

165
00:06:56,290 --> 00:06:58,040
i et heltall liste.

166
00:06:58,040 --> 00:07:01,280
Som er mellom dagens tredje og fjerde noder.

167
00:07:01,280 --> 00:07:03,760
Igjen har vi å traversere listen bare for å

168
00:07:03,760 --> 00:07:06,520
komme til tredje element, den vi setter etter.

169
00:07:06,520 --> 00:07:09,300
Så lager vi en crawler peker igjen for å traversere listen,

170
00:07:09,300 --> 00:07:11,400
sjekk om vårt hode pekeren er null,

171
00:07:11,400 --> 00:07:14,810
og hvis det ikke er det, peke søkeroboten pekeren på hodet node.

172
00:07:16,880 --> 00:07:18,060
Så er vi på første element.

173
00:07:18,060 --> 00:07:21,020
Vi må gå frem to flere elementer før vi kan sette inn,

174
00:07:21,020 --> 00:07:23,390
slik at vi kan bruke en for loop

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

176
00:07:26,430 --> 00:07:28,590
og i hver iterasjon av loopen,

177
00:07:28,590 --> 00:07:31,540
fremme søkeroboten pekeren framover ved en node

178
00:07:31,540 --> 00:07:34,570
ved å sjekke om den nåværende node neste feltet er null,

179
00:07:34,570 --> 00:07:37,550
og hvis det ikke er det, flytter søkeroboten pekeren til neste node

180
00:07:37,550 --> 00:07:41,810
ved å sette den lik gjeldende node neste pekeren.

181
00:07:41,810 --> 00:07:45,210
Så, siden vår for loop sier å gjøre det

182
00:07:45,210 --> 00:07:47,550
to ganger,

183
00:07:49,610 --> 00:07:51,190
Vi har nådd tredje node,

184
00:07:51,190 --> 00:07:53,110
og når søkeroboten indikatoren har nådd node etter

185
00:07:53,110 --> 00:07:55,270
som vi ønsker å sette vår nye heltall,

186
00:07:55,270 --> 00:07:57,050
hvordan gjør vi faktisk gjør innsetting?

187
00:07:57,050 --> 00:07:59,440
>> Vel, har vår nye heltall som skal settes inn i listen

188
00:07:59,440 --> 00:08:01,250
som en del av sin egen node struct,

189
00:08:01,250 --> 00:08:03,140
siden dette er virkelig en sekvens av noder.

190
00:08:03,140 --> 00:08:05,690
Så, la oss lage en ny pekepinn på node

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

192
00:08:08,910 --> 00:08:11,800
og sett den til å peke til minne om at vi nå bevilger

193
00:08:11,800 --> 00:08:14,270
på haugen for noden selv,

194
00:08:14,270 --> 00:08:16,000
og hvor mye minne trenger vi å fordele?

195
00:08:16,000 --> 00:08:18,250
Vel, på størrelse med en node,

196
00:08:20,450 --> 00:08:23,410
og vi ønsker å sette sitt val feltet til heltall som vi vil sette inn.

197
00:08:23,410 --> 00:08:25,590
La oss si, 6.

198
00:08:25,590 --> 00:08:27,710
Nå inneholder noden vårt heltallsverdi.

199
00:08:27,710 --> 00:08:30,650
Det er også lurt å starte den nye nodens neste felt

200
00:08:30,650 --> 00:08:33,690
å peke på null,

201
00:08:33,690 --> 00:08:35,080
men hva nå?

202
00:08:35,080 --> 00:08:37,179
>> Vi må endre interne strukturen listen

203
00:08:37,179 --> 00:08:40,409
og de neste pekere finnes i listen eksisterende

204
00:08:40,409 --> 00:08:42,950
3. og 4. noder.

205
00:08:42,950 --> 00:08:46,560
Siden de neste pekere bestemme rekkefølgen av listen,

206
00:08:46,560 --> 00:08:48,650
og siden vi sette vår nye node

207
00:08:48,650 --> 00:08:50,510
rett inn i midten av listen,

208
00:08:50,510 --> 00:08:52,010
det kan være litt vanskelig.

209
00:08:52,010 --> 00:08:54,250
Dette er fordi, husk, vår datamaskin

210
00:08:54,250 --> 00:08:56,250
vet bare plasseringen av noder i listen

211
00:08:56,250 --> 00:09:00,400
grunn av de neste pekere lagret i tidligere noder.

212
00:09:00,400 --> 00:09:03,940
Så, hvis vi noen gang mistet oversikten over noen av disse stedene,

213
00:09:03,940 --> 00:09:06,860
si ved å endre en av de neste pekere i vår liste,

214
00:09:06,860 --> 00:09:09,880
for eksempel, sier vi endret

215
00:09:09,880 --> 00:09:12,920
3. nodens neste felt

216
00:09:12,920 --> 00:09:15,610
å peke på noen node over her.

217
00:09:15,610 --> 00:09:17,920
Vi vil være ute av lykken, fordi vi ikke ville

218
00:09:17,920 --> 00:09:20,940
har noen anelse om hvor du finner resten av listen,

219
00:09:20,940 --> 00:09:23,070
og det er åpenbart veldig dårlig.

220
00:09:23,070 --> 00:09:25,080
Så må vi være veldig forsiktig med rekkefølgen

221
00:09:25,080 --> 00:09:28,360
der vi manipulere våre neste pekere under innsetting.

222
00:09:28,360 --> 00:09:30,540
>> Så, for å forenkle dette, la oss si at

223
00:09:30,540 --> 00:09:32,220
våre 4 første noder

224
00:09:32,220 --> 00:09:36,200
kalles A, B, C og D, med pilene representerer kjeden av pekere

225
00:09:36,200 --> 00:09:38,070
som kobler nodene.

226
00:09:38,070 --> 00:09:40,050
Så må vi sette inn vår nye node

227
00:09:40,050 --> 00:09:42,070
i mellom noder C og D.

228
00:09:42,070 --> 00:09:45,060
Det er viktig å gjøre det i riktig rekkefølge, og jeg vil vise deg hvorfor.

229
00:09:45,060 --> 00:09:47,500
>> La oss se på feil måte å gjøre det først.

230
00:09:47,500 --> 00:09:49,490
Hei, vi vet den nye noden må komme rett etter C,

231
00:09:49,490 --> 00:09:51,910
så la oss sette C neste pekeren

232
00:09:51,910 --> 00:09:54,700
å peke på new_node.

233
00:09:56,530 --> 00:09:59,180
Greit, virker greit, vi må bare gjøre ferdig nå ved

234
00:09:59,180 --> 00:10:01,580
gjør den nye nodens neste pekeren peker til D,

235
00:10:01,580 --> 00:10:03,250
men vent, hvordan kan vi gjøre det?

236
00:10:03,250 --> 00:10:05,170
Det eneste som kunne fortelle oss hvor D var,

237
00:10:05,170 --> 00:10:07,630
var neste pekeren tidligere lagret i C,

238
00:10:07,630 --> 00:10:09,870
men vi omskrev at pekeren

239
00:10:09,870 --> 00:10:11,170
å peke på den nye noden,

240
00:10:11,170 --> 00:10:14,230
så vi ikke lenger har noen anelse hvor D er i minnet,

241
00:10:14,230 --> 00:10:17,020
og vi har mistet resten av listen.

242
00:10:17,020 --> 00:10:19,000
Ikke bra i det hele tatt.

243
00:10:19,000 --> 00:10:21,090
>> Så, hvordan vi gjør dette riktig?

244
00:10:22,360 --> 00:10:25,090
Først peker den nye nodens neste peker på D.

245
00:10:26,170 --> 00:10:28,990
Nå, både den nye nodens og C er neste pekere

246
00:10:28,990 --> 00:10:30,660
peker til samme node, D,

247
00:10:30,660 --> 00:10:32,290
men det er fint.

248
00:10:32,290 --> 00:10:35,680
Nå kan vi peke C neste pekeren på den nye noden.

249
00:10:37,450 --> 00:10:39,670
Så har vi gjort dette uten å miste data.

250
00:10:39,670 --> 00:10:42,280
I kode, er C gjeldende node

251
00:10:42,280 --> 00:10:45,540
at traversering pekeren crawler peker til,

252
00:10:45,540 --> 00:10:50,400
og D er representert ved noden pekes til av gjeldende nodens neste felt,

253
00:10:50,400 --> 00:10:52,600
eller crawler → neste.

254
00:10:52,600 --> 00:10:55,460
Så vi først sette den nye nodens neste pekeren

255
00:10:55,460 --> 00:10:57,370
å peke på crawler → neste,

256
00:10:57,370 --> 00:11:00,880
på samme måte som vi sa new_node neste pekeren skal

257
00:11:00,880 --> 00:11:02,780
peke på D i illustrasjonen.

258
00:11:02,780 --> 00:11:04,540
Deretter kan vi sette gjeldende node neste pekeren

259
00:11:04,540 --> 00:11:06,330
til vår nye node,

260
00:11:06,330 --> 00:11:10,980
akkurat som vi måtte vente til punkt C til new_node i tegningen.

261
00:11:10,980 --> 00:11:12,250
Nå er alt er i orden, og vi tapte ikke

262
00:11:12,250 --> 00:11:14,490
spore av data, og vi var i stand til å bare

263
00:11:14,490 --> 00:11:16,200
stokk vår nye node i midten av listen

264
00:11:16,200 --> 00:11:19,330
uten å gjenoppbygge det hele eller skiftende noen elementer

265
00:11:19,330 --> 00:11:22,490
måten vi ville ha hatt til med en fast lengde array.

266
00:11:22,490 --> 00:11:26,020
>> Så, koblede lister er en grunnleggende, men viktig, dynamisk datastruktur

267
00:11:26,020 --> 00:11:29,080
som har både fordeler og ulemper

268
00:11:29,080 --> 00:11:31,260
sammenlignet matriser og andre datastrukturer,

269
00:11:31,260 --> 00:11:33,350
og som ofte er tilfellet i informatikk,

270
00:11:33,350 --> 00:11:35,640
det er viktig å vite når du skal bruke hvert verktøy,

271
00:11:35,640 --> 00:11:37,960
slik at du kan velge riktig verktøy til rett jobb.

272
00:11:37,960 --> 00:11:40,060
>> For mer praksis, kan du prøve å skrive funksjoner

273
00:11:40,060 --> 00:11:42,080
slette noder fra en lenket liste -

274
00:11:42,080 --> 00:11:44,050
Husk å være forsiktig om i hvilken rekkefølge du omorganisere

275
00:11:44,050 --> 00:11:47,430
de neste pekere for å sikre at du ikke mister en del av listen -

276
00:11:47,430 --> 00:11:50,200
eller en funksjon for å telle nodene i en lenket liste,

277
00:11:50,200 --> 00:11:53,280
eller en morsom en, for å snu rekkefølgen på alle nodene i en lenket liste.

278
00:11:53,280 --> 00:11:56,090
>> Mitt navn er Jackson Steinkamp, ​​er dette CS50.