1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] I programmering behöver vi ofta för att representera listor över värden,

2
00:00:10,050 --> 00:00:12,840
såsom namnen på eleverna i ett avsnitt

3
00:00:12,840 --> 00:00:15,100
eller deras poäng på den senaste frågesporten.

4
00:00:15,100 --> 00:00:17,430
>> I C-språket, deklarerade arrayer kan användas

5
00:00:17,430 --> 00:00:19,160
att lagra listor.

6
00:00:19,160 --> 00:00:21,200
Det är lätt att räkna upp elementen i en lista

7
00:00:21,200 --> 00:00:23,390
lagras i en array, och om du behöver komma åt

8
00:00:23,390 --> 00:00:25,050
eller ändra den i: te listelement

9
00:00:25,050 --> 00:00:27,570
för någon godtycklig index I,

10
00:00:27,570 --> 00:00:29,910
som kan göras i konstant tid,

11
00:00:29,910 --> 00:00:31,660
men arrayer har nackdelar också.

12
00:00:31,660 --> 00:00:33,850
>> När vi förklarar dem, vi måste säga

13
00:00:33,850 --> 00:00:35,900
på framsidan hur stora de är,

14
00:00:35,900 --> 00:00:38,160
det vill säga hur många element som de kan lagra

15
00:00:38,160 --> 00:00:40,780
och hur stor dessa element är, som bestäms av deras typ.

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

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

18
00:00:48,220 --> 00:00:50,200
som är storleken på en int.

19
00:00:50,200 --> 00:00:52,590
>> Vi kan inte ändra en rad storlek efter anmälan.

20
00:00:52,590 --> 00:00:55,290
Vi måste göra en ny array om vi vill lagra fler element.

21
00:00:55,290 --> 00:00:57,410
Anledningen till att denna begränsning finns är att vår

22
00:00:57,410 --> 00:00:59,040
Programmet lagrar hela uppsättningen

23
00:00:59,040 --> 00:01:02,310
som en sammanhängande bit av minne.

24
00:01:02,310 --> 00:01:04,500
Säga att detta är den buffert där vi lagras i vår grupp.

25
00:01:04,500 --> 00:01:06,910
Det kan finnas andra variabler

26
00:01:06,910 --> 00:01:08,310
ligger intill matrisen

27
00:01:08,310 --> 00:01:10,060
i minnet, så att vi inte kan

28
00:01:10,060 --> 00:01:12,060
bara göra arrayen större.

29
00:01:12,060 --> 00:01:15,700
>> Ibland vill vi handla arrayen snabba dataåtkomst hastighet

30
00:01:15,700 --> 00:01:17,650
för lite mer flexibilitet.

31
00:01:17,650 --> 00:01:20,380
Ange den länkade listan, en annan grundläggande datastruktur

32
00:01:20,380 --> 00:01:22,360
du kanske inte så bekant med.

33
00:01:22,360 --> 00:01:24,200
På en hög nivå,

34
00:01:24,200 --> 00:01:26,840
en länkad lista lagrar data i en sekvens av noder

35
00:01:26,840 --> 00:01:29,280
som är anslutna till varandra med länkar,

36
00:01:29,280 --> 00:01:31,760
därav namnet "länkad lista".

37
00:01:31,760 --> 00:01:33,840
Som vi ser, denna skillnad i design

38
00:01:33,840 --> 00:01:35,500
leder till olika fördelar och nackdelar

39
00:01:35,500 --> 00:01:37,000
än en matris.

40
00:01:37,000 --> 00:01:39,840
>> Här är några C-kod för en länkad mycket enkel lista med heltal.

41
00:01:39,840 --> 00:01:42,190
Du kan se att vi har representerade varje nod

42
00:01:42,190 --> 00:01:45,520
i listan som en struct som innehåller 2 saker,

43
00:01:45,520 --> 00:01:47,280
ett heltal för att lagra kallas "Val '

44
00:01:47,280 --> 00:01:50,460
och en länk till nästa nod på listan

45
00:01:50,460 --> 00:01:52,990
som vi representerar som en pekare som kallas "Nästa".

46
00:01:54,120 --> 00:01:56,780
På detta sätt, kan vi spåra hela listan

47
00:01:56,780 --> 00:01:58,790
med bara en enda pekare till den 1: a noden,

48
00:01:58,790 --> 00:02:01,270
och då kan vi följa nästa pekare

49
00:02:01,270 --> 00:02:03,130
till den 2: a noden,

