Array vs Daftar Tertaut
Array adalah struktur data yang paling umum digunakan untuk menyimpan kumpulan elemen. Sebagian besar bahasa pemrograman menyediakan metode untuk mendeklarasikan array dengan mudah dan mengakses elemen dalam array. Daftar tertaut, lebih tepatnya daftar tertaut tunggal, juga merupakan struktur data yang dapat digunakan untuk menyimpan kumpulan elemen. Itu terdiri dari urutan node dan setiap node memiliki referensi ke node berikutnya dalam urutan.
Ditunjukkan pada gambar 1, adalah bagian dari kode yang biasanya digunakan untuk mendeklarasikan dan menetapkan nilai ke array. Gambar 2 menggambarkan bagaimana array akan terlihat seperti di memori.
Kode di atas mendefinisikan array yang dapat menyimpan 5 bilangan bulat dan diakses menggunakan indeks 0 hingga 4. Salah satu properti penting dari array adalah seluruh array dialokasikan sebagai satu blok memori dan setiap elemen mendapatkan ruangnya sendiri dalam larik. Setelah array didefinisikan, ukurannya tetap. Jadi, jika Anda tidak yakin tentang ukuran array pada waktu kompilasi, Anda harus mendefinisikan array yang cukup besar agar aman. Namun, sebagian besar waktu kita sebenarnya akan menggunakan lebih sedikit elemen daripada yang telah kita alokasikan. Jadi sejumlah besar memori sebenarnya terbuang sia-sia. Di sisi lain jika "array cukup besar" sebenarnya tidak cukup besar, program akan macet.
Daftar tertaut mengalokasikan memori ke elemen-elemennya secara terpisah di blok memorinya sendiri dan struktur keseluruhan diperoleh dengan menghubungkan elemen-elemen ini sebagai tautan dalam sebuah rantai. Setiap elemen dalam daftar tertaut memiliki dua bidang seperti yang ditunjukkan pada Gambar 3. Bidang data menyimpan data aktual yang disimpan dan bidang berikutnya menyimpan referensi ke elemen berikutnya dalam rantai. Elemen pertama dari daftar tertaut disimpan sebagai kepala daftar tertaut.
| data | berikutnya |
Gambar 3: Elemen Daftar Tertaut
Gambar 4 menggambarkan daftar tertaut dengan tiga elemen. Setiap elemen menyimpan datanya dan semua elemen kecuali yang terakhir menyimpan referensi ke elemen berikutnya. Elemen terakhir memegang nilai nol di bidang berikutnya. Elemen apa pun dalam daftar dapat diakses dengan memulai dari kepala dan mengikuti penunjuk berikutnya hingga Anda memenuhi elemen yang diperlukan.
Meskipun array dan daftar tertaut serupa dalam arti keduanya digunakan untuk menyimpan kumpulan elemen, keduanya menimbulkan perbedaan karena strategi yang mereka gunakan untuk mengalokasikan memori ke elemennya. Array mengalokasikan memori ke semua elemennya sebagai satu blok dan ukuran array harus ditentukan saat runtime. Ini akan membuat array tidak efisien dalam situasi di mana Anda tidak mengetahui ukuran array pada waktu kompilasi. Karena daftar tertaut mengalokasikan memori ke elemen-elemennya secara terpisah, itu akan jauh lebih efisien dalam situasi di mana Anda tidak mengetahui ukuran daftar pada waktu kompilasi. Deklarasi dan mengakses elemen dalam daftar tertaut tidak akan mudah dibandingkan dengan bagaimana Anda mengakses elemen dalam array secara langsung menggunakan indeksnya.
