1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Sa programming, madalas naming kailangan upang kumatawan sa listahan ng mga halaga,

2
00:00:10,050 --> 00:00:12,840
tulad ng mga pangalan ng mga mag-aaral sa isang seksyon

3
00:00:12,840 --> 00:00:15,100
o ang kanilang mga marka sa mga pinakabagong pagsusulit.

4
00:00:15,100 --> 00:00:17,430
>> Sa wika ng C, ipinahayag array ay maaaring magamit

5
00:00:17,430 --> 00:00:19,160
upang mag-imbak ng mga listahan.

6
00:00:19,160 --> 00:00:21,200
Madaling magbilang ang mga elemento ng isang listahan

7
00:00:21,200 --> 00:00:23,390
naka-imbak sa isang array, at kung kailangan mo upang ma-access

8
00:00:23,390 --> 00:00:25,050
o baguhin ang ith elemento listahan

9
00:00:25,050 --> 00:00:27,570
para sa ilang arbitrary index ako,

10
00:00:27,570 --> 00:00:29,910
na maaaring gawin sa pare-pareho ang oras,

11
00:00:29,910 --> 00:00:31,660
ngunit array ay may disadvantages, masyadong.

12
00:00:31,660 --> 00:00:33,850
>> Kapag ipinapahayag namin ang mga ito, kami ay kinakailangan upang sabihin

13
00:00:33,850 --> 00:00:35,900
up front kung gaano kalaki ang mga ito,

14
00:00:35,900 --> 00:00:38,160
iyon ay, kung gaano karaming mga elemento ang maaari silang mag-imbak

15
00:00:38,160 --> 00:00:40,780
at kung gaano kalaki ang mga elementong ito, na kung saan ay tinutukoy sa pamamagitan ng kanilang mga uri.

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

17
00:00:45,450 --> 00:00:48,220
maaaring iimbak ng 10 mga item

18
00:00:48,220 --> 00:00:50,200
na ang laki ng isang int.

19
00:00:50,200 --> 00:00:52,590
>> Hindi namin maaaring baguhin ang laki ng isang array pagkatapos ng deklarasyon.

20
00:00:52,590 --> 00:00:55,290
Mayroon kaming upang gumawa ng isang bagong array kung gusto namin upang mag-imbak ng higit pang mga elemento.

21
00:00:55,290 --> 00:00:57,410
Ang dahilan ng limitasyong ito ang umiiral na ay na ang aming

22
00:00:57,410 --> 00:00:59,040
programa iniimbak ang buong array

23
00:00:59,040 --> 00:01:02,310
bilang isang magkadikit na tipak ng memorya.

24
00:01:02,310 --> 00:01:04,500
Sabihing ito ay ang buffer kung saan kami naka-imbak sa aming array.

25
00:01:04,500 --> 00:01:06,910
Maaaring may iba pang mga variable

26
00:01:06,910 --> 00:01:08,310
matatagpuan sa tabi mismo sa array

27
00:01:08,310 --> 00:01:10,060
sa memory, kaya hindi namin mai-

28
00:01:10,060 --> 00:01:12,060
array ang mas malaking.

29
00:01:12,060 --> 00:01:15,700
>> Minsan nais naming ikakalakal mabilis ang array data sa bilis ng access

30
00:01:15,700 --> 00:01:17,650
para sa isang maliit na higit pang kakayahang umangkop.

31
00:01:17,650 --> 00:01:20,380
Ipasok ang naka-link na listahan, ang isa pang pangunahing istraktura ng data

32
00:01:20,380 --> 00:01:22,360
hindi mo maaaring maging pamilyar sa.

33
00:01:22,360 --> 00:01:24,200
Sa isang mataas na antas,

34
00:01:24,200 --> 00:01:26,840
naka-link na listahan ay nag-iimbak ng mga data sa isang pagkakasunud-sunod ng mga node

35
00:01:26,840 --> 00:01:29,280
na konektado sa bawat isa sa mga link,

36
00:01:29,280 --> 00:01:31,760
samakatuwid 'naka-link na listahan.' ang pangalan

