1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] I programmering, vi ofte nødt til at repræsentere lister over værdier,

2
00:00:10,050 --> 00:00:12,840
såsom navne på studerende i et afsnit

3
00:00:12,840 --> 00:00:15,100
eller deres scoringer på det seneste quiz.

4
00:00:15,100 --> 00:00:17,430
>> I C-sprog, erklæres arrays kan anvendes

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

6
00:00:19,160 --> 00:00:21,200
Det er nemt at opregne de elementer i en liste

7
00:00:21,200 --> 00:00:23,390
gemt i et array, og hvis du har brug for at få adgang

8
00:00:23,390 --> 00:00:25,050
eller ændre den i'te listeelement

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

10
00:00:27,570 --> 00:00:29,910
der kan gø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 forpligtet til at sige

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

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

15
00:00:38,160 --> 00:00:40,780
og hvor store disse elementer, som bestemmes af deres 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 gemme 10 varer

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

19
00:00:50,200 --> 00:00:52,590
>> Vi kan ikke ændre et array størrelse efter erklæring.

20
00:00:52,590 --> 00:00:55,290
Vi er nødt til at lave et nyt array, hvis vi ønsker at gemme flere elementer.

21
00:00:55,290 --> 00:00:57,410
Grunden denne begrænsning eksisterer, er, at vores

22
00:00:57,410 --> 00:00:59,040
programmet lagrer hele arrayet

23
00:00:59,040 --> 00:01:02,310
som en sammenhængende luns af hukommelsen.

24
00:01:02,310 --> 00:01:04,500
Sige dette er den buffer, hvor vi gemt i vores array.

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

26
00:01:06,910 --> 00:01:08,310
beliggende lige ud til arrayet

27
00:01:08,310 --> 00:01:10,060
i hukommelsen, så vi kan ikke

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

29
00:01:12,060 --> 00:01:15,700
>> Nogle gange er vi gerne vil handle arrayet hurtige dataadgang hastighed

30
00:01:15,700 --> 00:01:17,650
for lidt mere fleksibilitet.

31
00:01:17,650 --> 00:01:20,380
Indtast den linkede liste, en anden grundlæggende datastruktur

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

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

34
00:01:24,200 --> 00:01:26,840
en sammenkædet liste lagrer data i en sekvens af knudepunkter

35
00:01:26,840 --> 00:01:29,280
som er forbundet til hinanden med links,

36
00:01:29,280 --> 00:01:31,760
deraf navnet 'linkede liste.'

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

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

39
00:01:35,500 --> 00:01:37,000
end et array.

40
00:01:37,000 --> 00:01:39,840
>> Her er nogle C-kode for en meget simpel hægtet liste af heltal.

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

42
00:01:42,190 --> 00:01:45,520
på listen som en struct, der indeholder 2 ting,

43
00:01:45,520 --> 00:01:47,280
et heltal til at gemme kaldes 'val'

44
00:01:47,280 --> 00:01:50,460
og et link til den næste node i listen

45
00:01:50,460 --> 00:01:52,990
som vi repræsenterer som en pegepind kaldes 'næste'.

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

47
00:01:56,780 --> 00:01:58,790
med blot et enkelt pointer til 1. node,

48
00:01:58,790 --> 00:02:01,270
og så kan vi følge de næste pointers

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, indtil vi kommer til slutningen af ​​listen.

53
00:02:10,520 --> 00:02:12,210
>> Du vil måske være i stand til at se 1 fordel dette har

54
00:02:12,210 --> 00:02:14,490
over den statiske array-struktur - med en linket liste,

55
00:02:14,490 --> 00:02:16,450
vi har ikke brug for en stor luns af hukommelse helt.

56
00:02:17,400 --> 00:02:20,530
Den 1. node af listen kunne leve på dette sted i hukommelsen,

57
00:02:20,530 --> 00:02:23,160
og 2. knude kunne være helt herovre.

