1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Dalam pemrograman, kita sering perlu untuk mewakili daftar nilai,

2
00:00:10,050 --> 00:00:12,840
seperti nama-nama siswa dalam bagian

3
00:00:12,840 --> 00:00:15,100
atau mereka nilai pada kuis terbaru.

4
00:00:15,100 --> 00:00:17,430
>> Dalam bahasa C, menyatakan array dapat digunakan

5
00:00:17,430 --> 00:00:19,160
untuk menyimpan daftar.

6
00:00:19,160 --> 00:00:21,200
Sangat mudah untuk menghitung unsur-unsur dari daftar

7
00:00:21,200 --> 00:00:23,390
disimpan dalam array, dan jika Anda perlu untuk mengakses

8
00:00:23,390 --> 00:00:25,050
atau memodifikasi elemen daftar engan

9
00:00:25,050 --> 00:00:27,570
untuk beberapa indeks sewenang-wenang I,

10
00:00:27,570 --> 00:00:29,910
yang dapat dilakukan dalam waktu yang konstan,

11
00:00:29,910 --> 00:00:31,660
tapi array memiliki kelemahan juga.

12
00:00:31,660 --> 00:00:33,850
>> Ketika kita menyatakan mereka, kita diminta untuk mengatakan

13
00:00:33,850 --> 00:00:35,900
di depan seberapa besar mereka,

14
00:00:35,900 --> 00:00:38,160
yaitu, berapa banyak elemen yang mereka dapat menyimpan

15
00:00:38,160 --> 00:00:40,780
dan seberapa besar elemen ini, yang ditentukan oleh jenis mereka.

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

17
00:00:45,450 --> 00:00:48,220
dapat menyimpan 10 item

18
00:00:48,220 --> 00:00:50,200
yang merupakan ukuran int.

19
00:00:50,200 --> 00:00:52,590
>> Kita tidak bisa mengubah ukuran array setelah deklarasi.

20
00:00:52,590 --> 00:00:55,290
Kami harus membuat array baru jika kita ingin menyimpan elemen lebih.

21
00:00:55,290 --> 00:00:57,410
Alasan keterbatasan ini ada adalah bahwa kita

22
00:00:57,410 --> 00:00:59,040
Program menyimpan seluruh array

23
00:00:59,040 --> 00:01:02,310
sebagai sepotong bersebelahan memori.

24
00:01:02,310 --> 00:01:04,500
Katakanlah ini adalah buffer di mana kita disimpan dalam array kita.

25
00:01:04,500 --> 00:01:06,910
Mungkin ada variabel lain

26
00:01:06,910 --> 00:01:08,310
terletak tepat di sebelah array

27
00:01:08,310 --> 00:01:10,060
dalam memori, sehingga kita tidak bisa

28
00:01:10,060 --> 00:01:12,060
hanya membuat array besar.

29
00:01:12,060 --> 00:01:15,700
>> Kadang-kadang kita ingin perdagangan kecepatan cepat array akses data

30
00:01:15,700 --> 00:01:17,650
untuk fleksibilitas yang lebih sedikit.

31
00:01:17,650 --> 00:01:20,380
Masukkan linked list, struktur lain data dasar

32
00:01:20,380 --> 00:01:22,360
Anda mungkin tidak akrab dengan.

33
00:01:22,360 --> 00:01:24,200
Pada tingkat tinggi,

34
00:01:24,200 --> 00:01:26,840
sebuah linked list menyimpan data dalam urutan node

35
00:01:26,840 --> 00:01:29,280
yang terhubung satu sama lain dengan link,

36
00:01:29,280 --> 00:01:31,760
maka 'linked list.' nama

37
00:01:31,760 --> 00:01:33,840
Seperti yang akan kita lihat, perbedaan dalam desain

38
00:01:33,840 --> 00:01:35,500
mengarah ke berbagai keuntungan dan kerugian

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

40
00:01:37,000 --> 00:01:39,840
>> Berikut adalah beberapa kode C untuk linked list sangat sederhana dari bilangan bulat.

41
00:01:39,840 --> 00:01:42,190
Anda dapat melihat bahwa kita telah mewakili setiap node

42
00:01:42,190 --> 00:01:45,520
dalam daftar sebagai struct yang berisi 2 hal,