37
00:01:31,760 --> 00:01:33,840
Tulad ng makikita namin makita, ang pagkakaibang ito sa disenyo

38
00:01:33,840 --> 00:01:35,500
humantong sa iba't ibang mga kalamangan at disadvantages

39
00:01:35,500 --> 00:01:37,000
kaysa sa isang array.

40
00:01:37,000 --> 00:01:39,840
>> Narito ang ilang C code para sa isang napaka-simpleng naka-link na listahan ng mga integer.

41
00:01:39,840 --> 00:01:42,190
Maaari mong makita na namin kinakatawan ang bawat node

42
00:01:42,190 --> 00:01:45,520
sa listahan bilang isang struct na naglalaman ng 2 bagay,

43
00:01:45,520 --> 00:01:47,280
isang integer upang mag-imbak na tinatawag na 'Val'

44
00:01:47,280 --> 00:01:50,460
at isang link sa susunod na node sa listahan

45
00:01:50,460 --> 00:01:52,990
kung saan ay kumakatawan namin bilang isang pointer na tinatawag na 'susunod.'

46
00:01:54,120 --> 00:01:56,780
Sa ganitong paraan, maaari naming subaybayan ang buong listahan

47
00:01:56,780 --> 00:01:58,790
ng isang pointer sa node 1st,

48
00:01:58,790 --> 00:02:01,270
at pagkatapos ay maaari naming sundin ang mga susunod na mga pointer

49
00:02:01,270 --> 00:02:03,130
sa 2nd node,

50
00:02:03,130 --> 00:02:05,280
sa 3rd node,

51
00:02:05,280 --> 00:02:07,000
sa ika-4 na node,

52
00:02:07,000 --> 00:02:09,889
at iba pa, hanggang sa makuha namin sa dulo ng listahan.

53
00:02:10,520 --> 00:02:12,210
>> Na maaaring magawa upang makita ang 1 samantalahin ito ay may

54
00:02:12,210 --> 00:02:14,490
sa ibabaw ng static na istraktura ng array - na may naka-link na listahan,

55
00:02:14,490 --> 00:02:16,450
hindi namin kailangan ng isang malaking tipak ng memory sa kabuuan.

56
00:02:17,400 --> 00:02:20,530
Ang 1st node ng listahan ay maaaring manirahan sa lugar na ito sa memory,

57
00:02:20,530 --> 00:02:23,160
at sa 2nd na node ay maaaring ang lahat ng mga paraan sa paglipas dito.

58
00:02:23,160 --> 00:02:25,780
Maaari naming makakuha ng sa lahat ng mga node hindi mahalaga kung saan sa memory ang mga ito,

59
00:02:25,780 --> 00:02:28,890
dahil simula sa node 1st, susunod na pointer sa bawat node

60
00:02:28,890 --> 00:02:31,700
ay nagsasabi sa amin kung saan mismo upang pumunta sa susunod na.

61
00:02:31,700 --> 00:02:33,670
>> Bukod pa rito, hindi namin upang sabihin up front

62
00:02:33,670 --> 00:02:36,740
kung gaano kalaki ang isang naka-link na listahan ay ang paraan na gawin namin sa static array,

63
00:02:36,740 --> 00:02:39,060
dahil maaari naming patuloy na magdagdag ng mga node sa isang listahan

64
00:02:39,060 --> 00:02:42,600
hangga't may espasyo sa isang lugar sa memory para sa bagong mga node.

65
00:02:42,600 --> 00:02:45,370
Samakatuwid, ang mga naka-link na listahan ay madaling upang baguhin ang laki dynamic.

66
00:02:45,370 --> 00:02:47,950
Sabihin nating, sa ibang pagkakataon sa programa kailangan namin upang magdagdag ng higit pang mga node

67
00:02:47,950 --> 00:02:49,350
sa aming listahan.

68
00:02:49,350 --> 00:02:51,480
Upang magpasok ng isang bagong node sa aming listahan sa mabilisang,

69
00:02:51,480 --> 00:02:53,740
lahat kami ay may sa gawin ay magtalaga ng memory para sa node,