50
00:02:03,130 --> 00:02:05,280
till den 3: e noden,

51
00:02:05,280 --> 00:02:07,000
till 4: e noden,

52
00:02:07,000 --> 00:02:09,889
och så vidare, tills vi kommer till slutet av listan.

53
00:02:10,520 --> 00:02:12,210
>> Du kanske kan se en fördel har detta

54
00:02:12,210 --> 00:02:14,490
över den statiska matrisstruktur - med en länkad lista,

55
00:02:14,490 --> 00:02:16,450
Vi behöver inte en stor bit av minnet helt och hållet.

56
00:02:17,400 --> 00:02:20,530
Den 1: a noden i listan kunde leva på denna plats i minnet,

57
00:02:20,530 --> 00:02:23,160
och 2nd noden kan vara ända hit.

58
00:02:23,160 --> 00:02:25,780
Vi kan få till alla noder oavsett var i minnet de är,

59
00:02:25,780 --> 00:02:28,890
eftersom start vid 1: a noden varje nod nästa pekare

60
00:02:28,890 --> 00:02:31,700
berättar exakt vart man ska gå härnäst.

61
00:02:31,700 --> 00:02:33,670
>> Dessutom behöver vi inte säga upp front

62
00:02:33,670 --> 00:02:36,740
hur stor en länkad lista kommer att vara hur vi gör med statiska arrayer,

63
00:02:36,740 --> 00:02:39,060
eftersom vi kan fortsätta att lägga noder i en lista

64
00:02:39,060 --> 00:02:42,600
så länge det finns utrymme någonstans i minnet för nya noder.

65
00:02:42,600 --> 00:02:45,370
Därför länkade listor är lätta att ändra storlek dynamiskt.

66
00:02:45,370 --> 00:02:47,950
Säg, senare i programmet måste vi lägga till fler noder

67
00:02:47,950 --> 00:02:49,350
i vår lista.

68
00:02:49,350 --> 00:02:51,480
Om du vill infoga en ny nod i vår lista i farten,

69
00:02:51,480 --> 00:02:53,740
allt vi behöver göra är att allokera minne för denna nod,

70
00:02:53,740 --> 00:02:55,630
plopp i datavärdet,

71
00:02:55,630 --> 00:02:59,070
och sedan placera den där vi vill genom att justera lämpliga pekare.

72
00:02:59,070 --> 00:03:02,310
>> Till exempel, om vi ville placera en nod i mellan

73
00:03:02,310 --> 00:03:04,020
den 2: a och 3: e noder i listan,

74
00:03:04,020 --> 00:03:06,800
 Vi skulle inte behöva flytta 2 eller 3 noder alls.

75
00:03:06,800 --> 00:03:09,190
Säg att vi sätter denna röda nod.

76
00:03:09,190 --> 00:03:12,890
Allt vi skulle behöva göra är att ställa den nya noden nästa pekare

77
00:03:12,890 --> 00:03:14,870
att peka på noden 3:e

78
00:03:14,870 --> 00:03:18,580
och sedan ReWire 2: a noden nästa pekare

79
00:03:18,580 --> 00:03:20,980
att peka på vår nya noden.

80
00:03:22,340 --> 00:03:24,370
Så kan vi ändra storleken våra listor på fluga

81
00:03:24,370 --> 00:03:26,090
eftersom vår dator inte är beroende av indexering,

82
00:03:26,090 --> 00:03:28,990
utan snarare på att koppla med pekare för att lagra dem.

83
00:03:29,120 --> 00:03:31,600
>> Emellertid, en nackdel med länkade listor

84
00:03:31,600 --> 00:03:33,370
är att, till skillnad från en statisk matris,

85
00:03:33,370 --> 00:03:36,690
datorn kan inte bara hoppa till mitten av listan.

86
00:03:38,040 --> 00:03:40,780
Eftersom datorn har att besöka varje nod i den länkade listan

87
00:03:40,780 --> 00:03:42,330
för att komma till nästa,

88
00:03:42,330 --> 00:03:44,770
det kommer att ta längre tid att hitta en viss nod

89
00:03:44,770 --> 00:03:46,400
än den skulle i en array.

90
00:03:46,400 --> 00:03:48,660
Att korsa hela listan tar tid proportionell

91
00:03:48,660 --> 00:03:50,580
till längden av listan,

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 genomsnitt, når varje nod

94
00:03:56,510 --> 00:03:58,800
också tar tid proportionell mot n..