58
00:02:23,160 --> 00:02:25,780
Vi kan komme til alle de noder, uanset hvor i hukommelsen de er,

59
00:02:25,780 --> 00:02:28,890
fordi starter ved 1. knudepunkt, hver node næste pointer

60
00:02:28,890 --> 00:02:31,700
fortæller os præcis, hvor de skal gå næste.

61
00:02:31,700 --> 00:02:33,670
>> Derudover har vi ikke til at sige op foran

62
00:02:33,670 --> 00:02:36,740
hvor stor en sammenkædet liste vil være den måde, vi gør med statiske arrays,

63
00:02:36,740 --> 00:02:39,060
da vi kan holde tilføje noder til en liste

64
00:02:39,060 --> 00:02:42,600
så længe der er plads et eller andet sted i hukommelsen for nye noder.

65
00:02:42,600 --> 00:02:45,370
Derfor hægtede lister er nemme at ændre størrelsen dynamisk.

66
00:02:45,370 --> 00:02:47,950
Sig, senere i det program, vi har brug for at tilføje flere noder

67
00:02:47,950 --> 00:02:49,350
ind i vores liste.

68
00:02:49,350 --> 00:02:51,480
Hvis du vil indsætte en ny node i vores liste på flue,

69
00:02:51,480 --> 00:02:53,740
alt, hvad vi skal gøre, er tildele hukommelse til denne knude,

70
00:02:53,740 --> 00:02:55,630
plumpet i dataværdi,

71
00:02:55,630 --> 00:02:59,070
og derefter placere den hvor vi ønsker ved at justere de passende pointers.

72
00:02:59,070 --> 00:03:02,310
>> For eksempel, hvis vi ønskede at anbringe en knude i mellem

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

74
00:03:04,020 --> 00:03:06,800
 ville vi ikke nødt til at flytte den 2. eller 3. noder på alle.

75
00:03:06,800 --> 00:03:09,190
Sig vi indsætte denne røde node.

76
00:03:09,190 --> 00:03:12,890
Alt, hvad vi ville have at gøre, er at sætte den nye node næste pointer

77
00:03:12,890 --> 00:03:14,870
at pege til 3. node

78
00:03:14,870 --> 00:03:18,580
og derefter ReWire 2. knudepunkts næste pointerjustering

79
00:03:18,580 --> 00:03:20,980
til at pege på vores nye node.

80
00:03:22,340 --> 00:03:24,370
Så kan vi ændre størrelsen på vores liste på farten

81
00:03:24,370 --> 00:03:26,090
da vores computer ikke er afhængig af indeksering,

82
00:03:26,090 --> 00:03:28,990
men snarere på at knytte med pegepinde til at gemme dem.

83
00:03:29,120 --> 00:03:31,600
>> En ulempe ved knyttet lister

84
00:03:31,600 --> 00:03:33,370
er, at i modsætning til et statisk array,

85
00:03:33,370 --> 00:03:36,690
computeren kan ikke bare hoppe til midten af ​​listen.

86
00:03:38,040 --> 00:03:40,780
Da computeren har til at besøge hver node i den linkede liste

87
00:03:40,780 --> 00:03:42,330
for at komme til det næste,

88
00:03:42,330 --> 00:03:44,770
det vil tage længere tid at finde en bestemt node

89
00:03:44,770 --> 00:03:46,400
end den ville i et array.

90
00:03:46,400 --> 00:03:48,660
Til at krydse hele listen tager tid proportional

91
00:03:48,660 --> 00:03:50,580
til længden af ​​listen,

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

93
00:03:54,630 --> 00:03:56,510
I gennemsnit nåede enhver node

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

95
00:03:58,800 --> 00:04:00,700
>> Lad os nu faktisk skrive noget kode

96
00:04:00,700 --> 00:04:02,000
der arbejder med hægtede lister.

