Susun atur lwn Senarai Terpaut
Array ialah struktur data yang paling biasa digunakan untuk menyimpan koleksi elemen. Kebanyakan bahasa pengaturcaraan menyediakan kaedah untuk mengisytiharkan tatasusunan dan mengakses elemen dalam tatasusunan dengan mudah. Senarai terpaut, lebih tepat lagi senarai pautan tunggal, juga merupakan struktur data yang boleh digunakan untuk menyimpan koleksi elemen. Ia terdiri daripada jujukan nod dan setiap nod mempunyai rujukan kepada nod seterusnya dalam jujukan.
Ditunjukkan dalam rajah 1, ialah sekeping kod yang biasanya digunakan untuk mengisytiharkan dan memberikan nilai kepada tatasusunan. Rajah 2 menggambarkan rupa tatasusunan dalam ingatan.
Kod di atas mentakrifkan tatasusunan yang boleh menyimpan 5 integer dan ia diakses menggunakan indeks 0 hingga 4. Satu sifat penting tatasusunan ialah keseluruhan tatasusunan diperuntukkan sebagai satu blok memori dan setiap elemen mendapat ruangnya sendiri dalam tatasusunan. Sebaik sahaja tatasusunan ditakrifkan, saiznya ditetapkan. Jadi jika anda tidak pasti tentang saiz tatasusunan pada masa penyusunan, anda perlu menentukan tatasusunan yang cukup besar untuk berada di bahagian yang selamat. Tetapi, kebanyakan masa kita sebenarnya akan menggunakan bilangan elemen yang kurang daripada yang telah kita peruntukkan. Jadi sejumlah besar ingatan sebenarnya terbuang. Sebaliknya jika "tatasusunan yang cukup besar" sebenarnya tidak cukup besar, program akan ranap.
Senarai terpaut memperuntukkan memori kepada elemennya secara berasingan dalam blok memorinya sendiri dan struktur keseluruhan diperoleh dengan memautkan elemen ini sebagai pautan dalam rantai. Setiap elemen dalam senarai terpaut mempunyai dua medan seperti yang ditunjukkan dalam Rajah 3. Medan data memegang data sebenar yang disimpan dan medan seterusnya memegang rujukan kepada elemen seterusnya dalam rantaian. Elemen pertama senarai terpaut disimpan sebagai ketua senarai terpaut.
| data | seterusnya |
Rajah 3: Elemen Senarai Terpaut
Rajah 4 menggambarkan senarai terpaut dengan tiga elemen. Setiap elemen menyimpan datanya dan semua elemen kecuali yang terakhir menyimpan rujukan kepada elemen seterusnya. Elemen terakhir memegang nilai nol dalam medan seterusnya. Mana-mana elemen dalam senarai boleh diakses dengan bermula di kepala dan mengikuti penunjuk seterusnya sehingga anda memenuhi elemen yang diperlukan.
Walaupun tatasusunan dan senarai terpaut adalah serupa dalam erti kata kedua-duanya digunakan untuk menyimpan koleksi elemen, ia mengalami perbezaan disebabkan oleh strategi yang mereka gunakan untuk memperuntukkan memori kepada elemennya. Tatasusunan memperuntukkan memori kepada semua elemennya sebagai satu blok dan saiz tatasusunan perlu ditentukan semasa masa jalan. Ini akan menjadikan tatasusunan tidak cekap dalam situasi di mana anda tidak mengetahui saiz tatasusunan pada masa penyusunan. Memandangkan senarai terpaut memperuntukkan memori kepada elemennya secara berasingan, ia akan menjadi lebih cekap dalam situasi di mana anda tidak mengetahui saiz senarai pada masa penyusunan. Pengisytiharan dan mengakses elemen dalam senarai terpaut tidak akan lurus ke hadapan berbanding dengan cara anda mengakses terus elemen dalam tatasusunan menggunakan indeksnya.