43
00:01:45,520 --> 00:01:47,280
integer untuk menyimpan disebut 'val'

44
00:01:47,280 --> 00:01:50,460
dan link ke node berikutnya dalam daftar

45
00:01:50,460 --> 00:01:52,990
yang kami mewakili sebagai pointer yang disebut 'berikutnya. "

46
00:01:54,120 --> 00:01:56,780
Dengan cara ini, kita dapat melacak seluruh daftar

47
00:01:56,780 --> 00:01:58,790
hanya dengan pointer tunggal untuk node 1,

48
00:01:58,790 --> 00:02:01,270
dan kemudian kita bisa mengikuti petunjuk berikutnya

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

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

51
00:02:05,280 --> 00:02:07,000
ke simpul 4,

52
00:02:07,000 --> 00:02:09,889
dan seterusnya, sampai kita sampai ke akhir daftar.

53
00:02:10,520 --> 00:02:12,210
>> Anda mungkin dapat melihat keuntungan 1 ini memiliki

54
00:02:12,210 --> 00:02:14,490
atas struktur array statis - dengan linked list,

55
00:02:14,490 --> 00:02:16,450
kita tidak perlu sebagian besar dari memori sama sekali.

56
00:02:17,400 --> 00:02:20,530
Simpul 1 dari daftar bisa tinggal di tempat ini di memori,

57
00:02:20,530 --> 00:02:23,160
dan node 2 bisa semua jalan di sini.

58
00:02:23,160 --> 00:02:25,780
Kita bisa mendapatkan semua node di mana pun dalam memori mereka,

59
00:02:25,780 --> 00:02:28,890
karena dimulai dari node 1, pointer berikutnya masing-masing node

60
00:02:28,890 --> 00:02:31,700
memberitahu kita persis di mana harus pergi berikutnya.

61
00:02:31,700 --> 00:02:33,670
>> Selain itu, kita tidak harus mengatakan di depan

62
00:02:33,670 --> 00:02:36,740
seberapa besar sebuah linked list akan menjadi cara kita lakukan dengan array statis,

63
00:02:36,740 --> 00:02:39,060
karena kita dapat terus menambahkan node untuk daftar

64
00:02:39,060 --> 00:02:42,600
asalkan ada ruang di suatu tempat di memori untuk node baru.

65
00:02:42,600 --> 00:02:45,370
Oleh karena itu, daftar terhubung mudah untuk mengubah ukuran dinamis.

66
00:02:45,370 --> 00:02:47,950
Katakanlah, nanti dalam program kita perlu menambahkan node lebih

67
00:02:47,950 --> 00:02:49,350
dalam daftar kami.

68
00:02:49,350 --> 00:02:51,480
Untuk menyisipkan simpul baru ke dalam daftar kami on the fly,

69
00:02:51,480 --> 00:02:53,740
yang harus kita lakukan adalah mengalokasikan memori untuk simpul tersebut,

70
00:02:53,740 --> 00:02:55,630
plop dalam nilai data,

71
00:02:55,630 --> 00:02:59,070
dan kemudian tempat itu di mana kita inginkan dengan menyesuaikan pointer yang sesuai.

72
00:02:59,070 --> 00:03:02,310
>> Sebagai contoh, jika kita ingin menempatkan sebuah node di antara

73
00:03:02,310 --> 00:03:04,020
ke-2 dan ke-3 node dari daftar,

74
00:03:04,020 --> 00:03:06,800
 kita tidak harus memindahkan node 2 atau 3 sama sekali.

75
00:03:06,800 --> 00:03:09,190
Katakanlah kita memasukkan ini simpul merah.

76
00:03:09,190 --> 00:03:12,890
Semua kita harus lakukan adalah mengatur pointer berikutnya node baru

77
00:03:12,890 --> 00:03:14,870
untuk menunjuk ke simpul 3

78
00:03:14,870 --> 00:03:18,580
dan kemudian rewire pointer berikutnya node 2nd

79
00:03:18,580 --> 00:03:20,980
untuk menunjuk ke simpul baru kami.

80
00:03:22,340 --> 00:03:24,370
Jadi, kita dapat mengubah ukuran daftar kami on the fly

81
00:03:24,370 --> 00:03:26,090
karena komputer kita tidak bergantung pada pengindeksan,