70
00:02:53,740 --> 00:02:55,630
magsabuwatan sa ang halaga ng data,

71
00:02:55,630 --> 00:02:59,070
at pagkatapos ay ilagay ito kung saan nais naming sa pamamagitan ng pagsasaayos ng mga naaangkop na payo.

72
00:02:59,070 --> 00:03:02,310
>> Halimbawa, kung gusto naming maglagay ng node sa pagitan

73
00:03:02,310 --> 00:03:04,020
ang ika-2 at ika-3 na node ng listahan,

74
00:03:04,020 --> 00:03:06,800
 hindi namin ay upang ilipat ang 2nd o 3rd node sa lahat.

75
00:03:06,800 --> 00:03:09,190
Sabihing namin ang pagpasok ng ito pulang node.

76
00:03:09,190 --> 00:03:12,890
Ang lahat na gusto naming gawin ay nakatakda sa susunod na pointer ang bagong node

77
00:03:12,890 --> 00:03:14,870
upang tumuro sa ika-3 na node

78
00:03:14,870 --> 00:03:18,580
at pagkatapos ay rewire ng susunod na pointer sa 2nd node

79
00:03:18,580 --> 00:03:20,980
ituro sa aming bagong node.

80
00:03:22,340 --> 00:03:24,370
Kaya, maaari naming baguhin ang laki ng aming mga listahan sa mabilisang

81
00:03:24,370 --> 00:03:26,090
simula ng aming computer ay hindi umaasa sa pag-i-index,

82
00:03:26,090 --> 00:03:28,990
kundi sa pagli-link gamit ang pointer upang mag-imbak ang mga ito.

83
00:03:29,120 --> 00:03:31,600
>> Gayunpaman, ang dehado ng naka-link na listahan

84
00:03:31,600 --> 00:03:33,370
ay na, hindi katulad ng static na array,

85
00:03:33,370 --> 00:03:36,690
ang computer ay hindi maaari lamang tumalon sa gitna ng listahan.

86
00:03:38,040 --> 00:03:40,780
Dahil ang computer ay may upang bisitahin ang bawat node sa naka-link na listahan

87
00:03:40,780 --> 00:03:42,330
upang makakuha ng sa susunod na,

88
00:03:42,330 --> 00:03:44,770
ito ay pagpunta sa magtagal upang mahanap ang isang partikular na node

89
00:03:44,770 --> 00:03:46,400
kaysa sa gagawin ito sa isang array.

90
00:03:46,400 --> 00:03:48,660
Upang pagbagtas ang buong listahan ay tumatagal ng oras proporsyonal

91
00:03:48,660 --> 00:03:50,580
sa haba ng listahan,

92
00:03:50,580 --> 00:03:54,630
o O (n) sa asymptotic pagtatanda.

93
00:03:54,630 --> 00:03:56,510
Sa average, na umaabot sa anumang node

94
00:03:56,510 --> 00:03:58,800
nangangailangan ng panahon proporsyonal sa n.

95
00:03:58,800 --> 00:04:00,700
>> Ngayon, sabihin aktwal na magsulat ng ilang mga code

96
00:04:00,700 --> 00:04:02,000
na gumagana sa naka-link na listahan.

97
00:04:02,000 --> 00:04:04,220
Ipagpalagay natin na nais namin ang isang naka-link na listahan ng mga integer.

98
00:04:04,220 --> 00:04:06,140
Maaari naming kumakatawan sa isang node muli sa aming listahan

99
00:04:06,140 --> 00:04:08,340
bilang isang struct may 2 mga patlang,

100
00:04:08,340 --> 00:04:10,750
ng isang integer value na tinatawag na 'Val'

101
00:04:10,750 --> 00:04:13,490
at susunod na pointer sa susunod na node ng listahan.

102
00:04:13,490 --> 00:04:15,660
Well, tila simpleng sapat.

103
00:04:15,660 --> 00:04:17,220
>> Ipagpalagay natin na nais namin upang magsulat ng isang function

104
00:04:17,220 --> 00:04:19,329
kung aling mga traverses ang listahan at print ang

