1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] V programování, často potřebujeme reprezentovat seznamy hodnot,

2
00:00:10,050 --> 00:00:12,840
například názvy studentů v sekci

3
00:00:12,840 --> 00:00:15,100
nebo jejich skóre na poslední kvízu.

4
00:00:15,100 --> 00:00:17,430
>> V jazyce C, prohlásila pole mohou být použity

5
00:00:17,430 --> 00:00:19,160
uložit seznamy.

6
00:00:19,160 --> 00:00:21,200
Je to snadné vyjmenovat prvky seznamu

7
00:00:21,200 --> 00:00:23,390
uloženy v poli, a pokud budete potřebovat pro přístup k

8
00:00:23,390 --> 00:00:25,050
nebo upravit Ith prvek seznamu

9
00:00:25,050 --> 00:00:27,570
pro nějaký svévolný index I,

10
00:00:27,570 --> 00:00:29,910
který může být proveden v konstantním čase,

11
00:00:29,910 --> 00:00:31,660
ale pole mají nevýhody.

12
00:00:31,660 --> 00:00:33,850
>> Když jsme je deklarovat, že jsme povinni říci

13
00:00:33,850 --> 00:00:35,900
up front, jak velké jsou,

14
00:00:35,900 --> 00:00:38,160
že je, kolik prvků, které mohou uložit

15
00:00:38,160 --> 00:00:40,780
a jak velké tyto prvky jsou, která je určena jejich typu.

16
00:00:40,780 --> 00:00:45,450
Například, int arr (10)

17
00:00:45,450 --> 00:00:48,220
lze uložit 10 položek

18
00:00:48,220 --> 00:00:50,200
že jsou o velikosti typu int.

19
00:00:50,200 --> 00:00:52,590
>> Nemůžeme změnit celou řadu jeho velikost po vyhlášení.

20
00:00:52,590 --> 00:00:55,290
Musíme vytvořit nové pole, pokud chceme uložit více prvků.

21
00:00:55,290 --> 00:00:57,410
Důvodem toto omezení existuje, je, že naše

22
00:00:57,410 --> 00:00:59,040
Program ukládá celou řadu

23
00:00:59,040 --> 00:01:02,310
jako souvislý kus paměti.

24
00:01:02,310 --> 00:01:04,500
Řekněme to je vyrovnávací paměť, kde se uloží v našem poli.

25
00:01:04,500 --> 00:01:06,910
Tam by mohlo být jiné proměnné

26
00:01:06,910 --> 00:01:08,310
Nachází se hned vedle pole

27
00:01:08,310 --> 00:01:10,060
v paměti, takže nemůžeme

28
00:01:10,060 --> 00:01:12,060
jen aby pole větší.

29
00:01:12,060 --> 00:01:15,700
>> Někdy jsme chtěli obchodovat Array je rychlý přístup k datům rychlostí

30
00:01:15,700 --> 00:01:17,650
o trochu více flexibility.

31
00:01:17,650 --> 00:01:20,380
Zadejte spojový seznam, další základní údaje struktura

32
00:01:20,380 --> 00:01:22,360
nemusíte být obeznámeni s.

33
00:01:22,360 --> 00:01:24,200
Na vysoké úrovni,

34
00:01:24,200 --> 00:01:26,840
spojový seznam ukládá data v pořadí uzlů

35
00:01:26,840 --> 00:01:29,280
, které jsou vzájemně propojeny s odkazy,

36
00:01:29,280 --> 00:01:31,760
Odtud název "spojový seznam."

37
00:01:31,760 --> 00:01:33,840
Jak uvidíme, tento rozdíl v designu

38
00:01:33,840 --> 00:01:35,500
vede k různým výhodám a nevýhodám

39
00:01:35,500 --> 00:01:37,000
než pole.

40
00:01:37,000 --> 00:01:39,840
>> Zde je nějaký kód C pro velmi jednoduché propojeného seznamu celých čísel.

41
00:01:39,840 --> 00:01:42,190
Můžete vidět, že jsme zástupci každý uzel