82
00:03:26,090 --> 00:03:28,990
tetapi lebih pada menghubungkan menggunakan pointer untuk menyimpan mereka.

83
00:03:29,120 --> 00:03:31,600
>> Namun, kelemahan dari daftar terkait

84
00:03:31,600 --> 00:03:33,370
adalah bahwa, tidak seperti array statis,

85
00:03:33,370 --> 00:03:36,690
komputer tidak bisa hanya melompat ke tengah daftar.

86
00:03:38,040 --> 00:03:40,780
Karena komputer harus mengunjungi setiap node dalam linked list

87
00:03:40,780 --> 00:03:42,330
untuk sampai ke yang berikutnya,

88
00:03:42,330 --> 00:03:44,770
itu akan memakan waktu lebih lama untuk menemukan node tertentu

89
00:03:44,770 --> 00:03:46,400
daripada itu akan dalam array.

90
00:03:46,400 --> 00:03:48,660
Untuk melintasi seluruh daftar membutuhkan waktu proporsional

91
00:03:48,660 --> 00:03:50,580
dengan panjang daftar,

92
00:03:50,580 --> 00:03:54,630
atau O (n) dalam notasi asimtotik.

93
00:03:54,630 --> 00:03:56,510
Rata-rata, mencapai setiap node

94
00:03:56,510 --> 00:03:58,800
juga membutuhkan waktu sebanding dengan n.

95
00:03:58,800 --> 00:04:00,700
>> Sekarang, mari kita benar-benar menulis beberapa kode

96
00:04:00,700 --> 00:04:02,000
yang bekerja dengan daftar link.

97
00:04:02,000 --> 00:04:04,220
Katakanlah kita ingin linked list dari bilangan bulat.

98
00:04:04,220 --> 00:04:06,140
Kita bisa mewakili node dalam daftar kami lagi

99
00:04:06,140 --> 00:04:08,340
sebagai struct dengan 2 bidang,

100
00:04:08,340 --> 00:04:10,750
nilai integer disebut 'val'

101
00:04:10,750 --> 00:04:13,490
dan pointer sebelah node berikutnya dari daftar.

102
00:04:13,490 --> 00:04:15,660
Nah, tampaknya cukup sederhana.

103
00:04:15,660 --> 00:04:17,220
>> Katakanlah kita ingin menulis fungsi

104
00:04:17,220 --> 00:04:19,329
yang melintasi daftar dan mencetak

105
00:04:19,329 --> 00:04:22,150
nilai yang disimpan dalam simpul terakhir dari list.

106
00:04:22,150 --> 00:04:24,850
Nah, itu berarti kita harus melintasi semua node dalam daftar

107
00:04:24,850 --> 00:04:27,310
untuk menemukan yang terakhir, tapi karena kita tidak menambahkan

108
00:04:27,310 --> 00:04:29,250
atau menghapus apa-apa, kita tidak ingin mengubah

109
00:04:29,250 --> 00:04:32,210
struktur internal dari pointer berikutnya dalam daftar.

110
00:04:32,210 --> 00:04:34,790
>> Jadi, kita akan membutuhkan pointer khusus untuk traversal

111
00:04:34,790 --> 00:04:36,940
yang kita sebut 'crawler.'

112
00:04:36,940 --> 00:04:38,870
Ini akan merangkak melalui semua elemen dari daftar

113
00:04:38,870 --> 00:04:41,190
dengan mengikuti rantai pointer berikutnya.

114
00:04:41,190 --> 00:04:43,750
Semua telah kita simpan adalah pointer ke node 1,

115
00:04:43,750 --> 00:04:45,730
atau 'kepala' dari daftar.

116
00:04:45,730 --> 00:04:47,370
Kepala poin ke node 1.

117
00:04:47,370 --> 00:04:49,120
Ini jenis pointer-ke-node.

118
00:04:49,120 --> 00:04:51,280
>> Untuk mendapatkan node 1 aktual dalam daftar,

119
00:04:51,280 --> 00:04:53,250
kita harus dereference pointer ini,

120
00:04:53,250 --> 00:04:55,100
tapi sebelum kita dapat dereference itu, kita perlu memeriksa

121
00:04:55,100 --> 00:04:57,180
jika pointer adalah null pertama.

122
00:04:57,180 --> 00:04:59,190
Jika itu nol, daftar kosong,

