Susun atur vs Senarai Terpaut
Susun atur adalah struktur data yang paling biasa digunakan untuk menyimpan koleksi elemen. Sebilangan besar bahasa pengaturcaraan menyediakan kaedah untuk menyatakan larik dan elemen akses dalam larik dengan mudah. Senarai terpaut, lebih tepatnya senarai berangkai tunggal, juga merupakan struktur data yang dapat digunakan untuk menyimpan koleksi elemen. Ia terdiri daripada urutan nod dan setiap simpul mempunyai rujukan ke simpul seterusnya dalam urutan.
Yang ditunjukkan dalam gambar 1, adalah sekeping kod yang biasanya digunakan untuk menyatakan dan memberikan nilai pada array. Gambar 2 menggambarkan bagaimana rupa array dalam memori.
Kod di atas mentakrifkan array yang dapat menyimpan 5 bilangan bulat dan mereka diakses menggunakan indeks 0 hingga 4. Satu sifat penting bagi array ialah keseluruhan array diperuntukkan sebagai satu blok memori dan setiap elemen mendapat ruang tersendiri dalam array. Setelah tatasusunan ditentukan, ukurannya tetap. Oleh itu, jika anda tidak pasti mengenai ukuran array pada masa penyusunan, anda harus menentukan susunan yang cukup besar untuk berada di sisi selamat. Tetapi, selalunya kita akan menggunakan lebih sedikit elemen daripada yang telah kita peruntukkan. Oleh itu, sejumlah besar memori sebenarnya terbuang. Sebaliknya jika "array yang cukup besar" sebenarnya tidak cukup besar, program akan terhenti.
Senarai terpaut mengalokasikan memori untuk unsur-unsurnya secara berasingan dalam blok memori tersendiri dan keseluruhan struktur diperoleh dengan menghubungkan elemen-elemen ini sebagai pautan dalam rantai. Setiap elemen dalam senarai terpaut mempunyai dua bidang seperti yang ditunjukkan dalam Gambar 3. Medan data menyimpan data sebenar yang tersimpan dan medan seterusnya menyimpan rujukan ke elemen seterusnya dalam rantai. Unsur pertama senarai terpaut disimpan sebagai ketua senarai terpaut.
Gambar 3: Unsur Senarai Terpaut
Rajah 4 menggambarkan senarai yang dipautkan dengan tiga elemen. Setiap elemen menyimpan datanya dan semua elemen kecuali yang terakhir menyimpan rujukan ke elemen seterusnya. Elemen terakhir mempunyai nilai nol di medan seterusnya. Mana-mana elemen dalam senarai boleh diakses dengan bermula dari kepala dan mengikuti penunjuk seterusnya sehingga anda memenuhi elemen yang diperlukan.
Walaupun susunan dan senarai yang dipautkan serupa dalam arti bahawa kedua-duanya digunakan untuk menyimpan koleksi elemen, mereka mengalami perbezaan kerana strategi yang mereka gunakan untuk mengalokasikan memori ke elemennya. Susun atur mengalihkan memori ke semua elemennya sebagai satu blok dan ukuran array harus ditentukan pada waktu berjalan. Ini akan menjadikan tatasusunan tidak cekap dalam situasi di mana anda tidak mengetahui ukuran array pada waktu kompilasi. Oleh kerana senarai terpaut mengalokasikan memori untuk unsur-unsurnya secara berasingan, akan lebih berkesan dalam keadaan di mana anda tidak mengetahui ukuran senarai pada waktu penyusunan. Deklarasi dan mengakses elemen dalam senarai yang dipautkan tidak akan lurus berbanding dengan cara anda secara langsung mengakses elemen dalam array menggunakan indeksnya.