42
00:01:42,190 --> 00:01:45,520
v seznamu jako struct, který obsahuje 2 věci,

43
00:01:45,520 --> 00:01:47,280
číslo uložit tzv. "val"

44
00:01:47,280 --> 00:01:50,460
a odkaz na další uzel v seznamu

45
00:01:50,460 --> 00:01:52,990
které představují jako ukazatel s názvem "Další."

46
00:01:54,120 --> 00:01:56,780
Tímto způsobem, lze sledovat celý seznam

47
00:01:56,780 --> 00:01:58,790
pouze s jedním ukazatel na uzel 1st,

48
00:01:58,790 --> 00:02:01,270
a pak můžeme sledovat další ukazatele

49
00:02:01,270 --> 00:02:03,130
na druhé uzlu,

50
00:02:03,130 --> 00:02:05,280
na 3. uzlu,

51
00:02:05,280 --> 00:02:07,000
na 4. uzlu,

52
00:02:07,000 --> 00:02:09,889
a tak dále, dokud se na konec seznamu.

53
00:02:10,520 --> 00:02:12,210
>> Ty by mohly být schopni vidět 1 výhodu to má

54
00:02:12,210 --> 00:02:14,490
přes statické pole struktury - s propojeného seznamu,

55
00:02:14,490 --> 00:02:16,450
nepotřebujeme velký kus paměti dohromady.

56
00:02:17,400 --> 00:02:20,530
1. uzel seznamu by mohl žít na tomto místě v paměti,

57
00:02:20,530 --> 00:02:23,160
a 2. uzel by mohl být po celou cestu sem.

58
00:02:23,160 --> 00:02:25,780
Můžeme dostat do všech uzlů bez ohledu na to, kde v paměti jsou,

59
00:02:25,780 --> 00:02:28,890
protože začíná v uzlu 1st, každý uzel příští ukazatel

60
00:02:28,890 --> 00:02:31,700
nám říká přesně, kam jít dál.

61
00:02:31,700 --> 00:02:33,670
>> Navíc, nemáme říkat dopředu

62
00:02:33,670 --> 00:02:36,740
jak velký spojový seznam bude stejným způsobem jako my se statickými poli,

63
00:02:36,740 --> 00:02:39,060
protože můžeme držet přidání uzlů do seznamu

64
00:02:39,060 --> 00:02:42,600
jak dlouho jak tam je prostor někde v paměti pro nové uzly.

65
00:02:42,600 --> 00:02:45,370
Proto, propojené seznamy snadno změnit velikost dynamicky.

66
00:02:45,370 --> 00:02:47,950
Řekni, později v programu musíme přidat další uzly

67
00:02:47,950 --> 00:02:49,350
do našeho seznamu.

68
00:02:49,350 --> 00:02:51,480
Chcete-li vložit nový uzel do našeho seznamu za běhu,

69
00:02:51,480 --> 00:02:53,740
všechno, co musíme udělat, je alokovat paměť pro tento uzel,

70
00:02:53,740 --> 00:02:55,630
plop v datové hodnoty,

71
00:02:55,630 --> 00:02:59,070
a pak na místo, kde chceme úpravou vhodné ukazatele.

72
00:02:59,070 --> 00:03:02,310
>> Například, pokud chceme umístit uzel mezi

73
00:03:02,310 --> 00:03:04,020
2. a 3. uzly seznamu,

74
00:03:04,020 --> 00:03:06,800
 bychom neměli přesunout 2. nebo 3. uzly vůbec.

75
00:03:06,800 --> 00:03:09,190
Řekněme, že jsme vložením tuto červenou uzel.

76
00:03:09,190 --> 00:03:12,890
Vše budeme muset udělat, je nastavit nový uzel je další ukazatel

77
00:03:12,890 --> 00:03:14,870
poukázat na 3. uzlu

78
00:03:14,870 --> 00:03:18,580
a potom přepojit druhé uzlu je další ukazatel

79
00:03:18,580 --> 00:03:20,980
upozornit na náš nový uzel.

80
00:03:22,340 --> 00:03:24,370
Takže, můžeme měnit velikost své seznamy za běhu