105
00:04:19,329 --> 00:04:22,150
halaga na naka-imbak sa huling node ng listahan.

106
00:04:22,150 --> 00:04:24,850
Well, na ibig sabihin nito ay kailangan nating pagbagtas ang lahat ng mga node sa listahan

107
00:04:24,850 --> 00:04:27,310
upang mahanap ang huling, ngunit dahil hindi namin pagdaragdag ng

108
00:04:27,310 --> 00:04:29,250
o tinatanggal, hindi namin nais na baguhin

109
00:04:29,250 --> 00:04:32,210
ang panloob na istraktura ng susunod na pointer sa listahan.

110
00:04:32,210 --> 00:04:34,790
>> Kaya, makikita namin kailangan ang isang pointer para traversal

111
00:04:34,790 --> 00:04:36,940
na kami tatawag sa 'crawler.'

112
00:04:36,940 --> 00:04:38,870
Ito ay crawl sa pamamagitan ng ang lahat ng mga elemento ng listahan

113
00:04:38,870 --> 00:04:41,190
sa pamamagitan ng pagsunod sa mga kadena ng mga susunod na pointer.

114
00:04:41,190 --> 00:04:43,750
Lahat na naka-imbak namin ay isang pointer sa node 1st,

115
00:04:43,750 --> 00:04:45,730
o 'ulo' ng listahan.

116
00:04:45,730 --> 00:04:47,370
Head ng mga puntos sa 1st node.

117
00:04:47,370 --> 00:04:49,120
Ng uri ng pointer-sa-node.

118
00:04:49,120 --> 00:04:51,280
>> Upang makuha ang aktwal na 1st node sa listahan,

119
00:04:51,280 --> 00:04:53,250
mayroon kaming dereference pointer na ito,

120
00:04:53,250 --> 00:04:55,100
ngunit bago namin ito dereference, kailangan namin upang suriin

121
00:04:55,100 --> 00:04:57,180
kung ang pointer ay null unang.

122
00:04:57,180 --> 00:04:59,190
Kung ito ay null, listahan ay walang laman,

123
00:04:59,190 --> 00:05:01,320
at dapat naming i-print ang isang mensahe, dahil ang listahan ay walang laman,

124
00:05:01,320 --> 00:05:03,250
walang huling node.

125
00:05:03,250 --> 00:05:05,190
Ngunit, sabihin nating ay hindi walang laman ang listahan.

126
00:05:05,190 --> 00:05:08,340
Kung ito ay hindi, pagkatapos ay dapat namin crawl sa pamamagitan ng buong listahan

127
00:05:08,340 --> 00:05:10,440
hanggang sa makuha namin sa huling node ng listahan,

128
00:05:10,440 --> 00:05:13,030
at kung paano maaari naming sabihin kung kaming naghahanap sa huling node sa listahan?

129
00:05:13,670 --> 00:05:16,660
>> Well, kung ang susunod na pointer ng node ay null,

130
00:05:16,660 --> 00:05:18,320
alam namin na hindi namin sa dulo

131
00:05:18,320 --> 00:05:22,390
dahil ang huling susunod na pointer ay walang susunod na node sa listahan upang tumuro sa.

132
00:05:22,390 --> 00:05:26,590
Ito ay mahusay na kasanayan upang laging panatilihin ang susunod na pointer sa huling node nasimulan sa null

133
00:05:26,590 --> 00:05:30,800
Standardized ari-arian na inaalertuhan sa amin kapag kami naabot ang dulo ng listahan.

134
00:05:30,800 --> 00:05:33,510
>> Kaya, kung crawler → susunod ay null,

135
00:05:34,120 --> 00:05:38,270
tandaan na ang syntax ng arrow ay isang shortcut para sa dereferencing

136
00:05:38,270 --> 00:05:40,010
isang pointer sa isang struct, pagkatapos-access

137
00:05:40,010 --> 00:05:42,510
nito sa susunod na field katumbas sa mahirap:

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

139
00:05:49,820 --> 00:05:51,260
Kapag nalaman namin na ang huling node,

