Perbedaan antara array dan daftar tertaut

Array vs Daftar Tertaut

Array adalah struktur data yang paling umum digunakan untuk menyimpan pengumpulan elemen. Sebagian besar bahasa pemrograman menyediakan metode untuk dengan mudah mendeklarasikan array dan elemen akses dalam array. Daftar tertaut, daftar yang lebih tepat secara tunggal, juga merupakan struktur data yang dapat digunakan untuk menyimpan koleksi elemen. Ini terdiri dari urutan node dan setiap node memiliki referensi ke node berikutnya dalam urutan.

Ditunjukkan pada Gambar 1, adalah sepotong kode yang biasanya digunakan untuk mendeklarasikan dan menetapkan nilai ke array. Gambar 2 menggambarkan bagaimana suatu array akan terlihat dalam memori.

Kode di atas mendefinisikan array yang dapat menyimpan 5 bilangan bulat dan diakses menggunakan indeks 0 hingga 4. Salah satu sifat penting dari suatu array adalah bahwa seluruh array dialokasikan sebagai satu blok memori dan setiap elemen mendapatkan ruang sendiri dalam array. Setelah array didefinisikan, ukurannya diperbaiki. Jadi jika Anda tidak yakin tentang ukuran array pada waktu kompilasi, Anda harus menentukan array yang cukup besar untuk berada di sisi yang aman. Tapi, sebagian besar waktu kita benar -benar akan menggunakan lebih sedikit 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 elemen -elemennya secara terpisah di blok memori sendiri dan keseluruhan struktur diperoleh dengan menghubungkan elemen -elemen ini sebagai tautan dalam 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 memegang referensi ke elemen berikutnya dalam rantai. Elemen pertama dari daftar tertaut disimpan sebagai kepala daftar yang ditautkan.

Gambar 3: Elemen dari daftar yang ditautkan

Gambar 4 menggambarkan daftar tertaut dengan tiga elemen. Setiap elemen menyimpan data 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 pointer berikutnya sampai Anda memenuhi elemen yang diperlukan.

Meskipun array dan daftar yang ditautkan serupa dalam arti bahwa keduanya digunakan untuk menyimpan koleksi elemen, mereka menimbulkan perbedaan karena strategi yang mereka gunakan untuk mengalokasikan memori ke elemennya. Array mengalokasikan memori untuk semua elemennya sebagai satu blok dan ukuran array harus ditentukan saat runtime. Ini akan membuat array tidak efisien dalam situasi di mana Anda tidak tahu ukuran array pada waktu kompilasi. Karena daftar yang ditautkan mengalokasikan memori ke elemen -elemennya secara terpisah, itu akan jauh lebih efisien dalam situasi di mana Anda tidak tahu ukuran daftar pada waktu kompilasi. Deklarasi dan mengakses elemen dalam daftar yang ditautkan tidak akan langsung dibandingkan dengan bagaimana Anda secara langsung mengakses elemen dalam array menggunakan indeksnya.