81
00:03:24,370 --> 00:03:26,090
protože náš počítač nespoléhá na indexování,

82
00:03:26,090 --> 00:03:28,990
ale spíše na propojení s ukazateli jejich uložení.

83
00:03:29,120 --> 00:03:31,600
>> Nicméně, nevýhodou spojené seznamy

84
00:03:31,600 --> 00:03:33,370
je skutečnost, že na rozdíl od statické pole,

85
00:03:33,370 --> 00:03:36,690
Počítač nemůže jen tak skočit do středu seznamu.

86
00:03:38,040 --> 00:03:40,780
Vzhledem k tomu, že počítač má navštívit každý uzel v propojeném seznamu

87
00:03:40,780 --> 00:03:42,330
se dostat na další,

88
00:03:42,330 --> 00:03:44,770
to bude trvat déle najít určitý uzel

89
00:03:44,770 --> 00:03:46,400
, než by se v poli.

90
00:03:46,400 --> 00:03:48,660
Přejít celý seznam trvá dlouho úměrná

91
00:03:48,660 --> 00:03:50,580
k délce seznamu,

92
00:03:50,580 --> 00:03:54,630
nebo O (n) v asymptotické notaci.

93
00:03:54,630 --> 00:03:56,510
V průměru, dosažení libovolného uzlu

94
00:03:56,510 --> 00:03:58,800
bere rovněž časově proporcionální k n..

95
00:03:58,800 --> 00:04:00,700
>> Nyní, pojďme vlastně napsat nějaký kód

96
00:04:00,700 --> 00:04:02,000
, který pracuje s lineárními seznamy.

97
00:04:02,000 --> 00:04:04,220
Řekněme, že chceme propojeného seznamu celých čísel.

98
00:04:04,220 --> 00:04:06,140
Můžeme reprezentovat uzel v našem seznamu znovu

99
00:04:06,140 --> 00:04:08,340
jako struct s 2 polí,

100
00:04:08,340 --> 00:04:10,750
celočíselná hodnota tzv. "val"

101
00:04:10,750 --> 00:04:13,490
a další ukazatel na další uzel seznamu.

102
00:04:13,490 --> 00:04:15,660
No, vypadá docela jednoduché.

103
00:04:15,660 --> 00:04:17,220
>> Řekněme, že chcete napsat funkci

104
00:04:17,220 --> 00:04:19,329
který překročí seznamu a vytiskne

105
00:04:19,329 --> 00:04:22,150
Hodnota uložená v posledním uzlu seznamu.

106
00:04:22,150 --> 00:04:24,850
No, to znamená, že budeme muset přejít všechny uzly v seznamu

107
00:04:24,850 --> 00:04:27,310
najít ten poslední, ale protože nejsme přidání

108
00:04:27,310 --> 00:04:29,250
nebo cokoli smazali, nechceme měnit

109
00:04:29,250 --> 00:04:32,210
vnitřní struktura dalších ukazatelů v seznamu.

110
00:04:32,210 --> 00:04:34,790
>> Takže, budeme potřebovat ukazatel speciálně pro průchod

111
00:04:34,790 --> 00:04:36,940
které budeme nazývat "prolézací modul."

112
00:04:36,940 --> 00:04:38,870
To bude procházet přes všechny prvky seznamu

113
00:04:38,870 --> 00:04:41,190
podle pokynů řetězce dalších ukazatelů.

114
00:04:41,190 --> 00:04:43,750
Vše máme uloženy, je ukazatel na uzel 1st,

115
00:04:43,750 --> 00:04:45,730
nebo "hlava" ze seznamu.

116
00:04:45,730 --> 00:04:47,370
Head poukazuje na 1. uzlu.

117
00:04:47,370 --> 00:04:49,120
Je to typu pointer-to-uzlu.

118
00:04:49,120 --> 00:04:51,280
>> Chcete-li získat aktuální první uzel v seznamu,

119
00:04:51,280 --> 00:04:53,250
musíme dereference tento ukazatel,

120
00:04:53,250 --> 00:04:55,100
ale před tím, než může dereference to, musíme zkontrolovat