140
00:05:51,260 --> 00:05:53,830
gusto naming upang i-print ang crawler → Val,

141
00:05:53,830 --> 00:05:55,000
ang halaga sa kasalukuyang node

142
00:05:55,000 --> 00:05:57,130
kung saan alam namin ay ang huling.

143
00:05:57,130 --> 00:05:59,740
Kung hindi man, kung hindi kami pa sa huling node sa listahan,

144
00:05:59,740 --> 00:06:02,340
mayroon kaming upang lumipat sa susunod na node sa listahan

145
00:06:02,340 --> 00:06:04,750
at suriin kung iyon ang huling isa.

146
00:06:04,750 --> 00:06:07,010
Upang gawin ito, lamang namin-set ang aming crawler pointer

147
00:06:07,010 --> 00:06:09,840
upang ituro sa susunod na halaga ng ang kasalukuyang node,

148
00:06:09,840 --> 00:06:11,680
iyon ay, ang susunod na node sa listahan.

149
00:06:11,680 --> 00:06:13,030
Ito ay ginagawa sa pamamagitan ng pagtatakda

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

151
00:06:16,050 --> 00:06:18,960
Pagkatapos naming ulitin ang prosesong ito, na may isang loop halimbawa,

152
00:06:18,960 --> 00:06:20,960
hanggang sa nakita namin ang huling node.

153
00:06:20,960 --> 00:06:23,150
Kaya, halimbawa, kung crawler ay tumuturo sa ulo,

154
00:06:24,050 --> 00:06:27,710
kami ng crawler upang tumuro sa crawler → susunod,

155
00:06:27,710 --> 00:06:30,960
na ang parehong bilang ang susunod na field ng 1st node.

156
00:06:30,960 --> 00:06:33,620
Kaya, ngayon aming crawler ay tumuturo sa ika-2 node,

157
00:06:33,620 --> 00:06:35,480
at, muli, ulitin namin ito na may loop,

158
00:06:37,220 --> 00:06:40,610
hanggang sa natagpuan namin ang huling node, iyon ay,

159
00:06:40,610 --> 00:06:43,640
kung saan ang susunod na pointer sa node ay tumuturo sa null.

160
00:06:43,640 --> 00:06:45,070
At doon ay may namin ito,

161
00:06:45,070 --> 00:06:47,620
nalaman namin huling node sa listahan, at upang i-print ang halaga,

162
00:06:47,620 --> 00:06:50,800
namin lamang gamitin ang crawler → Val.

163
00:06:50,800 --> 00:06:53,130
>> Traversing ay hindi kaya masamang, ngunit kung ano ang tungkol sa pagpasok?

164
00:06:53,130 --> 00:06:56,290
Ay nagbibigay-daan nating gusto naming magpasok ng isang integer sa ika-4 na posisyon

165
00:06:56,290 --> 00:06:58,040
sa isang integer listahan.

166
00:06:58,040 --> 00:07:01,280
Ito ay sa pagitan ng kasalukuyang ika-3 at ika-4 na node.

167
00:07:01,280 --> 00:07:03,760
Muli, mayroon kami sa pagbagtas sa listahan lamang

168
00:07:03,760 --> 00:07:06,520
makuha ang 3rd elemento, namin ang pagpasok pagkatapos.

169
00:07:06,520 --> 00:07:09,300
Kaya, hindi namin muling lumikha ng isang crawler pointer sa pagbagtas sa listahan,

170
00:07:09,300 --> 00:07:11,400
suriin kung ang aming ulo pointer ay null,

171
00:07:11,400 --> 00:07:14,810
at kung ito ay hindi, ituro ang aming crawler pointer sa node ng ulo.

172
00:07:16,880 --> 00:07:18,060
Kaya, hindi namin sa 1st elemento.

173
00:07:18,060 --> 00:07:21,020
Mayroon kaming upang pumunta pasulong 2 higit pang mga elemento bago namin isingit,

174
00:07:21,020 --> 00:07:23,390
upang maaari naming gamitin para sa 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
at sa bawat pag-ulit ng loop,

