[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.