123
00:04:59,190 --> 00:05:01,320
dan kita harus mencetak pesan itu, karena daftar kosong,

124
00:05:01,320 --> 00:05:03,250
tidak ada node terakhir.

125
00:05:03,250 --> 00:05:05,190
Tapi, katakanlah daftar tidak kosong.

126
00:05:05,190 --> 00:05:08,340
Jika tidak, maka kita harus merangkak melalui seluruh daftar

127
00:05:08,340 --> 00:05:10,440
sampai kita sampai ke simpul terakhir dari daftar,

128
00:05:10,440 --> 00:05:13,030
dan bagaimana kita bisa mengetahui apakah kita sedang melihat node terakhir dalam daftar?

129
00:05:13,670 --> 00:05:16,660
>> Nah, jika pointer berikutnya simpul adalah nol,

130
00:05:16,660 --> 00:05:18,320
kita tahu bahwa kita berada di akhir

131
00:05:18,320 --> 00:05:22,390
sejak pointer berikutnya terakhir akan tidak memiliki simpul berikutnya dalam daftar untuk menunjuk ke.

132
00:05:22,390 --> 00:05:26,590
Ini praktik yang baik untuk selalu menjaga pointer berikutnya node lalu diinisialisasi ke nol

133
00:05:26,590 --> 00:05:30,800
untuk memiliki properti standar yang mengingatkan kita ketika kita telah mencapai akhir daftar.

134
00:05:30,800 --> 00:05:33,510
>> Jadi, jika crawler → berikutnya adalah nol,

135
00:05:34,120 --> 00:05:38,270
ingatlah bahwa sintaks panah adalah jalan pintas untuk dereferencing

136
00:05:38,270 --> 00:05:40,010
pointer ke struct, kemudian mengakses

137
00:05:40,010 --> 00:05:42,510
yang kolom berikutnya setara dengan canggung:

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

139
00:05:49,820 --> 00:05:51,260
Setelah kami menemukan node terakhir,

140
00:05:51,260 --> 00:05:53,830
kita ingin mencetak crawler → val,

141
00:05:53,830 --> 00:05:55,000
nilai dalam node saat ini

142
00:05:55,000 --> 00:05:57,130
yang kita tahu adalah yang terakhir.

143
00:05:57,130 --> 00:05:59,740
Jika tidak, jika kita belum pada simpul terakhir dalam daftar,

144
00:05:59,740 --> 00:06:02,340
kita harus beralih ke node berikutnya dalam daftar

145
00:06:02,340 --> 00:06:04,750
dan memeriksa apakah itu yang terakhir.

146
00:06:04,750 --> 00:06:07,010
Untuk melakukan hal ini, kita hanya mengatur pointer perayap kami

147
00:06:07,010 --> 00:06:09,840
untuk menunjuk ke nilai berikutnya node saat ini,

148
00:06:09,840 --> 00:06:11,680
yaitu, node berikutnya dalam daftar.

149
00:06:11,680 --> 00:06:13,030
Hal ini dilakukan dengan menetapkan

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

151
00:06:16,050 --> 00:06:18,960
Lalu kita ulangi proses ini, dengan loop misalnya,

152
00:06:18,960 --> 00:06:20,960
sampai kita menemukan node terakhir.

153
00:06:20,960 --> 00:06:23,150
Jadi, misalnya, jika crawler menunjuk ke kepala,

154
00:06:24,050 --> 00:06:27,710
kami menetapkan crawler untuk menunjuk ke crawler → berikutnya,

155
00:06:27,710 --> 00:06:30,960
yang sama dengan kolom berikutnya dari node 1.

156
00:06:30,960 --> 00:06:33,620
Jadi, sekarang crawler kami menunjuk ke node 2,

157
00:06:33,620 --> 00:06:35,480
dan, sekali lagi, kita ulangi ini dengan lingkaran,

158
00:06:37,220 --> 00:06:40,610
sampai kita telah menemukan node terakhir, yaitu,

159
00:06:40,610 --> 00:06:43,640
di mana pointer berikutnya node yang menunjuk ke null.

160
00:06:43,640 --> 00:06:45,070
Dan di sana kita memilikinya,

161
00:06:45,070 --> 00:06:47,620
kami telah menemukan node terakhir dalam daftar, dan mencetak nilainya,