95
00:03:58,800 --> 00:04:00,700
>> Nu ska vi faktiskt skriva lite kod

96
00:04:00,700 --> 00:04:02,000
som arbetar med länkade listor.

97
00:04:02,000 --> 00:04:04,220
Låt oss säga att vi vill ha en länkad lista av heltal.

98
00:04:04,220 --> 00:04:06,140
Vi kan representera en nod i vår lista igen

99
00:04:06,140 --> 00:04:08,340
som en struktur med 2 fält,

100
00:04:08,340 --> 00:04:10,750
ett heltal kallas "Val '

101
00:04:10,750 --> 00:04:13,490
och en nästa pekare till nästa nod på listan.

102
00:04:13,490 --> 00:04:15,660
Tja, det verkar enkelt nog.

103
00:04:15,660 --> 00:04:17,220
>> Låt oss säga att vi vill skriva en funktion

104
00:04:17,220 --> 00:04:19,329
som går igenom listan och skriver ut

105
00:04:19,329 --> 00:04:22,150
värde som lagras i den sista noden i listan.

106
00:04:22,150 --> 00:04:24,850
Tja, innebär att vi kommer att behöva korsa alla noder i listan

107
00:04:24,850 --> 00:04:27,310
att hitta den sista, men eftersom vi inte lägger

108
00:04:27,310 --> 00:04:29,250
eller ta bort något, vi vill inte ändra

109
00:04:29,250 --> 00:04:32,210
den interna strukturen för nästa pekare i listan.

110
00:04:32,210 --> 00:04:34,790
>> Så behöver vi en pekare speciellt för traversering

111
00:04:34,790 --> 00:04:36,940
som vi kallar "sökrobot".

112
00:04:36,940 --> 00:04:38,870
Det kommer att krypa igenom alla element i listan

113
00:04:38,870 --> 00:04:41,190
genom att följa kedjan av nästa pekare.

114
00:04:41,190 --> 00:04:43,750
Allt vi har lagrat en pekare till den 1: a noden,

115
00:04:43,750 --> 00:04:45,730
eller "chef" i listan.

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

117
00:04:47,370 --> 00:04:49,120
Det är av typen pekare-till-nod.

118
00:04:49,120 --> 00:04:51,280
>> För att få den verkliga 1:e nod i listan,

119
00:04:51,280 --> 00:04:53,250
vi dereference denna pekare,

120
00:04:53,250 --> 00:04:55,100
men innan vi kan dereference det måste vi kontrollera

121
00:04:55,100 --> 00:04:57,180
Om pekaren är null först.

122
00:04:57,180 --> 00:04:59,190
Om det är noll, är listan tom,

123
00:04:59,190 --> 00:05:01,320
och vi bör skriva ut ett budskap att eftersom listan är tom,

124
00:05:01,320 --> 00:05:03,250
det finns ingen sista nod.

125
00:05:03,250 --> 00:05:05,190
Men låt oss säga att listan inte är tom.

126
00:05:05,190 --> 00:05:08,340
Om det inte, bör vi krypa igenom hela listan

127
00:05:08,340 --> 00:05:10,440
tills vi kommer till den sista noden i listan,

128
00:05:10,440 --> 00:05:13,030
och hur kan vi berätta om vi tittar på den sista noden i listan?

129
00:05:13,670 --> 00:05:16,660
>> Tja, om en nod nästa pekare är null

130
00:05:16,660 --> 00:05:18,320
Vi vet att vi är i slutet

131
00:05:18,320 --> 00:05:22,390
sedan den senaste nästa pekare skulle ha någon nästa nod i listan för att peka på.

132
00:05:22,390 --> 00:05:26,590
Det är en god vana att alltid hålla den sista noden nästa pekare initieras till null

133
00:05:26,590 --> 00:05:30,800
att ha ett standardiserat egenskap som varnar oss när vi har nått slutet av listan.

134
00:05:30,800 --> 00:05:33,510
>> Så om sökrobot → Nästa är null,

135
00:05:34,120 --> 00:05:38,270
kom ihåg att pilen syntaxen är en genväg för att dereferencing

136
00:05:38,270 --> 00:05:40,010
en pekare till en struktur, och sedan komma

137
00:05:40,010 --> 00:05:42,510
nästa fält motsvarar besvärliga:

138
00:05:42,510 --> 00:05:48,750
(* Larvfötter). Nästa.

139
00:05:49,820 --> 00:05:51,260
När vi har hittat den sista noden,