177
00:07:28,590 --> 00:07:31,540
advance ang aming crawler pointer sa forward ng 1 node

178
00:07:31,540 --> 00:07:34,570
sa pamamagitan ng pagsuri kung ang susunod na field ang kasalukuyang node ay null,

179
00:07:34,570 --> 00:07:37,550
at kung ito ay hindi, ilipat ang aming crawler pointer sa susunod na node

180
00:07:37,550 --> 00:07:41,810
sa pamamagitan ng pagtatakda ng katumbas ng susunod na pointer ang kasalukuyang node.

181
00:07:41,810 --> 00:07:45,210
Kaya, dahil ang aming para sa loop sabi ni upang gawin iyon

182
00:07:45,210 --> 00:07:47,550
dalawang beses,

183
00:07:49,610 --> 00:07:51,190
Naabot namin ang 3rd node,

184
00:07:51,190 --> 00:07:53,110
at sabay-sabay ang aming crawler pointer ay naabot node pagkatapos

185
00:07:53,110 --> 00:07:55,270
kung saan gusto naming upang ipasok ang aming bagong integer,

186
00:07:55,270 --> 00:07:57,050
kung paano namin aktwal ang pagpasok?

187
00:07:57,050 --> 00:07:59,440
>> Well, ang aming bagong integer ay ipinasok sa listahan

188
00:07:59,440 --> 00:08:01,250
bilang bahagi ng sarili nitong node struct,

189
00:08:01,250 --> 00:08:03,140
dahil ito ay talagang isang pagkakasunud-sunod ng mga node.

190
00:08:03,140 --> 00:08:05,690
Kaya, sabihin gumawa ng isang bagong pointer sa node

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

192
00:08:08,910 --> 00:08:11,800
at itakda ito upang tumuro sa memorya na namin ngayon na maglaan

193
00:08:11,800 --> 00:08:14,270
sa magbunton para sa node mismo,

194
00:08:14,270 --> 00:08:16,000
at kung gaano karaming memory ang kailangan namin upang magtalaga?

195
00:08:16,000 --> 00:08:18,250
Well, ang laki ng isang node,

196
00:08:20,450 --> 00:08:23,410
at gusto naming i-set ang Val field sa integer na gusto namin upang ipasok.

197
00:08:23,410 --> 00:08:25,590
Sabihin nating, 6.

198
00:08:25,590 --> 00:08:27,710
Ngayon, ang node ay naglalaman ng aming mga halaga ng integer.

199
00:08:27,710 --> 00:08:30,650
Ring mahusay na kasanayan upang simulan ang susunod na field ang bagong node

200
00:08:30,650 --> 00:08:33,690
upang tumuro sa null,

201
00:08:33,690 --> 00:08:35,080
ngunit ngayon ano?

202
00:08:35,080 --> 00:08:37,179
>> Mayroon kaming upang baguhin ang panloob na istraktura ng listahan

203
00:08:37,179 --> 00:08:40,409
at ang susunod na mga pointer na nilalaman sa umiiral sa listahan

204
00:08:40,409 --> 00:08:42,950
Ika-3 at ika-4 na node.

205
00:08:42,950 --> 00:08:46,560
Dahil ang mga susunod na pointer matukoy ang pagkakasunud-sunod ng listahan,

206
00:08:46,560 --> 00:08:48,650
at dahil kami ay pagpasok ng aming bagong node

207
00:08:48,650 --> 00:08:50,510
pakanan papunta sa kalagitnaan ng listahan,

208
00:08:50,510 --> 00:08:52,010
ito ay isang bit nakakalito.

209
00:08:52,010 --> 00:08:54,250
Ito ay dahil, tandaan, ang aming mga computer na

210
00:08:54,250 --> 00:08:56,250
lamang alam ang lokasyon ng mga node sa listahan

211
00:08:56,250 --> 00:09:00,400
dahil sa sa susunod na mga pointer na naka-imbak sa nakaraang node.

212
00:09:00,400 --> 00:09:03,940
Kaya, kung namin nawala ang pagsubaybay ng anumang mga lokasyong ito,