162
00:06:47,620 --> 00:06:50,800
kita hanya menggunakan crawler → val.

163
00:06:50,800 --> 00:06:53,130
>> Melintasi tidak begitu buruk, tapi bagaimana memasukkan?

164
00:06:53,130 --> 00:06:56,290
Katakanlah kita ingin memasukkan integer ke posisi ke-4

165
00:06:56,290 --> 00:06:58,040
dalam daftar bilangan bulat.

166
00:06:58,040 --> 00:07:01,280
Itulah antara node 3 dan 4 saat ini.

167
00:07:01,280 --> 00:07:03,760
Sekali lagi, kita harus melintasi daftar hanya untuk

168
00:07:03,760 --> 00:07:06,520
sampai ke elemen ke-3, yang kita menyisipkan setelah.

169
00:07:06,520 --> 00:07:09,300
Jadi, kita menciptakan sebuah pointer crawler lagi untuk melintasi daftar,

170
00:07:09,300 --> 00:07:11,400
memeriksa apakah pointer kepala kita adalah null,

171
00:07:11,400 --> 00:07:14,810
dan jika tidak, arahkan pointer crawler kami di node kepala.

172
00:07:16,880 --> 00:07:18,060
Jadi, kita berada di elemen 1.

173
00:07:18,060 --> 00:07:21,020
Kita harus maju 2 elemen lagi sebelum kita dapat menyisipkan,

174
00:07:21,020 --> 00:07:23,390
sehingga kita bisa menggunakan untuk 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
dan di setiap iterasi dari loop,

177
00:07:28,590 --> 00:07:31,540
memajukan pointer perayap kami maju dengan 1 simpul

178
00:07:31,540 --> 00:07:34,570
dengan memeriksa apakah kolom berikutnya node saat ini adalah nol,

179
00:07:34,570 --> 00:07:37,550
dan jika tidak, pindahkan pointer crawler kami ke node berikutnya

180
00:07:37,550 --> 00:07:41,810
dengan menetapkan sama dengan pointer berikutnya node saat ini.

181
00:07:41,810 --> 00:07:45,210
Jadi, karena loop untuk kami mengatakan untuk melakukan itu

182
00:07:45,210 --> 00:07:47,550
dua kali,

183
00:07:49,610 --> 00:07:51,190
kami telah mencapai simpul 3,

184
00:07:51,190 --> 00:07:53,110
dan sekali pointer perayap kami telah mencapai simpul setelah

185
00:07:53,110 --> 00:07:55,270
yang kita ingin memasukkan integer baru kami,

186
00:07:55,270 --> 00:07:57,050
bagaimana kita benar-benar melakukan yang memasukkan?

187
00:07:57,050 --> 00:07:59,440
>> Nah, integer baru kami harus dimasukkan ke dalam daftar

188
00:07:59,440 --> 00:08:01,250
sebagai bagian dari struct node sendiri,

189
00:08:01,250 --> 00:08:03,140
karena ini adalah benar-benar urutan node.

190
00:08:03,140 --> 00:08:05,690
Jadi, mari kita membuat pointer baru ke node

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

192
00:08:08,910 --> 00:08:11,800
dan mengaturnya untuk menunjuk ke memori yang sekarang kita mengalokasikan

193
00:08:11,800 --> 00:08:14,270
pada tumpukan untuk node itu sendiri,

194
00:08:14,270 --> 00:08:16,000
dan memori berapa banyak kita perlu mengalokasikan?

195
00:08:16,000 --> 00:08:18,250
Nah, ukuran node,

196
00:08:20,450 --> 00:08:23,410
dan kami ingin mengatur medan val untuk integer yang ingin kita masukkan.

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

198
00:08:25,590 --> 00:08:27,710
Sekarang, node berisi nilai integer kami.

199
00:08:27,710 --> 00:08:30,650
Ini juga kebiasaan yang baik untuk menginisialisasi kolom berikutnya node baru

200
00:08:30,650 --> 00:08:33,690
untuk menunjuk ke nol,

201
00:08:33,690 --> 00:08:35,080
tapi sekarang apa?

202
00:08:35,080 --> 00:08:37,179
>> Kami harus mengubah struktur internal dari daftar

203
00:08:37,179 --> 00:08:40,409
dan pointer berikutnya yang terkandung dalam yang ada dalam daftar ini