140
00:05:51,260 --> 00:05:53,830
Vi vill skriva ut sökrobot → val,

141
00:05:53,830 --> 00:05:55,000
värdet i den aktuella noden

142
00:05:55,000 --> 00:05:57,130
som vi vet är den sista.

143
00:05:57,130 --> 00:05:59,740
Annars, om vi inte ännu på den sista noden i listan,

144
00:05:59,740 --> 00:06:02,340
Vi måste gå vidare till nästa nod i listan

145
00:06:02,340 --> 00:06:04,750
och kontrollera om det är den sista.

146
00:06:04,750 --> 00:06:07,010
För att göra detta, satte vi bara vår sökrobot pekare

147
00:06:07,010 --> 00:06:09,840
att peka på den aktuella noden nästa värde,

148
00:06:09,840 --> 00:06:11,680
dvs, den nästa nod i listan.

149
00:06:11,680 --> 00:06:13,030
Detta görs genom att ställa

150
00:06:13,030 --> 00:06:15,280
sökrobot = sökrobot → Nästa.

151
00:06:16,050 --> 00:06:18,960
Då vi upprepa denna process med en ögla till exempel,

152
00:06:18,960 --> 00:06:20,960
tills vi hittar den sista noden.

153
00:06:20,960 --> 00:06:23,150
Så, till exempel, om sökrobot pekade på huvudet,

154
00:06:24,050 --> 00:06:27,710
Vi satt sökrobot peka på sökrobot → nästa,

155
00:06:27,710 --> 00:06:30,960
som är densamma som nästa fält av den 1st noden.

156
00:06:30,960 --> 00:06:33,620
Så, nu är vår sökrobot pekar på 2. Noden,

157
00:06:33,620 --> 00:06:35,480
och, återigen, upprepar vi detta med en slinga,

158
00:06:37,220 --> 00:06:40,610
tills vi har hittat den sista noden, är att

159
00:06:40,610 --> 00:06:43,640
där noden nästa pekare pekar på null.

160
00:06:43,640 --> 00:06:45,070
Och där har vi det,

161
00:06:45,070 --> 00:06:47,620
Vi har hittat den sista noden i listan och skriva ut dess värde,

162
00:06:47,620 --> 00:06:50,800
Vi använder bara larvfötter → val.

163
00:06:50,800 --> 00:06:53,130
>> Tvärgående är inte så illa, men hur du sätter?

164
00:06:53,130 --> 00:06:56,290
Låt oss säga att vi vill infoga ett heltal i den 4: e positionen

165
00:06:56,290 --> 00:06:58,040
i ett heltal lista.

166
00:06:58,040 --> 00:07:01,280
Det är mellan de nuvarande 3 och 4 noder.

167
00:07:01,280 --> 00:07:03,760
Återigen måste vi korsa listan bara för att

168
00:07:03,760 --> 00:07:06,520
få till den 3: e elementet, ett vi sätter efter.

169
00:07:06,520 --> 00:07:09,300
Så skapar vi en sökrobot pekare igen korsa listan,

170
00:07:09,300 --> 00:07:11,400
kontrollera om vår framvisaren är null

171
00:07:11,400 --> 00:07:14,810
och om det inte pekar vår sökrobot pekare på huvudnoden.

172
00:07:16,880 --> 00:07:18,060
Så vi är på 1: a elementet.

173
00:07:18,060 --> 00:07:21,020
Vi måste gå framåt 2 fler element innan vi kan sätta in,

174
00:07:21,020 --> 00:07:23,390
så att vi kan använda en for-slinga

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

176
00:07:26,430 --> 00:07:28,590
och i varje iteration av slingan,

177
00:07:28,590 --> 00:07:31,540
öka vår sökrobot pekare fram 1 nod

178
00:07:31,540 --> 00:07:34,570
genom att kontrollera om den aktuella noden nästa fält är noll,

179
00:07:34,570 --> 00:07:37,550
och om det inte flyttar vår sökrobot pekare till nästa nod

180
00:07:37,550 --> 00:07:41,810
genom att ställa det lika med den aktuella noden nästa pekare.

181
00:07:41,810 --> 00:07:45,210
Så, eftersom vår för slinga säger att göra det

182
00:07:45,210 --> 00:07:47,550
två gånger,

183
00:07:49,610 --> 00:07:51,190
Vi har nått den 3: e noden,

184
00:07:51,190 --> 00:07:53,110
och när vår sökrobot pekare har nått noden efter

