[Powered by Google Translate] Dalam pemrograman, kita sering perlu untuk mewakili daftar nilai,
seperti nama-nama siswa dalam bagian
atau mereka nilai pada kuis terbaru.
>> Dalam bahasa C, menyatakan array dapat digunakan
untuk menyimpan daftar.
Sangat mudah untuk menghitung unsur-unsur dari daftar
disimpan dalam array, dan jika Anda perlu untuk mengakses
atau memodifikasi elemen daftar engan
untuk beberapa indeks sewenang-wenang I,
yang dapat dilakukan dalam waktu yang konstan,
tapi array memiliki kelemahan juga.
>> Ketika kita menyatakan mereka, kita diminta untuk mengatakan
di depan seberapa besar mereka,
yaitu, berapa banyak elemen yang mereka dapat menyimpan
dan seberapa besar elemen ini, yang ditentukan oleh jenis mereka.
Misalnya, int arr (10)
dapat menyimpan 10 item
yang merupakan ukuran int.
>> Kita tidak bisa mengubah ukuran array setelah deklarasi.
Kami harus membuat array baru jika kita ingin menyimpan elemen lebih.
Alasan keterbatasan ini ada adalah bahwa kita
Program menyimpan seluruh array
sebagai sepotong bersebelahan memori.
Katakanlah ini adalah buffer di mana kita disimpan dalam array kita.
Mungkin ada variabel lain
terletak tepat di sebelah array
dalam memori, sehingga kita tidak bisa
hanya membuat array besar.
>> Kadang-kadang kita ingin perdagangan kecepatan cepat array akses data
untuk fleksibilitas yang lebih sedikit.
Masukkan linked list, struktur lain data dasar
Anda mungkin tidak akrab dengan.
Pada tingkat tinggi,
sebuah linked list menyimpan data dalam urutan node
yang terhubung satu sama lain dengan link,
maka 'linked list.' nama
Seperti yang akan kita lihat, perbedaan dalam desain
mengarah ke berbagai keuntungan dan kerugian
dari array.
>> Berikut adalah beberapa kode C untuk linked list sangat sederhana dari bilangan bulat.
Anda dapat melihat bahwa kita telah mewakili setiap node
dalam daftar sebagai struct yang berisi 2 hal,
integer untuk menyimpan disebut 'val'
dan link ke node berikutnya dalam daftar
yang kami mewakili sebagai pointer yang disebut 'berikutnya. "
Dengan cara ini, kita dapat melacak seluruh daftar
hanya dengan pointer tunggal untuk node 1,
dan kemudian kita bisa mengikuti petunjuk berikutnya
ke node 2,
ke node 3,
ke simpul 4,
dan seterusnya, sampai kita sampai ke akhir daftar.
>> Anda mungkin dapat melihat keuntungan 1 ini memiliki
atas struktur array statis - dengan linked list,
kita tidak perlu sebagian besar dari memori sama sekali.
Simpul 1 dari daftar bisa tinggal di tempat ini di memori,
dan node 2 bisa semua jalan di sini.
Kita bisa mendapatkan semua node di mana pun dalam memori mereka,
karena dimulai dari node 1, pointer berikutnya masing-masing node
memberitahu kita persis di mana harus pergi berikutnya.
>> Selain itu, kita tidak harus mengatakan di depan
seberapa besar sebuah linked list akan menjadi cara kita lakukan dengan array statis,
karena kita dapat terus menambahkan node untuk daftar
asalkan ada ruang di suatu tempat di memori untuk node baru.
Oleh karena itu, daftar terhubung mudah untuk mengubah ukuran dinamis.
Katakanlah, nanti dalam program kita perlu menambahkan node lebih
dalam daftar kami.
Untuk menyisipkan simpul baru ke dalam daftar kami on the fly,
yang harus kita lakukan adalah mengalokasikan memori untuk simpul tersebut,
plop dalam nilai data,
dan kemudian tempat itu di mana kita inginkan dengan menyesuaikan pointer yang sesuai.
>> Sebagai contoh, jika kita ingin menempatkan sebuah node di antara
ke-2 dan ke-3 node dari daftar,
kita tidak harus memindahkan node 2 atau 3 sama sekali.
Katakanlah kita memasukkan ini simpul merah.
Semua kita harus lakukan adalah mengatur pointer berikutnya node baru
untuk menunjuk ke simpul 3
dan kemudian rewire pointer berikutnya node 2nd
untuk menunjuk ke simpul baru kami.
Jadi, kita dapat mengubah ukuran daftar kami on the fly
karena komputer kita tidak bergantung pada pengindeksan,
tetapi lebih pada menghubungkan menggunakan pointer untuk menyimpan mereka.
>> Namun, kelemahan dari daftar terkait
adalah bahwa, tidak seperti array statis,
komputer tidak bisa hanya melompat ke tengah daftar.
Karena komputer harus mengunjungi setiap node dalam linked list
untuk sampai ke yang berikutnya,
itu akan memakan waktu lebih lama untuk menemukan node tertentu
daripada itu akan dalam array.
Untuk melintasi seluruh daftar membutuhkan waktu proporsional
dengan panjang daftar,
atau O (n) dalam notasi asimtotik.
Rata-rata, mencapai setiap node
juga membutuhkan waktu sebanding dengan n.
>> Sekarang, mari kita benar-benar menulis beberapa kode
yang bekerja dengan daftar link.
Katakanlah kita ingin linked list dari bilangan bulat.
Kita bisa mewakili node dalam daftar kami lagi
sebagai struct dengan 2 bidang,
nilai integer disebut 'val'
dan pointer sebelah node berikutnya dari daftar.
Nah, tampaknya cukup sederhana.
>> Katakanlah kita ingin menulis fungsi
yang melintasi daftar dan mencetak
nilai yang disimpan dalam simpul terakhir dari list.
Nah, itu berarti kita harus melintasi semua node dalam daftar
untuk menemukan yang terakhir, tapi karena kita tidak menambahkan
atau menghapus apa-apa, kita tidak ingin mengubah
struktur internal dari pointer berikutnya dalam daftar.
>> Jadi, kita akan membutuhkan pointer khusus untuk traversal
yang kita sebut 'crawler.'
Ini akan merangkak melalui semua elemen dari daftar
dengan mengikuti rantai pointer berikutnya.
Semua telah kita simpan adalah pointer ke node 1,
atau 'kepala' dari daftar.
Kepala poin ke node 1.
Ini jenis pointer-ke-node.
>> Untuk mendapatkan node 1 aktual dalam daftar,
kita harus dereference pointer ini,
tapi sebelum kita dapat dereference itu, kita perlu memeriksa
jika pointer adalah null pertama.
Jika itu nol, daftar kosong,
dan kita harus mencetak pesan itu, karena daftar kosong,
tidak ada node terakhir.
Tapi, katakanlah daftar tidak kosong.
Jika tidak, maka kita harus merangkak melalui seluruh daftar
sampai kita sampai ke simpul terakhir dari daftar,
dan bagaimana kita bisa mengetahui apakah kita sedang melihat node terakhir dalam daftar?
>> Nah, jika pointer berikutnya simpul adalah nol,
kita tahu bahwa kita berada di akhir
sejak pointer berikutnya terakhir akan tidak memiliki simpul berikutnya dalam daftar untuk menunjuk ke.
Ini praktik yang baik untuk selalu menjaga pointer berikutnya node lalu diinisialisasi ke nol
untuk memiliki properti standar yang mengingatkan kita ketika kita telah mencapai akhir daftar.
>> Jadi, jika crawler → berikutnya adalah nol,
ingatlah bahwa sintaks panah adalah jalan pintas untuk dereferencing
pointer ke struct, kemudian mengakses
yang kolom berikutnya setara dengan canggung:
(* Crawler). Berikutnya.
Setelah kami menemukan node terakhir,
kita ingin mencetak crawler → val,
nilai dalam node saat ini
yang kita tahu adalah yang terakhir.
Jika tidak, jika kita belum pada simpul terakhir dalam daftar,
kita harus beralih ke node berikutnya dalam daftar
dan memeriksa apakah itu yang terakhir.
Untuk melakukan hal ini, kita hanya mengatur pointer perayap kami
untuk menunjuk ke nilai berikutnya node saat ini,
yaitu, node berikutnya dalam daftar.
Hal ini dilakukan dengan menetapkan
crawler = crawler → berikutnya.
Lalu kita ulangi proses ini, dengan loop misalnya,
sampai kita menemukan node terakhir.
Jadi, misalnya, jika crawler menunjuk ke kepala,
kami menetapkan crawler untuk menunjuk ke crawler → berikutnya,
yang sama dengan kolom berikutnya dari node 1.
Jadi, sekarang crawler kami menunjuk ke node 2,
dan, sekali lagi, kita ulangi ini dengan lingkaran,
sampai kita telah menemukan node terakhir, yaitu,
di mana pointer berikutnya node yang menunjuk ke null.
Dan di sana kita memilikinya,
kami telah menemukan node terakhir dalam daftar, dan mencetak nilainya,
kita hanya menggunakan crawler → val.
>> Melintasi tidak begitu buruk, tapi bagaimana memasukkan?
Katakanlah kita ingin memasukkan integer ke posisi ke-4
dalam daftar bilangan bulat.
Itulah antara node 3 dan 4 saat ini.
Sekali lagi, kita harus melintasi daftar hanya untuk
sampai ke elemen ke-3, yang kita menyisipkan setelah.
Jadi, kita menciptakan sebuah pointer crawler lagi untuk melintasi daftar,
memeriksa apakah pointer kepala kita adalah null,
dan jika tidak, arahkan pointer crawler kami di node kepala.
Jadi, kita berada di elemen 1.
Kita harus maju 2 elemen lagi sebelum kita dapat menyisipkan,
sehingga kita bisa menggunakan untuk loop
int i = 1; i <3, i + +
dan di setiap iterasi dari loop,
memajukan pointer perayap kami maju dengan 1 simpul
dengan memeriksa apakah kolom berikutnya node saat ini adalah nol,
dan jika tidak, pindahkan pointer crawler kami ke node berikutnya
dengan menetapkan sama dengan pointer berikutnya node saat ini.
Jadi, karena loop untuk kami mengatakan untuk melakukan itu
dua kali,
kami telah mencapai simpul 3,
dan sekali pointer perayap kami telah mencapai simpul setelah
yang kita ingin memasukkan integer baru kami,
bagaimana kita benar-benar melakukan yang memasukkan?
>> Nah, integer baru kami harus dimasukkan ke dalam daftar
sebagai bagian dari struct node sendiri,
karena ini adalah benar-benar urutan node.
Jadi, mari kita membuat pointer baru ke node
disebut 'new_node,'
dan mengaturnya untuk menunjuk ke memori yang sekarang kita mengalokasikan
pada tumpukan untuk node itu sendiri,
dan memori berapa banyak kita perlu mengalokasikan?
Nah, ukuran node,
dan kami ingin mengatur medan val untuk integer yang ingin kita masukkan.
Katakanlah, 6.
Sekarang, node berisi nilai integer kami.
Ini juga kebiasaan yang baik untuk menginisialisasi kolom berikutnya node baru
untuk menunjuk ke nol,
tapi sekarang apa?
>> Kami harus mengubah struktur internal dari daftar
dan pointer berikutnya yang terkandung dalam yang ada dalam daftar ini
3 dan 4 node.
Karena pointer selanjutnya menentukan urutan daftar,
dan karena kita sedang memasukkan simpul baru kami
tepat ke tengah-tengah daftar,
itu dapat menjadi sedikit rumit.
Hal ini karena, ingat, komputer kita
hanya tahu lokasi node dalam daftar
karena pointer berikutnya disimpan dalam node sebelumnya.
Jadi, jika kita pernah kehilangan jejak salah satu lokasi,
mengatakan dengan mengubah salah satu pointer berikutnya dalam daftar kami,
Misalnya, katakanlah kita berubah
node 3 di sebelah lapangan
untuk menunjuk ke beberapa node di sini.
Kami akan beruntung, karena kita tidak akan
punya ide di mana untuk menemukan sisa daftar,
dan itu jelas benar-benar buruk.
Jadi, kita harus benar-benar hati-hati tentang urutan
di mana kita memanipulasi pointer berikutnya kami selama penyisipan.
>> Jadi, untuk menyederhanakan hal ini, mari kita mengatakan bahwa
kami pertama 4 node
disebut A, B, C, dan D, dengan panah yang mewakili rantai pointer
yang menghubungkan node.
Jadi, kita harus memasukkan simpul baru kami
di antara node C dan D.
Sangatlah penting untuk melakukannya dalam urutan yang benar, dan aku akan menunjukkan mengapa.
>> Mari kita lihat cara yang salah untuk melakukannya terlebih dahulu.
Hei, kita tahu simpul baru harus datang tepat setelah C,
jadi mari kita mengatur pointer berikutnya C
untuk menunjuk ke new_node.
Baiklah, tampaknya baik-baik saja, kita hanya harus menyelesaikan sekarang oleh
membuat titik pointer berikutnya node baru ke D,
tapi tunggu, bagaimana kita bisa melakukan itu?
Satu-satunya hal yang bisa memberitahu kita di mana D adalah,
adalah pointer berikutnya sebelumnya disimpan di C,
tapi kami hanya menulis ulang pointer yang
untuk menunjuk ke simpul baru,
jadi kita tidak lagi memiliki petunjuk di mana D adalah dalam memori,
dan kami telah kehilangan seluruh daftar.
Tidak baik sama sekali.
>> Jadi, bagaimana kita melakukan ini dengan benar?
Pertama, arahkan pointer berikutnya node baru di D.
Sekarang, baik baru node dan C selanjutnya pointer
yang menunjuk ke node yang sama, D,
tapi itu baik-baik saja.
Sekarang kita bisa mengarahkan pointer berikutnya C di simpul baru.
Jadi, kami telah melakukan ini tanpa kehilangan data apapun.
Dalam kode, C adalah node saat
bahwa traversal pointer crawler menunjuk ke,
dan D diwakili oleh node ditunjukkan oleh kolom berikutnya node saat ini,
atau crawler → berikutnya.
Jadi, pertama-tama kita mengatur pointer berikutnya node baru
untuk menunjuk ke crawler → berikutnya,
dengan cara yang sama kita mengatakan pointer berikutnya new_node yang harus
menunjuk ke D dalam ilustrasi.
Kemudian, kita dapat mengatur pointer berikutnya node saat ini
ke node baru kami,
seperti kami harus menunggu untuk titik C untuk new_node dalam gambar.
Sekarang semuanya dalam rangka, dan kami tidak kehilangan
melacak dari setiap data, dan kami mampu hanya
tetap node baru kami di tengah-tengah daftar
tanpa membangun kembali seluruh hal atau bahkan menggeser setiap elemen
cara kita akan harus dengan array tetap-panjang.
>> Jadi, linked list adalah, dasar, namun penting dinamis struktur data
yang memiliki keuntungan dan kerugian
dibandingkan dengan array dan struktur data lainnya,
dan seperti yang sering terjadi dalam ilmu komputer,
itu penting untuk mengetahui kapan harus menggunakan setiap alat,
sehingga Anda dapat memilih alat yang tepat untuk pekerjaan yang tepat.
>> Untuk latihan lagi, cobalah menulis fungsi untuk
menghapus node dari linked list -
ingat untuk berhati-hati tentang urutan di mana Anda mengatur ulang
Anda selanjutnya pointer untuk memastikan bahwa Anda tidak kehilangan sepotong daftar Anda -
atau fungsi untuk menghitung node dalam linked list,
atau menyenangkan satu, untuk membalik urutan dari semua node dalam linked list.
>> Nama saya Jackson Steinkamp, ​​ini adalah CS50.