121
00:04:55,100 --> 00:04:57,180
v případě, že ukazatel je null první.

122
00:04:57,180 --> 00:04:59,190
Pokud je to null, seznam je prázdný,

123
00:04:59,190 --> 00:05:01,320
a my bychom měli vytisknout zprávu, že, protože seznam je prázdný,

124
00:05:01,320 --> 00:05:03,250
není poslední uzel.

125
00:05:03,250 --> 00:05:05,190
Ale řekněme, že seznam není prázdný.

126
00:05:05,190 --> 00:05:08,340
Pokud tomu tak není, pak bychom měli procházet celý seznam

127
00:05:08,340 --> 00:05:10,440
dokud se na poslední uzel seznamu,

128
00:05:10,440 --> 00:05:13,030
a jak můžeme říct, jestli se díváme na poslední uzel v seznamu?

129
00:05:13,670 --> 00:05:16,660
>> No, pokud uzel je další ukazatel je null,

130
00:05:16,660 --> 00:05:18,320
my víme, že jsme na konci

131
00:05:18,320 --> 00:05:22,390
od posledního další ukazatel by neměl další uzel v seznamu, aby ukazoval na.

132
00:05:22,390 --> 00:05:26,590
Je dobrým zvykem vždy poslední uzel je další ukazatel inicializován null

133
00:05:26,590 --> 00:05:30,800
mít standardizovanou vlastnost, která upozorní nás, když jsme došli na konec seznamu.

134
00:05:30,800 --> 00:05:33,510
>> Takže, pokud crawler → další je null,

135
00:05:34,120 --> 00:05:38,270
nezapomeňte, že šipka syntaxe je zkratka pro dereferencing

136
00:05:38,270 --> 00:05:40,010
ukazatel na struct, pak přístup

137
00:05:40,010 --> 00:05:42,510
její další pole odpovídá nepříjemné:

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

139
00:05:49,820 --> 00:05:51,260
Jakmile jsme našli poslední uzel,

140
00:05:51,260 --> 00:05:53,830
chceme tisknout prolézacího → val,

141
00:05:53,830 --> 00:05:55,000
hodnota v aktuálním uzlu

142
00:05:55,000 --> 00:05:57,130
které známe, je poslední.

143
00:05:57,130 --> 00:05:59,740
V opačném případě, když jsme ještě na poslední uzlu v seznamu,

144
00:05:59,740 --> 00:06:02,340
musíme přesunout na další uzel v seznamu

145
00:06:02,340 --> 00:06:04,750
a zkontrolujte, zda je to poslední.

146
00:06:04,750 --> 00:06:07,010
Chcete-li to, jen jsme nastavili pásové ukazatel

147
00:06:07,010 --> 00:06:09,840
bodu za aktuálním uzlem je další hodnoty,

148
00:06:09,840 --> 00:06:11,680
to znamená, že další uzel v seznamu.

149
00:06:11,680 --> 00:06:13,030
To se provádí nastavením

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → další.

151
00:06:16,050 --> 00:06:18,960
Pak se tento proces opakovat, se smyčkou například,

152
00:06:18,960 --> 00:06:20,960
dokud nenajdeme poslední uzel.

153
00:06:20,960 --> 00:06:23,150
Tak například, jestliže pásový ukazoval na hlavu,

154
00:06:24,050 --> 00:06:27,710
jsme se vydali prolézací modul, aby ukazoval na pásový → Další,

155
00:06:27,710 --> 00:06:30,960
který je stejný jako další oblasti prvního uzlu.

156
00:06:30,960 --> 00:06:33,620
Takže, teď náš prohledávač ukazuje na 2. uzlu,

157
00:06:33,620 --> 00:06:35,480
a opět, opakujeme to se smyčkou,

158
00:06:37,220 --> 00:06:40,610
až jsme zjistili, poslední uzel, který je,

159
00:06:40,610 --> 00:06:43,640
kde uzlu další ukazatel ukazuje na null.

160
00:06:43,640 --> 00:06:45,070
A tady to máme,