185
00:07:53,110 --> 00:07:55,270
som vi vill infoga vår nya heltal,

186
00:07:55,270 --> 00:07:57,050
hur vi faktiskt göra sätta?

187
00:07:57,050 --> 00:07:59,440
>> Tja, har vår nya heltal som skall införas i den förteckning

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

189
00:08:01,250 --> 00:08:03,140
eftersom detta är verkligen en sekvens av noder.

190
00:08:03,140 --> 00:08:05,690
Så, låt oss göra en ny pekare till noden

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

192
00:08:08,910 --> 00:08:11,800
och ställa in den att peka på minnet att vi nu fördela

193
00:08:11,800 --> 00:08:14,270
i stacken för själva noden,

194
00:08:14,270 --> 00:08:16,000
och hur mycket minne behöver vi fördela?

195
00:08:16,000 --> 00:08:18,250
Jo, storleken av en nod,

196
00:08:20,450 --> 00:08:23,410
och vi vill sätta sin val fält till heltal som vi vill infoga.

197
00:08:23,410 --> 00:08:25,590
Låt oss säga, 6.

198
00:08:25,590 --> 00:08:27,710
Nu innehåller noden vår heltalsvärde.

199
00:08:27,710 --> 00:08:30,650
Det är också bra att initiera den nya noden nästa fält

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

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

202
00:08:35,080 --> 00:08:37,179
>> Vi måste förändra den interna strukturen av listan

203
00:08:37,179 --> 00:08:40,409
och nästa pekare som finns i listan befintliga

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

205
00:08:42,950 --> 00:08:46,560
Eftersom nästa pekare bestämma i vilken ordning listan,

206
00:08:46,560 --> 00:08:48,650
och eftersom vi sätter vår nya noden

207
00:08:48,650 --> 00:08:50,510
rakt in i mitten av listan,

208
00:08:50,510 --> 00:08:52,010
det kan vara lite knepigt.

209
00:08:52,010 --> 00:08:54,250
Detta beror, kom ihåg, vår dator

210
00:08:54,250 --> 00:08:56,250
endast känner placeringen av noder i listan

211
00:08:56,250 --> 00:09:00,400
på grund av de nästa pekare lagrade i de tidigare noderna.

212
00:09:00,400 --> 00:09:03,940
Så, om vi någonsin förlorat reda på någon av dessa platser,

213
00:09:03,940 --> 00:09:06,860
säga genom att ändra en av de kommande pekare i vår lista,

214
00:09:06,860 --> 00:09:09,880
till exempel, säger vi ändrat

215
00:09:09,880 --> 00:09:12,920
den 3: e noden nästa fält

216
00:09:12,920 --> 00:09:15,610
att peka på någon nod hit.

217
00:09:15,610 --> 00:09:17,920
Vi skulle vara ute på tur, eftersom vi inte skulle

218
00:09:17,920 --> 00:09:20,940
har någon aning om var att hitta resten av listan,

219
00:09:20,940 --> 00:09:23,070
och det är naturligtvis riktigt illa.

220
00:09:23,070 --> 00:09:25,080
Så måste vi vara riktigt försiktig om beställning

221
00:09:25,080 --> 00:09:28,360
där vi manipulerar vår nästa pekare under införande.

222
00:09:28,360 --> 00:09:30,540
>> Så, för att förenkla detta, låt oss säga att

223
00:09:30,540 --> 00:09:32,220
vår första 4 noder

224
00:09:32,220 --> 00:09:36,200
kallas A, B, C och D, med pilarna representerar kedjan av pekare

225
00:09:36,200 --> 00:09:38,070
som ansluter noderna.

226
00:09:38,070 --> 00:09:40,050
Så måste vi sätta vår nya noden

227
00:09:40,050 --> 00:09:42,070
mellan noderna C och D.

228
00:09:42,070 --> 00:09:45,060
Det är viktigt att göra det i rätt ordning, och jag ska visa dig varför.

229
00:09:45,060 --> 00:09:47,500
>> Låt oss titta på fel sätt att göra det först.

230
00:09:47,500 --> 00:09:49,490
Hej, vi vet den nya noden måste komma direkt efter C,

231
00:09:49,490 --> 00:09:51,910
så låt oss ställa C: s nästa pekare

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

233
00:09:56,530 --> 00:09:59,180
Okej, verkar okej, vi bara avsluta nu genom

234
00:09:59,180 --> 00:10:01,580
gör den nya noden nästa pekare pekar på D,