97
00:04:02,000 --> 00:04:04,220
Lad os sige, at vi ønsker en tilknyttet liste med heltal.

98
00:04:04,220 --> 00:04:06,140
Vi kan repræsentere et knudepunkt i vores liste igen

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

100
00:04:08,340 --> 00:04:10,750
en heltalsværdi kaldet 'val'

101
00:04:10,750 --> 00:04:13,490
og en næste markør til den næste node i listen.

102
00:04:13,490 --> 00:04:15,660
Nå, synes simpelt nok.

103
00:04:15,660 --> 00:04:17,220
>> Lad os sige at vi vil skrive en funktion

104
00:04:17,220 --> 00:04:19,329
der gennemgår listen og udskriver den

105
00:04:19,329 --> 00:04:22,150
lagret i det sidste emne på listen.

106
00:04:22,150 --> 00:04:24,850
Tja, det betyder, at vi bliver nødt til at krydse alle knuder i listen

107
00:04:24,850 --> 00:04:27,310
at finde den sidste, men da vi ikke har tilføjet

108
00:04:27,310 --> 00:04:29,250
eller slette noget, vi ikke ønsker at ændre

109
00:04:29,250 --> 00:04:32,210
den interne struktur i de næste markører på listen.

110
00:04:32,210 --> 00:04:34,790
>> Så vil vi have en pointer specielt til traversal

111
00:04:34,790 --> 00:04:36,940
som vi kalder "crawler".

112
00:04:36,940 --> 00:04:38,870
Det vil kravle gennem alle elementer i listen

113
00:04:38,870 --> 00:04:41,190
ved at følge kæden af ​​næste pointers.

114
00:04:41,190 --> 00:04:43,750
Alt, hvad vi har gemt, er en pointer til 1. node,

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

116
00:04:45,730 --> 00:04:47,370
Head peger på 1. node.

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

118
00:04:49,120 --> 00:04:51,280
>> For at få den faktiske 1:e node i listen,

119
00:04:51,280 --> 00:04:53,250
vi er nødt til at dereference denne pointer,

120
00:04:53,250 --> 00:04:55,100
men før vi kan dereference det, er vi nødt til at kontrollere

121
00:04:55,100 --> 00:04:57,180
hvis markøren er nul først.

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

123
00:04:59,190 --> 00:05:01,320
og vi bør udskrive en besked, der, fordi listen er tom,

124
00:05:01,320 --> 00:05:03,250
der er ingen sidste knudepunkt.

125
00:05:03,250 --> 00:05:05,190
Men, lad os sige listen ikke er tom.

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

127
00:05:08,340 --> 00:05:10,440
indtil vi kommer til det sidste emne på listen,

128
00:05:10,440 --> 00:05:13,030
og hvordan kan vi fortælle, hvis vi ser på det sidste emne på listen?

129
00:05:13,670 --> 00:05:16,660
>> Tja, hvis en node næste pointer er nul,

130
00:05:16,660 --> 00:05:18,320
Vi ved, vi er i slutningen

131
00:05:18,320 --> 00:05:22,390
siden sidste næste pointerjustering ville have nogen næste node i listen at pege på.

132
00:05:22,390 --> 00:05:26,590
Det er god praksis altid at holde den sidste node næste pointer initialiseret til null

133
00:05:26,590 --> 00:05:30,800
at have en standardiseret egenskab, som advarer os, når vi har nået slutningen af ​​listen.

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

135
00:05:34,120 --> 00:05:38,270
huske på, at pilen syntaksen er en genvej til dereferere

136
00:05:38,270 --> 00:05:40,010
en pointer til en struct, så adgang

137
00:05:40,010 --> 00:05:42,510
den næste felt svarende til den akavede:

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

139
00:05:49,820 --> 00:05:51,260
Når vi har fundet den sidste node,

140
00:05:51,260 --> 00:05:53,830
vi ønsker at udskrive crawler → val,