161
00:06:45,070 --> 00:06:47,620
jsme našli poslední uzel v seznamu, a vytisknout svou hodnotu,

162
00:06:47,620 --> 00:06:50,800
stačí použít pásový → val.

163
00:06:50,800 --> 00:06:53,130
>> Pojezdu není tak špatné, ale co o vkládání?

164
00:06:53,130 --> 00:06:56,290
Řekněme, že chceme vložit celé číslo do 4. místě

165
00:06:56,290 --> 00:06:58,040
v celé číslo seznamu.

166
00:06:58,040 --> 00:07:01,280
To je mezi současnými 3. a 4. uzlů.

167
00:07:01,280 --> 00:07:03,760
Opět musíme procházet seznam jen

168
00:07:03,760 --> 00:07:06,520
dostat do 3. prvek, jeden jsme vkládání po.

169
00:07:06,520 --> 00:07:09,300
Takže, jsme vytvořit prolézacího ukazatel znovu procházet seznam,

170
00:07:09,300 --> 00:07:11,400
zkontrolujte, zda naše hlava ukazatel je null,

171
00:07:11,400 --> 00:07:14,810
a pokud tomu tak není, přejděte náš prohledávač ukazatel na hlavním uzlu.

172
00:07:16,880 --> 00:07:18,060
Takže, jsme na 1. prvek.

173
00:07:18,060 --> 00:07:21,020
Musíme jít vpřed 2 více prvků, než můžeme vložit,

174
00:07:21,020 --> 00:07:23,390
takže můžeme použít pro smyčce

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

176
00:07:26,430 --> 00:07:28,590
a v každém opakování smyčky,

177
00:07:28,590 --> 00:07:31,540
Rozšíření našich pásový ukazatel vpřed o 1 uzel

178
00:07:31,540 --> 00:07:34,570
zkontrolovat, zda je aktuální uzel je další pole null,

179
00:07:34,570 --> 00:07:37,550
a je-li to není, přesunout naše pásový ukazatel na další uzel

180
00:07:37,550 --> 00:07:41,810
nastavením je roven aktuálnímu uzlu příštího ukazatel.

181
00:07:41,810 --> 00:07:45,210
Takže, protože naše cyklu for říká k tomu, že

182
00:07:45,210 --> 00:07:47,550
dvakrát,

183
00:07:49,610 --> 00:07:51,190
jsme dosáhli 3. uzel,

184
00:07:51,190 --> 00:07:53,110
a poté, co náš prohledávač ukazatel dosáhl uzel po

185
00:07:53,110 --> 00:07:55,270
které chceme vložit náš nový integer,

186
00:07:55,270 --> 00:07:57,050
Jak jsme vlastně se liší vkládání?

187
00:07:57,050 --> 00:07:59,440
>> No, náš nový integer musí být vložen do seznamu

188
00:07:59,440 --> 00:08:01,250
jako součást vlastního uzlu struct,

189
00:08:01,250 --> 00:08:03,140
, protože to je ve skutečnosti sekvence uzlů.

190
00:08:03,140 --> 00:08:05,690
Takže, pojďme se nový ukazatel na uzel

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

192
00:08:08,910 --> 00:08:11,800
a nastavte ji upozornit na paměti, že jsme nyní přidělit

193
00:08:11,800 --> 00:08:14,270
na haldě pro uzel sám,

194
00:08:14,270 --> 00:08:16,000
a kolik paměti potřebujeme přidělit?

195
00:08:16,000 --> 00:08:18,250
No, o velikosti uzlu,

196
00:08:20,450 --> 00:08:23,410
a chceme nastavit svůj val pole na celé číslo, které chceme vložit.

197
00:08:23,410 --> 00:08:25,590
Řekněme, 6.

198
00:08:25,590 --> 00:08:27,710
Nyní, uzel obsahuje náš celočíselnou hodnotu.

199
00:08:27,710 --> 00:08:30,650
Je také dobrým zvykem inicializovat nový uzel je další pole

200
00:08:30,650 --> 00:08:33,690
bodu na hodnotu null,

201
00:08:33,690 --> 00:08:35,080
ale co teď?