204
00:08:40,409 --> 00:08:42,950
3 dan 4 node.

205
00:08:42,950 --> 00:08:46,560
Karena pointer selanjutnya menentukan urutan daftar,

206
00:08:46,560 --> 00:08:48,650
dan karena kita sedang memasukkan simpul baru kami

207
00:08:48,650 --> 00:08:50,510
tepat ke tengah-tengah daftar,

208
00:08:50,510 --> 00:08:52,010
itu dapat menjadi sedikit rumit.

209
00:08:52,010 --> 00:08:54,250
Hal ini karena, ingat, komputer kita

210
00:08:54,250 --> 00:08:56,250
hanya tahu lokasi node dalam daftar

211
00:08:56,250 --> 00:09:00,400
karena pointer berikutnya disimpan dalam node sebelumnya.

212
00:09:00,400 --> 00:09:03,940
Jadi, jika kita pernah kehilangan jejak salah satu lokasi,

213
00:09:03,940 --> 00:09:06,860
mengatakan dengan mengubah salah satu pointer berikutnya dalam daftar kami,

214
00:09:06,860 --> 00:09:09,880
Misalnya, katakanlah kita berubah

215
00:09:09,880 --> 00:09:12,920
node 3 di sebelah lapangan

216
00:09:12,920 --> 00:09:15,610
untuk menunjuk ke beberapa node di sini.

217
00:09:15,610 --> 00:09:17,920
Kami akan beruntung, karena kita tidak akan

218
00:09:17,920 --> 00:09:20,940
punya ide di mana untuk menemukan sisa daftar,

219
00:09:20,940 --> 00:09:23,070
dan itu jelas benar-benar buruk.

220
00:09:23,070 --> 00:09:25,080
Jadi, kita harus benar-benar hati-hati tentang urutan

221
00:09:25,080 --> 00:09:28,360
di mana kita memanipulasi pointer berikutnya kami selama penyisipan.

222
00:09:28,360 --> 00:09:30,540
>> Jadi, untuk menyederhanakan hal ini, mari kita mengatakan bahwa

223
00:09:30,540 --> 00:09:32,220
kami pertama 4 node

224
00:09:32,220 --> 00:09:36,200
disebut A, B, C, dan D, dengan panah yang mewakili rantai pointer

225
00:09:36,200 --> 00:09:38,070
yang menghubungkan node.

226
00:09:38,070 --> 00:09:40,050
Jadi, kita harus memasukkan simpul baru kami

227
00:09:40,050 --> 00:09:42,070
di antara node C dan D.

228
00:09:42,070 --> 00:09:45,060
Sangatlah penting untuk melakukannya dalam urutan yang benar, dan aku akan menunjukkan mengapa.

229
00:09:45,060 --> 00:09:47,500
>> Mari kita lihat cara yang salah untuk melakukannya terlebih dahulu.

230
00:09:47,500 --> 00:09:49,490
Hei, kita tahu simpul baru harus datang tepat setelah C,

231
00:09:49,490 --> 00:09:51,910
jadi mari kita mengatur pointer berikutnya C

232
00:09:51,910 --> 00:09:54,700
untuk menunjuk ke new_node.

233
00:09:56,530 --> 00:09:59,180
Baiklah, tampaknya baik-baik saja, kita hanya harus menyelesaikan sekarang oleh

234
00:09:59,180 --> 00:10:01,580
membuat titik pointer berikutnya node baru ke D,

235
00:10:01,580 --> 00:10:03,250
tapi tunggu, bagaimana kita bisa melakukan itu?

236
00:10:03,250 --> 00:10:05,170
Satu-satunya hal yang bisa memberitahu kita di mana D adalah,

237
00:10:05,170 --> 00:10:07,630
adalah pointer berikutnya sebelumnya disimpan di C,

238
00:10:07,630 --> 00:10:09,870
tapi kami hanya menulis ulang pointer yang

239
00:10:09,870 --> 00:10:11,170
untuk menunjuk ke simpul baru,

240
00:10:11,170 --> 00:10:14,230
jadi kita tidak lagi memiliki petunjuk di mana D adalah dalam memori,

241
00:10:14,230 --> 00:10:17,020
dan kami telah kehilangan seluruh daftar.