213
00:09:03,940 --> 00:09:06,860
sabihin sa pamamagitan ng pagbabago sa isa sa mga susunod na mga payo sa aming listahan,

214
00:09:06,860 --> 00:09:09,880
halimbawa, sinasabi namin ay nagbago

215
00:09:09,880 --> 00:09:12,920
susunod na field sa 3rd node

216
00:09:12,920 --> 00:09:15,610
upang tumuro sa ilang node sa paglipas dito.

217
00:09:15,610 --> 00:09:17,920
Gusto naming ka sana, dahil hindi namin gagawin

218
00:09:17,920 --> 00:09:20,940
anumang mga ideya kung saan upang mahanap ang natitirang bahagi ng listahan,

219
00:09:20,940 --> 00:09:23,070
at na malinaw naman ganap na hindi maayos.

220
00:09:23,070 --> 00:09:25,080
Kaya, mayroon kaming talagang maingat tungkol sa pagkakasunod-sunod

221
00:09:25,080 --> 00:09:28,360
kung saan namin manipulahin ang aming mga susunod na pointer sa panahon ng pagpapasok ng.

222
00:09:28,360 --> 00:09:30,540
>> Kaya, upang gawing simple ito, sabihin nating

223
00:09:30,540 --> 00:09:32,220
aming unang 4 node

224
00:09:32,220 --> 00:09:36,200
ay tinatawag na A, B, C, at D, gamit ang mga arrow na kumakatawan sa hanay ng mga payo

225
00:09:36,200 --> 00:09:38,070
na ikonekta ang mga node.

226
00:09:38,070 --> 00:09:40,050
Kaya, kailangan namin upang ipasok ang aming bagong node

227
00:09:40,050 --> 00:09:42,070
sa pagitan ng node C at D.

228
00:09:42,070 --> 00:09:45,060
Ito ay kritikal na upang gawin ang mga ito sa tamang pagkakasunod-sunod, at kukunin ko na ipakita sa iyo kung bakit.

229
00:09:45,060 --> 00:09:47,500
>> Tingnan natin sa maling paraan upang gawin ito unang.

230
00:09:47,500 --> 00:09:49,490
Uy, alam namin ang bagong node ay darating karapatan pagkatapos C,

231
00:09:49,490 --> 00:09:51,910
kaya sabihin itakda ang susunod na pointer C

232
00:09:51,910 --> 00:09:54,700
upang ituro sa new_node.

233
00:09:56,530 --> 00:09:59,180
Karapatan lahat, mukhang okay, namin lamang upang tapusin ngayon sa pamamagitan ng

234
00:09:59,180 --> 00:10:01,580
susunod na pointer sa bagong node punto sa D,

235
00:10:01,580 --> 00:10:03,250
ngunit paghihintay, kung paano namin gawin iyon?

236
00:10:03,250 --> 00:10:05,170
Ang tanging bagay na maaaring sabihin sa amin kung saan ang D ay,

237
00:10:05,170 --> 00:10:07,630
ay sa susunod na pointer sa nakaraang naka-imbak sa C,

238
00:10:07,630 --> 00:10:09,870
ngunit hindi namin lamang rewrote na pointer

239
00:10:09,870 --> 00:10:11,170
upang ituro sa bagong node,

240
00:10:11,170 --> 00:10:14,230
kaya hindi na namin anumang bakas kung saan D sa memorya,

241
00:10:14,230 --> 00:10:17,020
at hindi na namin nawala ang natitirang bahagi ng listahan.

242
00:10:17,020 --> 00:10:19,000
Hindi magandang sa lahat.

243
00:10:19,000 --> 00:10:21,090
>> Kaya, kung paano ang gagawin namin ang karapatan na ito?

244
00:10:22,360 --> 00:10:25,090
Una, ituro ang susunod na pointer ang bagong node sa D.

245
00:10:26,170 --> 00:10:28,990
Ngayon, sa parehong bagong node at C susunod na pointer

246
00:10:28,990 --> 00:10:30,660
ay na tumuturo sa parehong node, D,