202
00:08:35,080 --> 00:08:37,179
>> Máme změnit vnitřní strukturu seznamu

203
00:08:37,179 --> 00:08:40,409
a další ukazatele obsažené v seznamu je existující

204
00:08:40,409 --> 00:08:42,950
3. a 4. uzly.

205
00:08:42,950 --> 00:08:46,560
Vzhledem k tomu, další ukazatele určují pořadí v seznamu,

206
00:08:46,560 --> 00:08:48,650
a od té doby jsme vložením náš nový uzel

207
00:08:48,650 --> 00:08:50,510
přímo do středu seznamu,

208
00:08:50,510 --> 00:08:52,010
to může být trochu složitější.

209
00:08:52,010 --> 00:08:54,250
To je proto, pamatujte, náš počítač

210
00:08:54,250 --> 00:08:56,250
zná jen umístění uzlů v seznamu

211
00:08:56,250 --> 00:09:00,400
protože z dalších ukazatelů uložených v předchozích uzlů.

212
00:09:00,400 --> 00:09:03,940
Takže, pokud se někdy ztratil některé z těchto lokalit,

213
00:09:03,940 --> 00:09:06,860
říci změnou jednoho z následujících ukazatelů v našem seznamu,

214
00:09:06,860 --> 00:09:09,880
Například, že jsme změnily

215
00:09:09,880 --> 00:09:12,920
od 3. uzlu vedle pole

216
00:09:12,920 --> 00:09:15,610
poukázat na některé uzlu sem.

217
00:09:15,610 --> 00:09:17,920
Byli bychom smůlu, protože bychom

218
00:09:17,920 --> 00:09:20,940
tušení, kde najít zbytek seznamu,

219
00:09:20,940 --> 00:09:23,070
a to je zřejmě opravdu špatné.

220
00:09:23,070 --> 00:09:25,080
Takže, musíme být opravdu pozor na jejich pořadí

221
00:09:25,080 --> 00:09:28,360
, ve kterém jsme se manipulovat naše další ukazatele během zavádění.

222
00:09:28,360 --> 00:09:30,540
>> Takže, zjednodušit to, řekněme, že

223
00:09:30,540 --> 00:09:32,220
naše první 4 uzly

224
00:09:32,220 --> 00:09:36,200
se nazývá A, B, C a D, s šipkami představující řetěz ukazatelů

225
00:09:36,200 --> 00:09:38,070
která spojují uzly.

226
00:09:38,070 --> 00:09:40,050
Takže, je nutné vložit náš nový uzel

227
00:09:40,050 --> 00:09:42,070
mezi uzly C a D.

228
00:09:42,070 --> 00:09:45,060
Je důležité, aby to ve správném pořadí, a já vám ukážu, proč.

229
00:09:45,060 --> 00:09:47,500
>> Pojďme se podívat na špatně se to udělat jako první.

230
00:09:47,500 --> 00:09:49,490
Hele, my víme, že nový uzel má přijít hned po C,

231
00:09:49,490 --> 00:09:51,910
takže se pojďme nastavit C je další ukazatel

232
00:09:51,910 --> 00:09:54,700
poukázat na new_node.

233
00:09:56,530 --> 00:09:59,180
Dobře, zdá se v pořádku, jen musíme dokončit již nyní

234
00:09:59,180 --> 00:10:01,580
Díky nového uzlu je další ukazatel bod D,

235
00:10:01,580 --> 00:10:03,250
Ale počkejte, jak můžeme udělat, že?

236
00:10:03,250 --> 00:10:05,170
Jediná věc, která by nám mohl říct, kde D je,

237
00:10:05,170 --> 00:10:07,630
byla další ukazatel dříve uložené v C,

238
00:10:07,630 --> 00:10:09,870
ale my prostě přepsal tento ukazatel

239
00:10:09,870 --> 00:10:11,170
přejděte na nový uzel,

240
00:10:11,170 --> 00:10:14,230
takže již nemáme ponětí, kde D je v paměti,

241
00:10:14,230 --> 00:10:17,020
a my jsme ztratili zbytek seznamu.