242
00:10:17,020 --> 00:10:19,000
Tidak baik sama sekali.

243
00:10:19,000 --> 00:10:21,090
>> Jadi, bagaimana kita melakukan ini dengan benar?

244
00:10:22,360 --> 00:10:25,090
Pertama, arahkan pointer berikutnya node baru di D.

245
00:10:26,170 --> 00:10:28,990
Sekarang, baik baru node dan C selanjutnya pointer

246
00:10:28,990 --> 00:10:30,660
yang menunjuk ke node yang sama, D,

247
00:10:30,660 --> 00:10:32,290
tapi itu baik-baik saja.

248
00:10:32,290 --> 00:10:35,680
Sekarang kita bisa mengarahkan pointer berikutnya C di simpul baru.

249
00:10:37,450 --> 00:10:39,670
Jadi, kami telah melakukan ini tanpa kehilangan data apapun.

250
00:10:39,670 --> 00:10:42,280
Dalam kode, C adalah node saat

251
00:10:42,280 --> 00:10:45,540
bahwa traversal pointer crawler menunjuk ke,

252
00:10:45,540 --> 00:10:50,400
dan D diwakili oleh node ditunjukkan oleh kolom berikutnya node saat ini,

253
00:10:50,400 --> 00:10:52,600
atau crawler → berikutnya.

254
00:10:52,600 --> 00:10:55,460
Jadi, pertama-tama kita mengatur pointer berikutnya node baru

255
00:10:55,460 --> 00:10:57,370
untuk menunjuk ke crawler → berikutnya,

256
00:10:57,370 --> 00:11:00,880
dengan cara yang sama kita mengatakan pointer berikutnya new_node yang harus

257
00:11:00,880 --> 00:11:02,780
menunjuk ke D dalam ilustrasi.

258
00:11:02,780 --> 00:11:04,540
Kemudian, kita dapat mengatur pointer berikutnya node saat ini

259
00:11:04,540 --> 00:11:06,330
ke node baru kami,

260
00:11:06,330 --> 00:11:10,980
seperti kami harus menunggu untuk titik C untuk new_node dalam gambar.

261
00:11:10,980 --> 00:11:12,250
Sekarang semuanya dalam rangka, dan kami tidak kehilangan

262
00:11:12,250 --> 00:11:14,490
melacak dari setiap data, dan kami mampu hanya

263
00:11:14,490 --> 00:11:16,200
tetap node baru kami di tengah-tengah daftar

264
00:11:16,200 --> 00:11:19,330
tanpa membangun kembali seluruh hal atau bahkan menggeser setiap elemen

265
00:11:19,330 --> 00:11:22,490
cara kita akan harus dengan array tetap-panjang.

266
00:11:22,490 --> 00:11:26,020
>> Jadi, linked list adalah, dasar, namun penting dinamis struktur data

267
00:11:26,020 --> 00:11:29,080
yang memiliki keuntungan dan kerugian

268
00:11:29,080 --> 00:11:31,260
dibandingkan dengan array dan struktur data lainnya,

269
00:11:31,260 --> 00:11:33,350
dan seperti yang sering terjadi dalam ilmu komputer,

270
00:11:33,350 --> 00:11:35,640
itu penting untuk mengetahui kapan harus menggunakan setiap alat,

271
00:11:35,640 --> 00:11:37,960
sehingga Anda dapat memilih alat yang tepat untuk pekerjaan yang tepat.

272
00:11:37,960 --> 00:11:40,060
>> Untuk latihan lagi, cobalah menulis fungsi untuk

273
00:11:40,060 --> 00:11:42,080
menghapus node dari linked list -

274
00:11:42,080 --> 00:11:44,050
ingat untuk berhati-hati tentang urutan di mana Anda mengatur ulang

275
00:11:44,050 --> 00:11:47,430
Anda selanjutnya pointer untuk memastikan bahwa Anda tidak kehilangan sepotong daftar Anda -

276
00:11:47,430 --> 00:11:50,200
atau fungsi untuk menghitung node dalam linked list,

277
00:11:50,200 --> 00:11:53,280
atau menyenangkan satu, untuk membalik urutan dari semua node dalam linked list.

278
00:11:53,280 --> 00:11:56,090
>> Nama saya Jackson Steinkamp, ​​ini adalah CS50.