247
00:10:30,660 --> 00:10:32,290
ngunit ang fine.

248
00:10:32,290 --> 00:10:35,680
Ngayon ay maaari naming ituro ang susunod C pointer sa bagong node.

249
00:10:37,450 --> 00:10:39,670
Kaya, ginawa namin ito nang hindi nawawalan ng anumang data.

250
00:10:39,670 --> 00:10:42,280
Sa code, C ay ang kasalukuyang node

251
00:10:42,280 --> 00:10:45,540
na traversal pointer crawler ay tumuturo sa,

252
00:10:45,540 --> 00:10:50,400
at D ay kinakatawan ng node nakaumang sa pamamagitan ng susunod na field ang kasalukuyang node,

253
00:10:50,400 --> 00:10:52,600
o crawler → susunod.

254
00:10:52,600 --> 00:10:55,460
Kaya, muna namin magtakda ng susunod na pointer ang bagong node

255
00:10:55,460 --> 00:10:57,370
upang ituro sa crawler → susunod,

256
00:10:57,370 --> 00:11:00,880
sa parehong paraan na sinabi namin ang susunod na pointer new_node dapat

257
00:11:00,880 --> 00:11:02,780
tumuro sa D sa paglalarawan.

258
00:11:02,780 --> 00:11:04,540
Pagkatapos, maaari naming itakda ang susunod na pointer ang kasalukuyang node

259
00:11:04,540 --> 00:11:06,330
sa aming bagong node,

260
00:11:06,330 --> 00:11:10,980
tulad ng nagkaroon kami maghintay upang ituro ang C upang new_node sa drawing.

261
00:11:10,980 --> 00:11:12,250
Ngayon ang lahat sa pagkakasunod-sunod, at hindi namin mawala

262
00:11:12,250 --> 00:11:14,490
subaybayan ng anumang data, at hindi namin magagawang lamang

263
00:11:14,490 --> 00:11:16,200
dumikit ang aming bagong node sa gitna ng listahan

264
00:11:16,200 --> 00:11:19,330
walang muling pagtatayo ang buong bagay o kahit na paglilipat anumang mga elemento

265
00:11:19,330 --> 00:11:22,490
paraan ay namin ay nagkaroon na may isang nakapirming haba ng array.

266
00:11:22,490 --> 00:11:26,020
>> Kaya, ang mga naka-link na listahan ay isang pangunahing, ngunit mahalaga, dynamic na istraktura ng data

267
00:11:26,020 --> 00:11:29,080
na may parehong mga kalamangan at disadvantages

268
00:11:29,080 --> 00:11:31,260
kumpara sa mga array at iba pang mga data kaayusan,

269
00:11:31,260 --> 00:11:33,350
at bilang ay madalas na ang kaso sa computer science,

270
00:11:33,350 --> 00:11:35,640
Mahalagang malaman kapag upang gamitin sa bawat tool,

271
00:11:35,640 --> 00:11:37,960
sa gayon ay maaari mong piliin ang mga tamang tool para sa tamang trabaho.

272
00:11:37,960 --> 00:11:40,060
>> Para sa higit pang mga kasanayan, subukan ang pagsusulat ng mga function sa

273
00:11:40,060 --> 00:11:42,080
tanggalin ang node mula sa naka-link na listahan -

274
00:11:42,080 --> 00:11:44,050
tandaan na maging maingat tungkol sa pagkakasunud-sunod kung saan mong isaayos muli

275
00:11:44,050 --> 00:11:47,430
ang iyong mga susunod na pointer upang matiyak na hindi ka mawalan ng isang tipak ng iyong listahan -

276
00:11:47,430 --> 00:11:50,200
o isang function upang mabilang ang mga node sa isang naka-link na listahan,

277
00:11:50,200 --> 00:11:53,280
o isang masaya, upang baliktarin ang pagkakasunod-sunod ng lahat ng node sa isang naka-link na listahan.

278
00:11:53,280 --> 00:11:56,090
>> Ang pangalan ko ay Jackson Steinkamp, ​​ito ay CS50.