242
00:10:17,020 --> 00:10:19,000
Vůbec dobré.

243
00:10:19,000 --> 00:10:21,090
>> Tak, jak to uděláme toto právo?

244
00:10:22,360 --> 00:10:25,090
Za prvé, bodu nového uzlu je další ukazatel na D.

245
00:10:26,170 --> 00:10:28,990
Nyní, jak nový uzel je a C je další ukazatele

246
00:10:28,990 --> 00:10:30,660
směřují na stejný uzel, D,

247
00:10:30,660 --> 00:10:32,290
ale to je v pořádku.

248
00:10:32,290 --> 00:10:35,680
Nyní můžeme bod C je další ukazatel na nový uzel.

249
00:10:37,450 --> 00:10:39,670
Takže jsme udělali to bez ztráty dat.

250
00:10:39,670 --> 00:10:42,280
V kódu, C je aktuální uzel

251
00:10:42,280 --> 00:10:45,540
že traversal ukazatel prolézací modul ukazuje na,

252
00:10:45,540 --> 00:10:50,400
a D je reprezentován uzlem na který ukazuje aktuální uzlu následujícího pole,

253
00:10:50,400 --> 00:10:52,600
nebo pásovém podvozku → další.

254
00:10:52,600 --> 00:10:55,460
Takže, nejprve nastavte nový uzel je další ukazatel

255
00:10:55,460 --> 00:10:57,370
poukázat na pásový → Další,

256
00:10:57,370 --> 00:11:00,880
stejným způsobem jsme si řekli, new_node příští ukazatel by měl

257
00:11:00,880 --> 00:11:02,780
poukazují na D na obrázku.

258
00:11:02,780 --> 00:11:04,540
Pak můžeme nastavit aktuální uzel je další ukazatel

259
00:11:04,540 --> 00:11:06,330
do našeho nového uzlu,

260
00:11:06,330 --> 00:11:10,980
stejně jako jsme museli čekat, až bodu C na new_node ve výkresu.

261
00:11:10,980 --> 00:11:12,250
Nyní je všechno v pořádku, a my jsme neztratili

262
00:11:12,250 --> 00:11:14,490
přehled o veškerých údajů, a my jsme byli schopni jen

263
00:11:14,490 --> 00:11:16,200
držet náš nový uzel ve středu seznamu

264
00:11:16,200 --> 00:11:19,330
bez přestavět celou věc, nebo dokonce posunutí všechny prvky

265
00:11:19,330 --> 00:11:22,490
způsob, jakým by se museli s pevnou délkou pole.

266
00:11:22,490 --> 00:11:26,020
>> Takže, propojené seznamy jsou základní, ale důležité, dynamická datová struktura

267
00:11:26,020 --> 00:11:29,080
které mají výhody i nevýhody

268
00:11:29,080 --> 00:11:31,260
ve srovnání s poli a jiných datových struktur,

269
00:11:31,260 --> 00:11:33,350
a jak je tomu často v informatice,

270
00:11:33,350 --> 00:11:35,640
je důležité vědět, kdy použít každý nástroj,

271
00:11:35,640 --> 00:11:37,960
takže si můžete vybrat ten správný nástroj na správné místo.

272
00:11:37,960 --> 00:11:40,060
>> Pro více praxe, zkuste napsat funkce

273
00:11:40,060 --> 00:11:42,080
odstranění uzlů z propojeného seznamu -

274
00:11:42,080 --> 00:11:44,050
nezapomeňte dávat pozor na pořadí, ve kterém jste změny uspořádání

275
00:11:44,050 --> 00:11:47,430
vaše další ukazatele, aby zajistily, že neztratíte kus svého seznamu -

276
00:11:47,430 --> 00:11:50,200
nebo funkci počítat uzly v propojeném seznamu,

277
00:11:50,200 --> 00:11:53,280
nebo legrace jeden, obrátit pořadí všech uzlů v propojeném seznamu.

278
00:11:53,280 --> 00:11:56,090
>> Jmenuji se Jackson Steinkamp, ​​je to CS50.