235
00:10:01,580 --> 00:10:03,250
men vänta, hur kan vi göra det?

236
00:10:03,250 --> 00:10:05,170
Det enda som skulle kunna tala om för oss där D var,

237
00:10:05,170 --> 00:10:07,630
var nästa pekare lagrad tidigare i C,

238
00:10:07,630 --> 00:10:09,870
men vi skrev bara att pekaren

239
00:10:09,870 --> 00:10:11,170
att peka till den nya noden,

240
00:10:11,170 --> 00:10:14,230
så vi inte längre har någon aning där D är i minnet,

241
00:10:14,230 --> 00:10:17,020
och vi har förlorat resten av listan.

242
00:10:17,020 --> 00:10:19,000
Inte bra alls.

243
00:10:19,000 --> 00:10:21,090
>> Så, hur vi gör detta rätt?

244
00:10:22,360 --> 00:10:25,090
Först pekar den nya noden nästa pekare vid D.

245
00:10:26,170 --> 00:10:28,990
Nu, både den nya nodens och C: s nästa pekare

246
00:10:28,990 --> 00:10:30,660
pekar på samma nod, D,

247
00:10:30,660 --> 00:10:32,290
men det är bra.

248
00:10:32,290 --> 00:10:35,680
Nu kan vi punkt C nästa pekare på den nya noden.

249
00:10:37,450 --> 00:10:39,670
Så har vi gjort detta utan att förlora några data.

250
00:10:39,670 --> 00:10:42,280
I kod, C är aktuella noden

251
00:10:42,280 --> 00:10:45,540
att förflyttning pekaren sökrobot pekar på,

252
00:10:45,540 --> 00:10:50,400
och D representeras av noden pekas på av den aktuella noden nästa fält,

253
00:10:50,400 --> 00:10:52,600
eller larvfötter → Nästa.

254
00:10:52,600 --> 00:10:55,460
Så ställer vi först den nya noden nästa pekare

255
00:10:55,460 --> 00:10:57,370
att peka på sökrobot → nästa,

256
00:10:57,370 --> 00:11:00,880
på samma sätt som vi sa new_node nästa pekare bör

257
00:11:00,880 --> 00:11:02,780
peka till D i figuren.

258
00:11:02,780 --> 00:11:04,540
Då kan vi ställa den aktuella noden nästa pekare

259
00:11:04,540 --> 00:11:06,330
till vår nya noden,

260
00:11:06,330 --> 00:11:10,980
precis som vi var tvungna att vänta till punkt C för att new_node på ritningen.

261
00:11:10,980 --> 00:11:12,250
Nu allt är i ordning, och vi inte förlorar

262
00:11:12,250 --> 00:11:14,490
reda på alla uppgifter, och vi kunde bara

263
00:11:14,490 --> 00:11:16,200
hålla vår nya nod i mitten av listan

264
00:11:16,200 --> 00:11:19,330
utan att bygga om hela eller ens flytta några element

265
00:11:19,330 --> 00:11:22,490
det sätt vi skulle ha behövt en fast längd matris.

266
00:11:22,490 --> 00:11:26,020
>> Så, länkade listor är en grundläggande, men viktiga, dynamiska datastruktur

267
00:11:26,020 --> 00:11:29,080
som har både fördelar och nackdelar

268
00:11:29,080 --> 00:11:31,260
jämfört med matriser och andra datastrukturer,

269
00:11:31,260 --> 00:11:33,350
och som ofta är fallet i datavetenskap,

270
00:11:33,350 --> 00:11:35,640
Det är viktigt att veta när du ska använda varje verktyg,

271
00:11:35,640 --> 00:11:37,960
så att du kan välja rätt verktyg för rätt jobb.

272
00:11:37,960 --> 00:11:40,060
>> För mer övning, försök att skriva funktioner

273
00:11:40,060 --> 00:11:42,080
bort noder från en länkad lista -

274
00:11:42,080 --> 00:11:44,050
kom ihåg att vara försiktig om i vilken ordning du ordna

275
00:11:44,050 --> 00:11:47,430
ditt nästa pekare för att säkerställa att du inte förlorar en bit av din lista -

276
00:11:47,430 --> 00:11:50,200
eller en funktion för att räkna noderna i en länkad lista,

277
00:11:50,200 --> 00:11:53,280
eller en rolig en, för att kasta om ordningen av alla noder i en länkad lista.

278
00:11:53,280 --> 00:11:56,090
>> Mitt namn är Jackson Steinkamp, ​​det här CS50.