Array vs Daftar Tertaut
Array adalah struktur data yang paling umum digunakan untuk menyimpan kumpulan elemen. Kebanyakan bahasa pemrograman menyediakan metode untuk mendeklarasikan array dengan mudah dan elemen akses 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 tersebut.
Ditunjukkan pada gambar 1, adalah potongan kode yang biasanya digunakan untuk mendeklarasikan dan menetapkan nilai ke array. Gambar 2 menggambarkan bagaimana sebuah array akan terlihat dalam memori.
Kode di atas mendefinisikan sebuah array yang dapat menyimpan 5 bilangan bulat dan mereka diakses menggunakan indeks 0 sampai 4. Salah satu properti penting dari sebuah array adalah bahwa seluruh array dialokasikan sebagai satu blok memori dan setiap elemen mendapatkan ruangnya sendiri dalam array tersebut. Setelah array ditentukan, ukurannya ditetapkan. Jadi, jika Anda tidak yakin tentang ukuran larik pada waktu kompilasi, Anda harus menentukan larik yang cukup besar agar berada di sisi yang aman. Namun, sebagian besar waktu kita sebenarnya akan menggunakan lebih sedikit jumlah elemen daripada yang telah kita alokasikan. Jadi, sejumlah besar memori sebenarnya terbuang. Di sisi lain, jika "array yang cukup besar" sebenarnya tidak cukup besar, program akan macet.
Daftar tertaut mengalokasikan memori ke elemennya secara terpisah di blok memorinya sendiri dan struktur keseluruhan diperoleh dengan menghubungkan 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 dari daftar tertaut.
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. Setiap elemen 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 elemennya secara terpisah, ini akan menjadi lebih efisien dalam situasi di mana Anda tidak mengetahui ukuran daftar pada waktu kompilasi. Deklarasi dan mengakses elemen dalam daftar tertaut tidak akan langsung dibandingkan dengan cara Anda mengakses elemen secara langsung dalam array menggunakan indeksnya.