141
00:05:53,830 --> 00:05:55,000
værdien i den aktuelle node

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

143
00:05:57,130 --> 00:05:59,740
Ellers, hvis vi ikke er endnu på det sidste node i listen,

144
00:05:59,740 --> 00:06:02,340
vi er nødt til at gå videre til den næste node i listen

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

146
00:06:04,750 --> 00:06:07,010
For at gøre dette, har vi bare indstille vores webcrawler pointer

147
00:06:07,010 --> 00:06:09,840
at pege på den aktuelle node næste værdi,

148
00:06:09,840 --> 00:06:11,680
det vil sige den næste node i listen.

149
00:06:11,680 --> 00:06:13,030
Dette gøres ved at sætte

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → næste.

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

152
00:06:18,960 --> 00:06:20,960
indtil vi finder den sidste node.

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

154
00:06:24,050 --> 00:06:27,710
vi satte crawler til at pege på crawler → næste,

155
00:06:27,710 --> 00:06:30,960
hvilket er det samme som det næste felt i den 1. node.

156
00:06:30,960 --> 00:06:33,620
Så nu er vores crawler peger til 2. node,

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

158
00:06:37,220 --> 00:06:40,610
indtil vi har fundet den sidste node, dvs

159
00:06:40,610 --> 00:06:43,640
hvor knuden næste pointer peger 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 fundet den sidste node i listen, og at udskrive dens værdi,

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

163
00:06:50,800 --> 00:06:53,130
>> Gennemkører er ikke så slemt, men hvad med at indsætte?

164
00:06:53,130 --> 00:06:56,290
Lad os sige, at vi ønsker at indsætte et heltal i den 4. plads

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

166
00:06:58,040 --> 00:07:01,280
Det er mellem de nuværende 3. og 4. noder.

167
00:07:01,280 --> 00:07:03,760
Igen, vi er nødt til at krydse den liste bare til

168
00:07:03,760 --> 00:07:06,520
komme til 3. element, den ene vi indsætte efter.

169
00:07:06,520 --> 00:07:09,300
Så skaber vi en crawler pointer igen at krydse listen,

170
00:07:09,300 --> 00:07:11,400
kontrollere, om vores hoved pointer er nul,

171
00:07:11,400 --> 00:07:14,810
og hvis det ikke er, peger vores webcrawler pointer i spidsen node.

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

173
00:07:18,060 --> 00:07:21,020
Vi er nødt til at gå fremad 2 flere elementer, før vi kan indsætte,

174
00:07:21,020 --> 00:07:23,390
så vi kan bruge en for-løkke

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

176
00:07:26,430 --> 00:07:28,590
og i hver iteration af løkken,

177
00:07:28,590 --> 00:07:31,540
fremme vores webcrawler pointer frem med 1 node

178
00:07:31,540 --> 00:07:34,570
ved at kontrollere, om den aktuelle node næste felt er nul,

179
00:07:34,570 --> 00:07:37,550
og hvis det ikke er, skal du flytte vores webcrawler markøren til den næste node

180
00:07:37,550 --> 00:07:41,810
ved at sætte det lig med den aktuelle node næste pointer.

181
00:07:41,810 --> 00:07:45,210
Så da vores for løkke siger at gøre det

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

183
00:07:49,610 --> 00:07:51,190
vi har nået den 3. knude,

184
00:07:51,190 --> 00:07:53,110
og når vores webcrawler pointer har nået node efter

185
00:07:53,110 --> 00:07:55,270
som vi ønsker at indsætte vores nye heltal,

186
00:07:55,270 --> 00:07:57,050
hvordan kan vi rent faktisk gør det indsættelse?

187
00:07:57,050 --> 00:07:59,440
>> Nå, vores nye heltal skal indsættes i listen

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

189
00:08:01,250 --> 00:08:03,140
idet dette er virkelig en sekvens af knudepunkter.

190
00:08:03,140 --> 00:08:05,690
Så lad os lave en ny pointer til knude

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

192
00:08:08,910 --> 00:08:11,800
og sæt den til at pege på hukommelse, som vi nu tildele

193
00:08:11,800 --> 00:08:14,270
på heapen for knuden selv,

194
00:08:14,270 --> 00:08:16,000
og hvor meget hukommelse har vi brug for at afsætte?

195
00:08:16,000 --> 00:08:18,250
Nå, størrelsen af ​​et knudepunkt,

196
00:08:20,450 --> 00:08:23,410
og vi ønsker at sætte sit val felt til heltal, vi ønsker at indsætte.

197
00:08:23,410 --> 00:08:25,590
Lad os sige, 6.

198
00:08:25,590 --> 00:08:27,710
Nu node indeholder vores heltalsværdi.

199
00:08:27,710 --> 00:08:30,650
Det er også god praksis at initialisere den nye node næste felt

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

201
00:08:33,690 --> 00:08:35,080
men hvad nu?

202
00:08:35,080 --> 00:08:37,179
>> Vi ændre den interne struktur af listen

203
00:08:37,179 --> 00:08:40,409
og de næste pointers i listen eksisterende

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

205
00:08:42,950 --> 00:08:46,560
Da de næste pointers bestemme rækkefølgen af ​​listen,

206
00:08:46,560 --> 00:08:48,650
og da vi sætter vores nye knudepunkt

207
00:08:48,650 --> 00:08:50,510
lige ind i midten af ​​listen,

208
00:08:50,510 --> 00:08:52,010
det kan være en smule tricky.

209
00:08:52,010 --> 00:08:54,250
Dette skyldes, husk, vores computer

210
00:08:54,250 --> 00:08:56,250
kun kender placeringen af ​​knudepunkter i listen

211
00:08:56,250 --> 00:09:00,400
på grund af de næste pointers lagret i de foregående knudepunkter.

212
00:09:00,400 --> 00:09:03,940
Så hvis vi nogensinde mistet overblikket over nogen af ​​disse steder,

213
00:09:03,940 --> 00:09:06,860
sige ved at ændre en af ​​de næste pejlemærker i vores liste,

214
00:09:06,860 --> 00:09:09,880
for eksempel, siger vi ændret

215
00:09:09,880 --> 00:09:12,920
3. knudepunkts næste felt

216
00:09:12,920 --> 00:09:15,610
at pege på nogle node herovre.

217
00:09:15,610 --> 00:09:17,920
Vi ville være ude af lykke, fordi vi ikke ville

218
00:09:17,920 --> 00:09:20,940
har nogen idé om, hvor at finde resten af ​​listen,

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

220
00:09:23,070 --> 00:09:25,080
Så vi er nødt til at være virkelig forsigtig med ordren

221
00:09:25,080 --> 00:09:28,360
hvor vi manipulere vores næste pointers under indføring.

222
00:09:28,360 --> 00:09:30,540
>> Så for at forenkle det, så lad os sige, at

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

224
00:09:32,220 --> 00:09:36,200
kaldes A, B, C og D, med pilene repræsenterer kæden af ​​pegepinde

225
00:09:36,200 --> 00:09:38,070
der forbinder knudepunkter.

226
00:09:38,070 --> 00:09:40,050
Så er vi nødt til at indsætte vores nye knudepunkt

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

228
00:09:42,070 --> 00:09:45,060
Det er afgørende at gøre det i den rigtige rækkefølge, og jeg vil vise dig hvorfor.

229
00:09:45,060 --> 00:09:47,500
>> Lad os se på den forkerte måde at gøre det først.

230
00:09:47,500 --> 00:09:49,490
Hey, vi ved det nye knudepunkt skal komme lige efter C,

231
00:09:49,490 --> 00:09:51,910
så lad os indstille C næste pointer

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

233
00:09:56,530 --> 00:09:59,180
Okay, virker okay, vi bare nødt til at slutte op nu ved

234
00:09:59,180 --> 00:10:01,580
gør den nye knude næste pointer pege på D,

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

236
00:10:03,250 --> 00:10:05,170
Det eneste, der kunne fortælle os, hvor D var,

237
00:10:05,170 --> 00:10:07,630
blev den næste pointer tidligere lagret i C,

238
00:10:07,630 --> 00:10:09,870
men vi bare omskrev denne pegepind

239
00:10:09,870 --> 00:10:11,170
den peger på den nye knudepunkt,

240
00:10:11,170 --> 00:10:14,230
så vi ikke længere har nogen anelse om, hvor D er i hukommelsen,

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

242
00:10:17,020 --> 00:10:19,000
Ikke god til alle.

243
00:10:19,000 --> 00:10:21,090
>> Så hvordan vi gør det rigtigt?

244
00:10:22,360 --> 00:10:25,090
Først peger det nye knudepunkt næste pointer på D.

245
00:10:26,170 --> 00:10:28,990
Nu, både den nye node-og C'er næste pointers

246
00:10:28,990 --> 00:10:30,660
peger på det samme knudepunkt, D,

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

248
00:10:32,290 --> 00:10:35,680
Nu kan vi pege C næste pointer på det nye knudepunkt.

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

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

251
00:10:42,280 --> 00:10:45,540
at gennemkrydsning pointer crawler peger på,

252
00:10:45,540 --> 00:10:50,400
og D er repræsenteret ved knudepunktet peges på af den aktuelle node næste felt,

253
00:10:50,400 --> 00:10:52,600
eller crawler → næste.

254
00:10:52,600 --> 00:10:55,460
Så vi startede det nye knudepunkt næste pointer

255
00:10:55,460 --> 00:10:57,370
at pege på crawler → næste,

256
00:10:57,370 --> 00:11:00,880
på samme måde, vi sagde new_node næste pointer bør

257
00:11:00,880 --> 00:11:02,780
pege på D på illustrationen.

258
00:11:02,780 --> 00:11:04,540
Derefter kan vi sætte den aktuelle node næste pointer

259
00:11:04,540 --> 00:11:06,330
til vores nye knudepunkt,

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

261
00:11:10,980 --> 00:11:12,250
Nu alt er i orden, og vi ikke mister

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

263
00:11:14,490 --> 00:11:16,200
holde vores nye knudepunkt i midten af ​​listen

264
00:11:16,200 --> 00:11:19,330
uden at genopbygge det hele eller endda flytte eventuelle elementer

265
00:11:19,330 --> 00:11:22,490
den måde, vi ville have haft til med en fast længde array.

266
00:11:22,490 --> 00:11:26,020
>> Så hægtede lister er en grundlæggende, men vigtig, dynamisk datastruktur

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

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

269
00:11:31,260 --> 00:11:33,350
og som det ofte er tilfældet i datalogi,

270
00:11:33,350 --> 00:11:35,640
Det er vigtigt at vide, hvornår du skal bruge hvert værktøj,

271
00:11:35,640 --> 00:11:37,960
så du kan vælge det rigtige værktøj til det rigtige job.

272
00:11:37,960 --> 00:11:40,060
>> For mere praksis, så prøv at skrive funktioner til

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

274
00:11:42,080 --> 00:11:44,050
husk at være forsigtig med den rækkefølge, som du omarrangere

275
00:11:44,050 --> 00:11:47,430
Deres næste pointere at sikre, at du ikke mister en bid af din liste -

276
00:11:47,430 --> 00:11:50,200
eller en funktion til at tælle knudepunkter i et sammenkædet liste,

277
00:11:50,200 --> 00:11:53,280
eller en sjov en, at bytte om på rækkefølgen af ​​alle knudepunkter i en sammenkædet liste.

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